LRU缓存实现-创新互联
LRU(Least Recently Used)最近最少使用算法，通过淘汰最久为使用的缓存使缓存容量满足一致性
(1) LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
(2) int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
(3)void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
(4)函数 get 和 put 必须以 O(1) 的平均时间复杂度运行
输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
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
(1)使用双向链表，从虚拟头节点插入时，尾节点就是最久未使用的节点，头节点就是最新插入的节点。由于双向链表的特性，删除链表中的节点的时间复杂度是O(1)。
(2)构建一个key-value结构，可以记录put()方法插入的键值，以及对应的节点地址，从而方便找到双向链表中的对应节点，此hash表结构为key(键)-value(值，对应节点地址)
(3)对于get(key)方法，需要满足获取到get(key)的值后，将双向链表的对应节点删除，并且重新从虚拟头节点后加入，然后维护hash表结构，记录key(键)-value(值，对应节点地址)
(4)对于put(key,value)方法，需要分类讨论
1)容量未满时，key值已经存在时，删除双向链表中对应节点，从虚拟头节点后再次加入，然后维 护hash表结构
key值不存在(新的key，value)，创建新的节点，直接从双向链表中的虚拟头节点后加入，维护hash表结构
2）容量已满，key值已经存在时，删除双向链表中对应节点，从虚拟头节点后再次加入，然后维 护hash表结构
key值不存在(新的key，value)，需要将双向链表尾节点删除，维护hash表中的信息(删除过期系欸但信息)，然后创建新节点，直接从双向链表中的虚拟头节点后加入，维护hash表结构(增加新节点信息)
class LRUCache {private:
struct Node{//双向链表的节点信息
int key = -1;
int val = -1;
Node* pre = NULL;
Node* next = NULL;
};
struct element{// hash表中的元素信息
int val = -1;
Node* addr = NULL;
};
Node* VirtualNode;// 链表的虚拟头节点
Node* tailNode; // 链表的尾节点
int size = 0;// 记录链表长度
int capacity;// 容量
unordered_mapmp; // hash表
public:
LRUCache(int capacity) {
this->capacity = capacity; // 初始化容量
this->VirtualNode = new Node(); // 初始化虚拟头节点
this->tailNode = this->VirtualNode;
}
void addLinkedList(Node* node){//从头插入节点
if(VirtualNode->next == NULL){VirtualNode->next = node;
node->pre = VirtualNode;
}else{Node* temp = VirtualNode->next;
node->next = temp;
node->pre = VirtualNode;
VirtualNode->next = node;
temp->pre = node;
}
// 维护尾指针，第一次插入的节点为尾指针
if(size == 0){tailNode = node;
}
size++;
}
void removeLinkedList(Node* node){//删除某个节点，使用双向链表可以找到该节点的前一个和后一个节点
Node* preNode = node->pre;
Node* nextNode = node->next;
// 需要删除的节点是尾节点
if(node == tailNode){preNode->next = NULL;
tailNode = preNode;// 维护尾节点
}else{preNode->next = nextNode;
nextNode->pre = preNode;
}
size--;
}
int get(int key) {// 没有节点或需要查询的节点已经过期
if( size == 0 || mp[key].val == -1){return -1;
}
else{// 如果节点过期，需要将hash表中的val值置为-1，此时链表中已经不存在该节点，无法完成删除操作
// 更新链表，使得尾节点是最近最少使用的节点，头节点是最近使用过的节点
// 删除mp[key].addr节点，并且从头插入此节点
removeLinkedList(mp[key].addr);
addLinkedList(mp[key].addr);
return mp[key].val;
}
}
void put(int key, int value) {
// 链表长度小于capacity
if(this->size< this->capacity){// 如果key值存在过了
if(mp[key].val != -1){// 将链表中的mp[key].addr节点删除，重新添加
removeLinkedList(mp[key].addr);
addLinkedList(mp[key].addr);
// 维护hash表，更新val
mp[key].val = value;
}else{//key值之前未添加过，添加新的key值
// 创建新节点
Node* node = new Node;
node->key = key;
node->val = value;
//向链表中添加新节点node
addLinkedList(node);
//维护hash表
mp[key].val = value;
mp[key].addr = node;
}
}else{//链表长度超过容量
// 如果之前key值存在过了，不产生新节点
if(mp[key].val != -1){// 将链表中的mp[key].addr节点删除，重新添加
removeLinkedList(mp[key].addr);
addLinkedList(mp[key].addr);
//维护hash表
mp[key].val = value;
}else{// 如果之前key值不存在，产生新节点
// 维护hash表,节点过期
mp[tailNode->key].val = -1;
// 删除链表尾部节点（最近最少使用）
removeLinkedList(tailNode);
// 创建新节点
Node* node = new Node;
node->key = key;
node->val = value;
// 添加新节点
addLinkedList(node);
// 维护hash表
mp[key].val = value;
mp[key].addr = node;
}
}
}
}; 可见在向LinkedList中加入元素后，都需要维护hash表，所以代码可以调整，并且使用stl中的list结构代替自己编写的双向链表，从而减少代码量
class LRUCache {private:
struct element{// hash表中的元素信息
int val = -1;
list::iterator addr;
};
listLinkedList;//使用双向链表
// int size = 0;// 记录链表长度，由于list.size()函数的时间复杂度是O(N),可以通过维护一个size()值减少此处的时间消耗
int capacity;// 容量
unordered_mapmp; // hash表
public:
LRUCache(int capacity) {this->capacity = capacity; // 初始化容量
}
int get(int key) {// 没有节点或需要查询的节点已经过期
if( LinkedList.size() == 0 || mp[key].val == -1){return -1;
}
else{// 如果节点过期，需要将hash表中的val值置为-1，此时链表中已经不存在该节点，无法完成删除操作
// 更新链表，使得尾节点是最近最少使用的节点，头节点是最近使用过的节点
// 删除mp[key].addr节点，并且从头插入此节点
LinkedList.erase(mp[key].addr);
LinkedList.push_front(key);
mp[key].addr = LinkedList.begin();
return mp[key].val;
}
}
void put(int key, int value) {// 链表长度小于capacity
if(LinkedList.size()< this->capacity){// 如果key值存在过了
if(mp[key].val != -1){// 将链表中的mp[key].addr节点删除，重新添加
LinkedList.erase(mp[key].addr);
LinkedList.push_front(key);
}else{//key值之前未添加过，添加新的key值
//向链表中添加新节点node
LinkedList.push_front(key);
}
}else{//链表长度超过容量
// 如果之前key值存在过了，不产生新节点
if(mp[key].val != -1){// 将链表中的mp[key].addr节点删除，重新添加
LinkedList.erase(mp[key].addr);
LinkedList.push_front(key);
}else{// 如果之前key值不存在，产生新节点
// 维护hash表,节点过期
mp[LinkedList.back()].val = -1;
// 删除链表尾部节点（最近最少使用）
LinkedList.pop_back();
// 添加新节点
LinkedList.push_front(key);
}
}
// 维护hash表，更新val
mp[key].val = value;
mp[key].addr = LinkedList.begin();
}
}; 注：list结构的list.size()方法的时间复杂度为O(n)，因为其内部调用了distance()方法计算了所有元素的个数，因此可以使用size变量得到双向链表得长度
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
本文题目：LRU缓存实现-创新互联
本文来源：http://ybzwz.com/article/ccicii.html
