LRU 缓存
LRU，即Least-Recently-Used。是一种高速缓存替换策略，是一种缓存机制。主要是利用局部性原理。
局部性原理分两种，空间局部性和时间局部性。
在一个具有良好时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来再被多次应用。
在一个具有良好空间局部性的程序中，如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。
显然，LRU是利用到了时间局部性。
在CSAPP的P434 组相联高速缓存中不命中时的行替换 出现。
最近最少使用（LRU）策略会替换最后一次访问时间最久远的那一行。
题目分析
实现 LRUCache 类：
-
LRUCache(int capacity)以 正整数 作为容量 capacity 初始化 LRU 缓存 -
int get(int key)如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 -
void put(int key, int value)如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。来源：力扣（LeetCode）
这是一道很优秀的设计问题，而不是关于某个问题的算法。
题目要求你利用相关的知识，设计一个能够简单实现LRU 缓存机制的类。
根据刚刚所说的CSAPP中的背景知识，可以知道要设计出的类：
- 需要存储每个键值。（put函数插入，get函数查询）
- 键值对（key，value）需要用哈希表来存储。（O(1) 的平均时间复杂度）
那现在留下的问题就是，如何做到逐出。
队列
首先可以想到，利用队列的先进先出原则。
- 如果使用了，就将它拿出，再插入到队列中。
- 队首为最久未使用，队尾为最近使用。
那么如何逐出？拿出怎么做到？这里就遇到了难以删除的问题。
双向链表
所以，下面介绍双向链表的解法。
- 双向链表可以直接访问到尾部。尾部代表最久未使用。
- 链表方便插入和删除。
- 根据键值，利用哈希表能定位到对应的存储节点。
内存泄漏？
双向链表可以利用指向关系做到删除，将节点剔除于链表外。
然而我们在剔除后，对于访问的节点来说，还需要再加到头部节点。而对于没有访问的节点，我们需要真正删除它。
所以代码中有两个delete函数，来避免内存泄漏。
代码
class LRUCache {
private:
struct DoubleLinkNode {
int key;
int value;
DoubleLinkNode* prev;
DoubleLinkNode* next;
DoubleLinkNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
DoubleLinkNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr){}
};
map<int, DoubleLinkNode *> cache;
DoubleLinkNode* head;
DoubleLinkNode* tail;
int capacity;
int size;
void addNodeHead(DoubleLinkNode* node)//双向链表头插法
{
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
void deleteNode(DoubleLinkNode* node)//剔除尾节点
{
node->next->prev = node->prev;
node->prev->next = node->next;
}
void moveNodeHead(DoubleLinkNode* node)
{
deleteNode(node);
addNodeHead(node);
}
DoubleLinkNode* deleteTail()//删除尾节点
{
DoubleLinkNode* temp = tail->prev;
deleteNode(temp);
return temp;
}
public:
LRUCache(int capacity)
{
this->capacity = capacity;
size = 0;
head = new DoubleLinkNode();
tail = new DoubleLinkNode();
head->next = tail;
tail->prev = head;
}
int get(int key)
{
if (cache.count(key))
{
moveNodeHead(cache[key]);
return cache[key]->value;
}else
{
return -1;
}
}
void put(int key, int value)
{
if (cache.count(key))
{
cache[key]->value = value;
moveNodeHead(cache[key]);
}else
{
DoubleLinkNode* node = new DoubleLinkNode(key, value);
addNodeHead(node);
cache[key] = node;
size += 1;
if (size > capacity)
{
DoubleLinkNode* temp = deleteTail();
cache.erase(temp->key);
delete temp;//避免内存泄漏
size -= 1;
}
}
}
};
/**
* 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);
*/