0146. LRU Cache
===============
题目信息
--------
:题号: 0146. LRU 缓存
:难度: Medium
:主题: 设计、哈希表、双向链表、数据结构不变量
:原题: `LeetCode 0146 `_
:重点: 让哈希表回答键定位,让双向链表维护使用顺序,并保持两种结构对每个缓存项的一一对应
题目重述
--------
设计容量固定的最近最少使用缓存 ``LRUCache``:
* ``get(key)``:键存在时返回值,并把它更新为最近使用;不存在返回 ``-1``,顺序不变;
* ``put(key, value)``:已有键就更新值并刷新为最近使用;新键则插入。插入后超过容量时,删除最久没有被
成功 ``get`` 或 ``put`` 的键。
两种操作都要求平均 ``O(1)`` 时间。容量至少为一。
自建示例
--------
.. code-block:: text
LRUCache cache(2)
put(4, 40) 顺序:[4]
put(7, 70) 顺序:[7, 4]
get(4) -> 40 顺序:[4, 7]
put(9, 90) 顺序:[9, 4],淘汰 7
get(7) -> -1 顺序仍为 [9, 4]
容量为一时连续执行 ``put(3, 8)``、``put(3, 11)`` 只是更新同一条目,不应先淘汰再创建;随后
``get(3)`` 返回 ``11``。
C++ 实现
--------
.. code-block:: cpp
#include
class LRUCache {
private:
struct Node {
int key;
int value;
Node* previous;
Node* next;
Node(int nodeKey, int nodeValue)
: key(nodeKey),
value(nodeValue),
previous(nullptr),
next(nullptr) {}
};
int capacity_;
std::unordered_map index_;
Node* mostRecentSentinel_;
Node* leastRecentSentinel_;
void detach(Node* node) {
node->previous->next = node->next;
node->next->previous = node->previous;
}
void insertAsMostRecent(Node* node) {
node->previous = mostRecentSentinel_;
node->next = mostRecentSentinel_->next;
mostRecentSentinel_->next->previous = node;
mostRecentSentinel_->next = node;
}
void markAsMostRecent(Node* node) {
detach(node);
insertAsMostRecent(node);
}
public:
LRUCache(int capacity)
: capacity_(capacity),
mostRecentSentinel_(new Node(0, 0)),
leastRecentSentinel_(new Node(0, 0)) {
mostRecentSentinel_->next = leastRecentSentinel_;
leastRecentSentinel_->previous = mostRecentSentinel_;
}
int get(int key) {
auto found = index_.find(key);
if (found == index_.end()) {
return -1;
}
Node* node = found->second;
markAsMostRecent(node);
return node->value;
}
void put(int key, int value) {
auto found = index_.find(key);
if (found != index_.end()) {
Node* node = found->second;
node->value = value;
markAsMostRecent(node);
return;
}
Node* node = new Node(key, value);
index_[key] = node;
insertAsMostRecent(node);
if (static_cast(index_.size()) > capacity_) {
Node* victim = leastRecentSentinel_->previous;
detach(victim);
index_.erase(victim->key);
delete victim;
}
}
~LRUCache() {
Node* node = mostRecentSentinel_;
while (node != nullptr) {
Node* next = node->next;
delete node;
node = next;
}
}
};
题解
----
先列出每次操作真正需要什么
~~~~~~~~~~~~~~~~~~~~~~~~~~
``get`` 需要按键找到条目,并把它移到“最新”位置;``put`` 还需要在容量超限时立刻找到“最旧”条目。于是
至少有三类基本操作:
* 按键定位任意条目;
* 已知条目时从顺序中删除并移到最前;
* 直接取得并删除顺序末尾。
若只用哈希表,可给每个键附带递增时间戳,查找和刷新是平均 ``O(1)``,但淘汰时必须扫描所有条目寻找最小
时间戳,耗时 ``O(capacity)``。若只用按新旧排列的普通序列,末尾淘汰很快,按键查找和把中间条目移到
最前又需要线性扫描。单一结构各自只解决了一半问题。
组合结构怎样分工
~~~~~~~~~~~~~~~~
哈希表 ``index_`` 保存 ``key -> Node*``,负责平均常数时间定位。双向链表按使用时间排列,越靠近
``mostRecentSentinel_`` 越新,越靠近 ``leastRecentSentinel_`` 越旧。已知节点地址后,双向链表能通过
``previous``、``next`` 在常数时间摘除中间节点;单链表做不到,因为它还要寻找前驱。
两个哨兵不代表缓存项,只固定边界:
.. code-block:: text
mostRecentSentinel
<-> 最近使用项 <-> ... <-> 最久未使用项
<-> leastRecentSentinel
空缓存时两个哨兵直接相连。插入首项、删除末项与处理中间节点使用完全相同的四个指针更新,不需要分别处理
空表、头节点和尾节点分支。
必须始终保持的三个不变量
~~~~~~~~~~~~~~~~~~~~~~~~
#. 每个真实缓存键在哈希表中出现一次,也在两个哨兵之间出现一次;``index_[key]`` 正好指向该链表节点;
#. ``mostRecentSentinel_->next`` 是最近成功访问的条目,``leastRecentSentinel_->previous`` 是最久未访问项;
#. 哈希表大小等于真实链表节点数,并且不超过容量(一次新插入的检查过程中可暂时多一)。
``detach`` 只接受真实节点,用两次跨接把它从当前位置删除;``insertAsMostRecent`` 把节点插到头哨兵之后。
``markAsMostRecent`` 组合两者,因此命中节点原本就在最前也无需特判:先摘除再插回,结果不变量不变。
``get`` 的分支意义
~~~~~~~~~~~~~~~~~
哈希未命中时返回 ``-1``,这次访问没有对应缓存项,不能改变新旧顺序。命中时先取得节点指针,移动到最新
位置,再返回值。移动与返回的先后在单线程结果上等价,但代码把“成功访问必刷新”集中在返回之前,不会
遗漏副作用。
对示例中的 ``get(4)``,原顺序 ``[7, 4]`` 先摘下 ``4`` 得到 ``[7]``,再插到头部得到 ``[4, 7]``;
随后淘汰依据已经正确改变。
``put`` 必须先区分覆盖与新增
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
已有键的 ``put`` 只更新现有节点的 ``value`` 并刷新位置,条目数不变,所以不能执行容量淘汰。新键才分配
节点、同时写入哈希并插到最新位置。若此时哈希大小超过容量,``leastRecentSentinel_->previous`` 就是唯一
应淘汰节点:先从链表摘除,再用节点内保存的 ``key`` 从哈希删除,最后释放节点。
删除必须同时作用于两种结构。只删哈希会让链表留下不可定位的旧节点;只删链表会让后续 ``get`` 取得悬空
或已淘汰节点。节点同时保存 ``key`` 和 ``value``,正是为了从表尾选中 victim 后能反向删除哈希项。
完整操作走读
~~~~~~~~~~~~
.. list-table::
:header-rows: 1
* - 操作
- 链表顺序(新到旧)
- 哈希变化
* - ``put(4, 40)``
- ``[4]``
- 增加 ``4 -> node4``
* - ``put(7, 70)``
- ``[7, 4]``
- 增加键 ``7``
* - ``get(4)``
- ``[4, 7]``
- 映射不变,只移动节点
* - ``put(9, 90)``
- 先 ``[9, 4, 7]``,再淘汰尾部成为 ``[9, 4]``
- 增加 ``9``,删除 ``7``
* - ``get(7)``
- ``[9, 4]``
- 未命中,不变
析构与边界状态
~~~~~~~~~~~~~~
析构函数沿 ``next`` 删除整条链,包括两个哨兵和所有尚存数据节点,防止手工 ``new`` 的内存泄漏。容量至少
为一,所以新插入后需要淘汰时,尾哨兵前必有真实节点;代码不会把哨兵当 victim。哨兵没有放入哈希,它们
的占位键值也不会与用户键冲突。
复杂度与方案选择
~~~~~~~~~~~~~~~~
哈希查找、插入和删除平均 ``O(1)``;已知节点的双向链表摘除、头插和尾部定位都是严格 ``O(1)``,所以
``get``、``put`` 均满足平均 ``O(1)``。空间为至多 ``capacity`` 个节点和哈希项,即 ``O(capacity)``。
主解采用哈希表与双向链表组合,因为它恰好覆盖三类所需操作;时间戳扫描与单序列方案只作为瓶颈推导,
没有额外认知收益值得保留第二份较长 C++ 实现。