题目内容
实现一个 LRUCache
类,三个接口:
-
LRUCache(int capacity)
创建一个大小为 capacity
的缓存
-
get(int key)
从缓存中获取键为 key
的键值对的 value
-
put(int key, int value)
向缓存中添加键值对 (key, value)
要求 get
和 put
的均摊时间复杂度为
O
(
1
)
O(1)
O(1)
题解
对于 get
操作,我们需要快速获取到 key
对应的键值对,哈希表可以解决。
对于 put
操作,我们需要快速 put
一个键值对,也可以用哈希表解决。
但是问题在于,我们 get
和 put
时,需要维护键值对最近使用的情况。
这部分我们可以用双向链表维护,每次操作一个键值对时,将其从原来链表的位置中移除,重新添加到链表头。定义链表头的数据是最近一次使用的,链表尾是最近最少使用的。
对于哈希表,键可以为 key
,映射到一个链表结点 LRUNode
,LRUNode
中包括前后链表结点,以及当前链表结点的 key
和 value
。
为什么我们要在链表结点中存储 key
呢,直接看上去没什么用。
考虑我们需要利用 LRU 策略从缓存中弹出一个最近最少使用的结点。
根据我们的定义,链表尾的结点是最近最少使用的,除了要将其从链表中移除,还需要将其从哈希表中移除,而从哈希表中移除需要使用 key
,这才是链表结点中存储 key
的原因。
定义LRU中的链表结点 LRUNode
。
struct LRUNode {
LRUNode* prev;
LRUNode* next;
int key;
int val;
LRUNode(int key, int val): key(key), val(val), prev(nullptr), next(nullptr) {}
};
对于 LRUNode
,其会从链表中被移除,也会被添加到链表,所以需要实现这两个方法
void removeLRUNodeFromLinklist(LRUNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void insertLRUNodeToLinklist(LRUNode* node) {
node->next = head->next;
head->next->prev = node;
head->next = node;
node->prev = head;
}
对于 LRUNode
,其会从哈希表 key2LRUNode
中被移除,也会被添加到哈希表 key2LRUNode
,所以需要实现这两个方法
void removeLRUNodeFromHashTable(LRUNode* node) {
if (!key2LRUNode.count(node->key)) return;
key2LRUNode.erase(node->key);
}
void insertLRUNodeToHashTable(LRUNode* node) {
key2LRUNode[node->key] = node;
}
接下来实现 get
的逻辑
int get(int key) {
// key 不存在
if (!key2LRUNode.count(key)) return -1;
// 取出 key 对应的 LRUNode
LRUNode* node = key2LRUNode[key];
// 当前 LRUNode 是最近一次使用的,将其放到链表头
removeLRUNodeFromLinklist(node);
insertLRUNodeToLinklist(node);
return node->val;
}
继续实现 put
的逻辑
void put(int key, int value) {
// 如果不存在 key ,则需要新建该键值对
if (!key2LRUNode.count(key)) {
// 缓存已满,要从缓存中通过LRU策略弹出最近最少使用的LRUNode
if (size_ >= capacity_) {
// 链表尾即最近最少使用的
LRUNode* node = tail->prev;
// 从链表中删去
removeLRUNodeFromLinklist(node);
// 从哈希表中删去
removeLRUNodeFromHashTable(node);
// 释放 node 的内存空间,如果是智能指针就不需要手动释放了
delete node;
// 释放一个空间
size_ -= 1;
}
// 创建一个新的 LRUNode
LRUNode* newLRUNode = new LRUNode(key, value);
// 添加到链表中
insertLRUNodeToLinklist(newLRUNode);
// 添加到哈希表中
insertLRUNodeToHashTable(newLRUNode);
size_ += 1;
} else {
// 获取到 key 对应的已存在于缓存中的 LRUNode 节点
LRUNode* node = key2LRUNode[key];
// 更新键值对的权值
node->val = value;
// 从链表中删去
removeLRUNodeFromLinklist(node);
// 添加到链表中
insertLRUNodeToLinklist(node);
// 添加到哈希表中,其实这步是不需要的,因为哈希表对应的是 LRUNode 的地址
insertLRUNodeToHashTable(node);
// 这里只是 key 对应的 value 修改了,size_ 不变
}
}