LRU 缓存（LeetCode #146）
LRU 缓存保留最近访问的键值对，容量不足时淘汰最久未用的条目。难点是每次 get、put 后既保持快速定位，又维护访问顺序，不能靠扫描缓存完成。
可以把条目看成一排卡片：左侧最近使用，右侧最久未用。已拿到某张卡时，移到前面不难；按键寻找它则需要另一种索引。Python 的 functools.lru_cache、Redis 的近似 allkeys-lru、操作系统的 LRU 类页面置换，都使用近期访问的思想，具体机制不必相同。
LRU 缓存如何工作
哈希表与双向链表分工
哈希表把键映射到链表节点，期望 O(1) 定位。双向链表保存新旧顺序，已知节点后，用常数次指针改写完成移除和头插。
哈希表回答“键在哪里”，链表回答“谁最新、谁最旧”。两者必须描述同一批存活条目：链中节点的键都在表中，表指向的节点也都在链中。
访问顺序链
从最近使用 MRU 排到最久未用 LRU，两侧各放一个不存真实条目的哨兵：
HEAD ↔ MRU ↔ ... ↔ LRU ↔ TAIL
头插总在 HEAD 与 HEAD.next 之间，淘汰总选 TAIL.prev。哨兵让空表和单节点也可采用同样的内部连接规则。
移除节点时，先保存 before = node.prev、after = node.next，再写 before.next = after、after.prev = before。
插入头部时，把节点放在 HEAD 与当前首节点（缓存为空时是 TAIL）之间，先更新新节点两条链接，再更新 HEAD.next 和该首节点的 prev。
动画把写入分开显示。节点可能暂时脱链，但哈希表仍指向它；也可能先入链、后写表。这些是操作内部状态，每个公开操作完成时必须恢复两者一致。
逐步演示
get 的行为
get(key) 先查表。缺失返回 -1，不移动任何节点，因为没有访问到缓存条目。
命中则取节点、保存值、脱链、移到 HEAD 后，再返回值。读操作也会更新近期顺序。若已是 MRU，可跳过指针改写，但完成后该键必须仍位于最前。
put 的行为
已有键时，修改原节点的值，把同一节点移到头部，不分配副本，也不增加大小。
新键则创建节点、头插、写入 key → node。表大小超过 capacity 时，找到 TAIL.prev，从链表和哈希表同时移除它。
只删链节点会留下过期映射；只删表项会留下无法按键找到、却占据链空间的节点。两项移除组成一次逻辑淘汰。
默认序列
容量为 3，依次运行：
put(1, 10), put(2, 20), put(3, 30), get(1), put(4, 40)
前三次 put 后顺序为 3, 2, 1，3 最近，1 最旧。
get(1) 返回 10，把 1 移到头部，顺序变为 1, 3, 2。键集合不变，但下次淘汰对象已改变。
put(4, 40) 先得到 4, 1, 3, 2，大小 4 超出容量。TAIL.prev 指向键 2，删除其节点和表项，最终为 4, 1, 3。
如果没有中间那次成功的 get(1)，键 1 仍最旧，最后会淘汰 1。读取是替换策略的一部分。
时间与空间复杂度
| 操作 | 期望时间 | 原因 |
|---|---|---|
get | O(1) | 哈希查询与常数次指针写入 |
put 已有键 | O(1) | 定位、改值、移动一次 |
put 新键 | O(1) | 插入一次，至多淘汰一次 |
| 空间 | O(capacity) | 每条目一个表项和一个节点 |
哈希查询采用期望 O(1) 模型；链表部分不按位置遍历，本身是最坏 O(1)。
边界情况
- 容量 1：首次插入之后，每个新键替换唯一的旧键，哨兵使连接逻辑不变。
- get 缺失：返回
-1，顺序不变。 - 更新已有键：覆盖值并移到 MRU，大小不变。
- get 当前 MRU：返回值，显示顺序不变。
- 更新必须复用节点：创建副本可能让表指向一份，链中又留一份。
常见错误
- 把 get 当只读。 成功命中的键要成为 MRU。
- 淘汰头部。 本课头部最新，尾部最旧，应选
TAIL.prev。 - 未保存邻居就改指针。 改线前保存所需引用，公开操作结束时同步哈希表与链表。
哨兵只减少分支，不能替代核心不变量：表定位节点，链给同一批节点排序。