LRU缓存

LRU缓存可以通过哈希表辅以双向链表实现：

双向链表按照被使用的顺序存储缓存中的键值对，靠近头部是最近使用的，靠近尾部是最久使用的；

哈希表通过缓存数据的键映射到其在双向链表中的位置。

【即：首先使用哈希表定位，找出缓存项在双向链表中的位置；然后将其移动到双向链表的头部】

具体实现

1、get函数

如果key不存在，返回-1；

如果key存在，将其移动到双向链表的头部，返回该节点的值。

2、put函数

如果key不存在，使用key和value创建新节点，然后将该节点添加到双向链表头部，并将key和该节点添加到哈希表；其次判断双向链表中节点数是否超出容量，如果超出则删除尾部节点，并删除哈希表中对应的项；

如果key存在，类似get，通过哈希表定位，修改对应的节点值为value，并移动到双向链表的头部。

Note：双向链表中使用一个伪头部和伪尾部标记界限，在添加和删除节点时就不需要判断相邻节点是否存在。

struct DLinkedNode {int key, value;DLinkedNode* prev;DLinkedNode* next;DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}};class LRUCache {private:unordered_map cache;DLinkedNode* head;DLinkedNode* tail;int size;int capacity;public:LRUCache(int _capacity): capacity(_capacity), size(0) {//伪头节点和伪尾节点head = new DLinkedNode();tail = new DLinkedNode();head->next = tail;tail->prev = head;}int get(int key) {if(!cache.count(key)) {return -1;}//存在，先定位后移动DLinkedNode* node = cache[key];moveToHead(node);return node->value;}void put(int key, int value) {if(!cache.count(key)) {DLinkedNode* node = new DLinkedNode(key, value);cache[key] = node;addToHead(node);++size;if(size > capacity) {DLinkedNode* removed = removeTail();cache.erase(removed->key);//防止内存泄露delete removed;--size;}}else {DLinkedNode* node = cache[key];node->value = value;moveToHead(node);}}void addToHead(DLinkedNode* node) {node->prev = head;node->next = head->next;head->next->prev = node;head->next = node;}void removeNode(DLinkedNode* node) {node->prev->next = node->next;node->next->prev = node->prev;}void moveToHead(DLinkedNode* node) {removeNode(node);addToHead(node);}DLinkedNode* removeTail() {DLinkedNode* node = tail->prev;removeNode(node);return 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); */