缓存系统

最久未使用缓存机制

最久未使用(Least Recently Used, LRU)缓存机制，将最近最少使用的内容替换掉。

利用哈希表和双向链表实现LRU缓存机制，使查找、添加和删除都是的操作。

待缓存的内容以键值对key-value的形式存在，哈希表存储了已经存在于缓存区的内容的key。双向链表的节点按照访问时间排序，越靠近尾部，越久没有被访问。

读取缓存时，只需要在哈希表中查找是否存在key，存在则返回对应的value，同时，这是最新访问的key-value，就把它移动到链表头部，如果不存在，就将其直接插入到链表头部。

更新缓存时，直接将key-value更新到链表头部即可，如果超出缓存区容量，将尾部节点删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <unordered_map>

class LRUCache {
public:
    explicit LRUCache(const int _capacity): capacity(_capacity) {
        dummy_head = new Node();
        dummy_tail = new Node();
        dummy_head->next = dummy_tail;
        dummy_tail->prev = dummy_head;
    }

    int get(const int key) {
        if (keys_mp.find(key) == keys_mp.end()) {
            return -1;
        }
        const int value = keys_mp[key]->value;
        removeFromCache(keys_mp[key]);
        insertToCache(key, value);

        return value;
    }

    void put(const int key, const int value) {
        if (keys_mp.find(key) != keys_mp.end()) {
            removeFromCache(keys_mp[key]);
        }
        insertToCache(key, value);

        if (keys_mp.size() > capacity) {
            keys_mp.erase(dummy_tail->prev->key);
            removeFromCache(dummy_tail->prev);
        }
    }

private:
    int capacity;
    typedef struct Node {
        int key;
        int value;
        Node *prev;
        Node *next;
        Node(): key(0), value(0), prev(nullptr), next(nullptr) {}
        Node(const int _key, const int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
    } Node;

    std::unordered_map<int, Node *> keys_mp;
    Node *dummy_head;
    Node *dummy_tail;

    void insertToCache(const int key, const int value)  {
        const auto node = new Node(key, value);
        keys_mp[key] = node;

        node->next = dummy_head->next;
        node->prev = dummy_head;
        dummy_head->next->prev = node;
        dummy_head->next = node;
    }

    static void removeFromCache(const Node * node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;

        delete node;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */