1
基于双向链表的 LRUCache 实现
source link: https://hsiaofongw.notion.site/LRUCache-cbc91d54f84f41e29ac3efcaed1e0ac1
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Drag image to reposition
基于双向链表的 LRUCache 实现
Created
July 27, 2022 4:17 PM
cache
cacheInvalidating
keyEvictionPolicy
Description
该文介绍了基于双向链表的LRUCache的实现。LRUCache需要实现put和get操作，通过哈希表和双向链表实现。哈希表用于快速查找key对应的节点，双向链表用于维护LRU顺序。当put操作时，如果容量已满，则淘汰最久未使用的节点，即LRU节点。当get操作时，返回节点对应的value，并将该节点移动到链表头部，表示最近使用过。该实现还考虑了一些细节，如LRU节点的删除和更新等。
Updated
July 16, 2023 5:58 AM
3 more properties
缓存数据结构与缓存失效策略
LRU Cache 说的是一种数据结构，对于类型参数 KeyT, ValT, 它至少支持：
void put(KeyT k, ValT v); // 存
Maybe<ValT> get(KeyT k); // 取
两种操作。
更详细地描述这个 LRUCache 支持的方法是这样：
因为对于 put 方法，传入的 key 需要被保存在内部的 HashMap 中，所以我们没有用引用，以此强调这个 KeyT 类型的 key 对象本身至少会被复制一次，复制到内部的 HashMap 中作为 key.
LRU Cache 中的 LRU 是一种缓存失效策略。
什么是缓存失效策略呢？当缓存空间占满了，而且又立刻需要缓存空间来存放从未见过的键值对的时候，一个 Cache 的实现就需要自己判断该使现有的哪一个键失效（从而把空间让出来），至于它是如何判断该选哪个的，就是缓存失效策略。
LRU 大概是这样的一个策略：当有需要的时候（当不得不的时候），我就使「最久没有被访问过」的键值对失效。你可以把它理解为键值对缓存的末位淘汰策略。
举个例子，假设我们有一个 capacity 为 3 的 LRU Cache 实例：
我们先做 3 次 put 操作：
现在，最久没有被碰过的 key 是 1, LRU Key 是 1.
而假如说我们这个时候再做一次 get 操作呢？
这时 LRU Key 是 2, 因为按照 put 的顺序，1 是最久没有被访问的，其次是 2, 其次是 3, 现在 1 被访问了，这个最久没有被访问的 key 就顺延到了 2, 你可以想象逻辑上这里存在一个「队列」，不过我们不一定用队列实现 LRU Cache.
这时，如果我们再 put 一个新的 key, 并且 put 之后再去 get 2, 就会发现 2 已经失效了：
这时因为，在 put 4 的时候，lruCache 拢共也就 3 的 capacity, 之前 3 个键值对已经把这个大小为 3 的 capacity 用完了，而 4 这个 key 不属于现有的任何一个 key, 所有 lruCache 需要找空间来放入这个新 key 4, 而缓存的 capacity 一般而言是很难变化的，所以就不得不选一个 key 来使它失效，从而把空间让出来给新的 key.
说到这里，相信你已经明白「缓存数据结构」，「缓存失效策略」，LRU 都分别是怎么一回事了。
实现一个 LRU Cache 数据结构的关键构件
实现一个 LRU Cache 需要实现它的两种操作：put 和 get, 而 put 和 get 除了把外部 KeyT 转为内部可寻址类型之外，还要:
判断外部传来的 key 是否有效；
如果有效，让它「更新」，从而不会被 LRU 策略末位淘汰；(也就是 LRUCache 内部的 renew 操作）
如果无效，操作是 put, 你得就是说选一个 key 来淘汰掉，让被淘汰掉的 key 变得无效，然后把新的键值对存入。
对于 1, 我的思路是在一个 HashMap 里边找这个 key, 如果这个 key 在里边，它就是有效的，否则就是无效的。HashMap 的 search 操作的时间复杂度在某些实现下是常量级别的。
对于 2, 我们引入一个环状双链表 DoubleLinkedList，具体后面细说。这是重点。
对于 3, 需要在环状双链表和 HashMap 都进行操作。
环状双链表
一个 DoubleLinkedList 构件在 LRUCache 中主要负责下列两件事：
维护一个指向 LRU Key 节点的指针；这个实际上是尾指针；
支持对一个 Key 节点进行 renew 操作，比如说当前 2 是 LRU Key, 3 是「次 LRU Key」，我 renew 2 这个 key, 那么 LRU Key 就应当变为另一个，变为 3 比如说；
一个 DoubleLinkedList 的结构是这样的：
在使用的时候，LRUCache 会在内部维护一个 capacity 个节点的双链表，双链表的节点的类型就是这个 DoubleLinkedList , 而 LRUCache 通过记录一个 std::shared_ptr<DoubleLinkedList> tail 指针来实现对这个成环的双链表的控制。
在任何时候，当需要 invalidate key 的时候，都是 invalidate tail 指针指向的那个节点中的 data 对象存储的 key, 找到这个 key 之后就去 HashMap 那里对这个 key 绑定 nullptr, 这就实现了 LRU Key 的 invalidate.
因为这个链表构造的时候就会被连接成环状，tail->next 是首指针，比如说 tail → x → y → z → … → tail → x, 我现在访问 y 这个 key, 那么就要对 y renew, 那么这个链表的结构就变为：tail → z → x → y → … → tail → z.
一句话概括就是：renew 一个 key 就是把它对应的节点交换到双链表的首节点，我们会发现这样的操作在双链表中，尤其是成环的双链表中是很容易办到的。
唯一需要考虑的一个 corner case 是被 renew 的那个 key 它对应的节点刚好是 tail 节点，那你就 rotate 一下这个双链表就行了，怎么 rotate 呢？this->tail = this->tail->prev.
纯文字描述可能过于抽象，从下面开始我想细说一下这个 LRU 缓存它跟 DoubleLinkedList 数据结构、HashMap 数据结构之间究竟是有着怎样的联系。
总体来说，DoubleLinkedList 和 HashMap 用来支撑 LRUCache 的内部实现，回顾前面，我们知道，一个 LRUCache 至少要实现两个方法：
我们先来看一下 get 方法，key 的内部 renew 操作和 evict (或者叫 invalidate) 操作先略过不讲。
首先，KeyT 是一个类型参数，那么 KeyT 到底是什么对于这个 template class 的编写者来说是不知道的，但无论如何，咱们至少可以合理的要求这个 KeyT 是 Hashable 的，也就是说，要求有一种方法能够把这个 KeyT key 对象 hash 成一个 [0, M) 范围内的整型下标值，其中 M 是哈希表结构内部的桶 (bucket) 的数量。
再者，假设我们已经得到了：
并且假设 hash collision 问题已经解决（已经通过某种方式解决），最终我们得到一个指针：
对，你没看错，基本的思路就是 LRUCache 内部维护着一个 capacity 长度的双链表，然后每个 key 指向一个双链表节点。
如果当前已经有了 capacity 个 key, 下次 put 的时候就直接覆写最旧的那个双链表节点 lruNode，并且在覆写之前从内部 HashMap 中删除 lruNode 的那个 key.
其实我们不用判断当前是不是已经有了 capacity 个 key, 我们直接每次 put 的时候直接往最旧的那个双链表节点 DoubleLinkedListNode *lruNode 覆写，并且覆写之前从内部的 HashMap 中删除 lruNode->data.key 这个 key 就可以了。
现在我们已经从 KeyT key 得到了 nodePtr , 如果是 get 操作，返回 nodePtr->data.val , 并且 renew nodePtr->data.key, 如果是 put 操作，那就是把 val 写到 nodePtr->data.val , 并且也 renew nodePtr->data.key.
基本上，你可以理解为，每次 put 或者 get, 都是先从 key 通过 HashMap 得到 nodePtr, 然后更新或者返回 nodePtr->data.val 的值。
以下为基于双链表的 LRUCache 设计架构示意图：
更准确地描述，size_t index 应该指向哈希桶才对，这里我画成了 Array, 不过你只要能够明白这个意思就行。当然你也可以把 Array 看成是关于桶的 Array, 能理解就行。
那个 LRUCache 内部维护的一个 tail 指针它实际上总是指向 LRUNode, 而 LRUNode 因为也是 tail, tail 的下一个也就是 tail->next 就是 head, 就是最新使用的。
所以，如果我们想 renew 一个 key, 只要把这个 key 对应的节点想办法挪到 tail->next 的位置，再让新上位的 tail-next 的下一个是旧的 tail->next 就可以了。
特例，当 currentNode 恰好就是 tail 的时候，不允许这样做，具体为何，请参看文末参考实现的代码。
如果我们想 invalidate 一个 LRU key, 我们就找到 LRUNode, 然后从 LRUNode 中取 key, 再在 LRUCache 内部维护的那个 HashMap 类型的对象中对这个 key 做 delete 操作就行了。
我自己写的实现：
核心代码：
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK