LC146
LC146 LRU 缓存：为什么 get(1) 之后，put(3,3) 淘汰的是 2？
HashMap 负责找到节点，双向链表负责重排顺序。这一页只讲清楚一件事：map 和链表如何同步变化。
·
对照错误模式：get 只返回值不 moveToHead → 更像 FIFO
实验剧本：put(1,1) → put(2,2) → get(1) → put(3,3) → get(2) · capacity=2
初始化 · dummy HEAD / TAIL1/26
操作流
put(1,1)
→
put(2,2)
→
get(1)
→
put(3,3)
→
get(2)
执行实验台
size: 0 / 2
← MRU sideLRU side →
HEAD
TAIL
HashMap · key → node
| key | points to |
|---|---|
| {} | |
map 存的是 node 引用，所以能 O(1) 找到链表里的真实节点。
访问 · —
map · cache = {}
链表 · HEAD ⇄ TAIL
当前代码行
初始化 · dummy HEAD / TAIL
哨兵头尾让插入、删除不需要 nil 判断。链表为空，map 为空。
head.next = tailtail.prev = headcache = make(map[int]*Node)
初始化只做常数次指针赋值。
不变量检查
- ✅head.next 是 MRU
- ✅tail.prev 是 LRU
- ✅map 中每个 key 都指向链表中的真实节点
- ✅链表中的每个真实节点都能在 map 中找到
- ✅size <= capacity (0 / 2)
逐帧 · 26 步