什么是 LRU cache?
1.LRU cache 是一种缓存淘汰策略, 因为任何计算机的缓存都是有限的, 所以缓存满了的时候就要淘汰一些, 然后让新的进来;
2.典型的例子是手机杀后台: 假设我按照时间顺序依次打开 4 个 app, 最大的缓存容量就是4, 再这样的配置下, 我们按下后台键; 日历 淘宝 抖音 小红书 ui上面小红书距离我们最近, 抖音第二, 淘宝第三, 日历第四
假设现在我们又打开了知乎, 这时候缓存不够了, 要选择一个淘汰, LRU 算法下把时间距离最远的 [日历] 淘汰掉变成: 淘宝 抖音 小红书 知乎; 这就是 LRU cache 算法起到的作用
思考下我们需要设计怎样的数据结构才能高效地实现这个过程:
1.首先我们要模拟时间顺序进出, 所以我们要用到队列
2.查找的时候需要 O(1) 实现, 那么就需要哈希表
3.要求插入和删除都是 O(1) 实现, 我们就需要引入链表这种结构, 兼顾到模拟时间顺序进出, 所以要用双向的链表模拟队列; 插入的时候每次插入到头部, 删除的时候需要用哈希表找到待删除节点, 执行删除操作
146.LRU 缓存
请你设计并实现一个满足 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) 的平均时间复杂度运行。示例：
输入
[“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
struct DLinkedListNode {
int key;
int value;
DLinkedListNode* pre;
DLinkedListNode* next;
DLinkedListNode(): key(0), value(0) {}
DLinkedListNode(int _key, int _value): key(_key), value(_value), pre(nullptr), next(nullptr) {}
};
class LRUCache {
private:
int size;
int totalCapacity;
DLinkedListNode* dummyHead;
DLinkedListNode* dummyTail;
unordered_map<int, DLinkedListNode*> key2node;
public:
LRUCache(int capacity) {
size = 0;
totalCapacity = capacity;
dummyHead = new DLinkedListNode();
dummyTail = new DLinkedListNode();
dummyHead->next = dummyTail;
dummyTail->pre = dummyHead;
}
// 如果待查询 key 不存在, 是个无效的查询, 直接返回 -1
// 如果存在, 移动 key 所在的 node 到开头
int get(int key) {
if (!key2node.count(key)) {
return -1;
}
DLinkedListNode* node = key2node[key];
moveNodeToHead(node);
return node->value;
}
// 如果待添加的 key 不存在, 加入哈希表
// 如果已经存在了, 移动在链表头, 重写 value
void put(int key, int value) {
if (!key2node.count(key)) {
DLinkedListNode* node = new DLinkedListNode(key, value);
key2node[key] = node;
addNodeToHead(node);
++size;
if (size > totalCapacity) {
// 返回待删除的节点的指针
DLinkedListNode* node = removeNodeTailNode();
key2node.erase(node->key);
delete node;
--size;
}
} else {
DLinkedListNode* node = key2node[key];
node->value = value;
moveNodeToHead(node);
}
}
void moveNodeToHead(DLinkedListNode* node) {
removeNode(node);
addNodeToHead(node);
}
// 双端操作: 先把 node 向 前后节点建立联系, 然后前后节点和 node 向 前后节点建立联系
void addNodeToHead(DLinkedListNode* node) {
node->pre = dummyHead;
node->next = dummyHead->next;
dummyHead->next->pre = node;
dummyHead->next = node;
}
void removeNode(DLinkedListNode* node) {
node->pre->next = node->next;
node->next->pre = node->pre;
}
DLinkedListNode* removeNodeTailNode() {
DLinkedListNode* node = dummyTail->pre;
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);
*/
转载请注明来源, from goldandrabbit.github.io
