LRU的实现

题目内容

实现一个 LRUCache 类，三个接口：

• LRUCache(int capacity) 创建一个大小为 capacity 的缓存
• get(int key) 从缓存中获取键为 key 的键值对的 value
• put(int key, int value) 向缓存中添加键值对 (key, value)

要求 get 和 put 的均摊时间复杂度为 $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 对应的 LRUNodeLRUNode* node = key2LRUNode[key];// 当前 LRUNode 是最近一次使用的，将其放到链表头removeLRUNodeFromLinklist(node);insertLRUNodeToLinklist(node);return node->val;
}

继续实现 put 的逻辑

void put(int key, int value) {// 如果不存在 key ，则需要新建该键值对if (!key2LRUNode.count(key)) {// 缓存已满，要从缓存中通过LRU策略弹出最近最少使用的LRUNodeif (size_ >= capacity_) {// 链表尾即最近最少使用的LRUNode* node = tail->prev;// 从链表中删去removeLRUNodeFromLinklist(node);// 从哈希表中删去removeLRUNodeFromHashTable(node);// 释放 node 的内存空间，如果是智能指针就不需要手动释放了delete node;// 释放一个空间size_ -= 1;}// 创建一个新的 LRUNodeLRUNode* 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_ 不变}
}