关于算法:算法LRU缓存机制

题目：

设计和实现一个 LRU (最近起码应用) 缓存机制。
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存。
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。
void put(int key, int value) 如果关键字曾经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字 - 值」。当缓存容量达到下限时，它应该在写入新数据之前删除最久未应用的数据值，从而为新的数据值留出空间。
是否能够在 O(1) 工夫复杂度内实现这两种操作？

解决办法：

哈希表 + 双向链表
1、双向链表：节点凑近头部是最近应用的，凑近尾部是最久未应用的，在双向链表的头部增加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。
2、哈希表：通过缓存数据的键映射到其在双向链表中的地位（定位），查找节点工夫复杂度：o(1)。
3、为了在链表操作过程中更少的判断头尾节点是否为 null，采纳哨兵机制，头尾都增加哨兵（与传统双向链表性能貌似无很大差异，只是判断 nullptr 较多容易出错）。

源码剖析：

// 节点定义
struct DLinkedNode
{
        int key, value; // 节点在 hash 表里的键值和值
        DLinkedNode*  prev;     // 此节点的前驱节点
        DLinkedNode*  next;     // 此节点的后继节点
        DLinkedNode() :key(0), value(0), prev(nullptr), next(nullptr) {} // 构造函数，赋值 key 和 value
        DLinkedNode(int _key, int _value) :key(_key), value(_value), prev(nullptr), next(nullptr) {} // 带参构造函数（重载）};
 
//LRU 缓存类
class LRUCache {
private:
        unordered_map<int, DLinkedNode*> cache; // 哈希映射表 
        DLinkedNode* head; // 双向链表头结点
        DLinkedNode* tail; // 双向链表尾结点
        int size; // 以后节点个数
        int capacity; //LRU 缓存最大节点个数（容量）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);
                }
        }
 
private:
        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;
        }
};
 
/*
测试数据：#include<iostream>
#include<unordered_map>
using namespace std;
 
int main(){LRUCache* lRUCache = new LRUCache(2);
        lRUCache->put(1, 1); // 缓存是 {1=1}
        lRUCache->put(2, 2); // 缓存是 {1=1, 2=2}
        lRUCache->get(1);    // 返回 1
        lRUCache->put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        lRUCache->get(2);    // 返回 -1 (未找到)
        lRUCache->put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        lRUCache->get(1);    // 返回 -1 (未找到)
        lRUCache->get(3);    // 返回 3
        lRUCache->get(4);    // 返回 4
 
        system("pause");
        return 0;
}
*/