设计实现LRU缓存机制

一、要求

LRU：最近最少使用算法

支持：get 和 put 操作
- get(key): 获取数据 get, 如果密钥 (key) 存在于缓存中，则返回对应的值
- put(key, value): 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少未使用的数据值，从而为新的数据值留出空间。
get 和 put 时间复杂度 $O(1)$
题目：https://leetcode-cn.com/problems/lru-cache/

二、实现

1. 说明

其实标准的 hash 数据结构可以实现get 操作 $O(1)$ , 但是针对put 操作的中，`到达内存容量上限是，删除最近最少使用的数据值的, 简单hash 无法做到 $O(1)$ ，因为无法判断那些数据是最近最少使用的。我们采取一个双向链表去维护LRU的数据值。

双向链表

如图所示，我们建立一个双向的链表去维持LRU 这么一个概念，通过头节点和尾节点去维护这个双向链表。我们每次操作一个节点（get, put)的时候，都把这个节点移到头节点后面。这样经过一系列的操作后，链表除了尾节点的最后一个就是最近最少使用的数据值。因为凡是被操作过的节点都是插入到头节点后面，未被操作的节点慢慢就挪到了尾部。

2. 实现hash

这里面我们采取的C++ STL中的unordered_map作为hash结构的实现。

3. 实现双向链表

链表的节点数据结构

template<typename K, typename V>
struct BiNode {
    K key;
    V value;
    BiNode(int k, int v = 0):key(k), value(v){};
    shared_ptr<BiNode> pre;
    shared_ptr<BiNode> next;
};

template<typename K, typename V>
bool operator==(const BiNode<K, V>& node1, const BiNode<K, V>& node2){
    return node1.key == node2.key;
}

namespace std {

    template<typename K, typename V>
    struct hash<BiNode<K, V>> {
        size_t operator()(const BiNode<K, V>& node) const noexcept {
            return std::hash<size_t>()(node.key);
        }
    };
}

应为我们会在unorderd_map中存储链表，所以要重载等于（==）和hash，使节点可以计算哈希值和判断散列冲突。

实现维护LRU的双向链表

template<typename K, typename V>
class LRUList {
public:
    using NodeType = BiNode<K, V>;
    using PNodeType = shared_ptr<NodeType>;

    LinkedList(){
        head_ = make_shared<NodeType>();
        tail_ = make_shared<NodeType>();
        head_->next = tail_;
        tail_->pre = head_;
    }

    PNodeType add(K key, V value){
        PNodeType node = make_shared<NodeType>(key, value);
        PNodeType next = head_->next;
        node->next = next;
        next->pre = node;
        head_->next = node;
        node->pre = head_;
    }

    PNodeType pop(){
        PNodeType target = tail_->pre;
        if(target == head_)
            return NullNode;
        PNodeType pre = target->pre;
        pre->next = tail_;
        tail_->pre = pre;
        return target;
    }

    PNodeType move_to_head(PNodeType node){
        PNodeType pre  = node->pre;
        PNodeType next = node->next;
        pre->next = next;
        next->pre = pre;

        next = head_->next;
        
        node->next = next;
        next->pre = node;
        node->pre = head_;
        head_->next = node;
    }

public:
    static const PNodeType NullNode = make_shared<NodeType>();
private:
    PNodeType head_;
    PNodeType tail_;
};

可以看到我们所有操作都是通过头节点和尾节点实现的，所以我们这个链表的操作的复杂度都是 $O(1)$ 的。

三、LRU 缓存机制

最终我们组合unordered_map(哈希）和 LRUList (双向链表）实现 LRU 缓存机制。

get(key): 获取的时候我们通过unordered_map直接获得对应的值， $O(1)$
put(key, value): 插入数据时候如果键值存在，直接插入。如果不存在，内存足够时，直接将节点插入unordered_map和LRUList中即可；不足时，现在LRUList中获取最近最实用的值，把其在哈希表和双向链表中删除，再插入新的节点。复杂度 $O(1)$


template<typename K, typename V>
class LRUCache {
public:
    using PNodeType = shared_ptr<BiNode<K, V>>;
public:

    LRUCache(int cap):cap_(cap){};
    PNodeType get(int key){
        if(dict_.count(key)){
            PNodeType node = dict_[key];
            list_.move_to_head(node);
            return node;    
        }
        
        return LRUList<K, V>::NullNode;
    }

    void set(int key, int val){
        PNodeType cur = nullptr;
        
        if(dict_.count(key)){
            cur = dict_[key];
            cur->value = val;
        }else{
            if(dict_.size() == cap_){
                auto del_node = list_.pop();
                dict_.erase(del_node->key);
            }
            cur = list_.add(key, val);
            dict_[key] = cur;
        }
        list_.move_to_head(cur);
    }

private:
    size_t cap_ = 0;
    LRUList<K, V> list_ = {};
    unordered_map<K, BiNode<K, V>> dict_ = {};
};