LRU 缓存动画演示
哈希表定位、双向链表排序，命中就搬到最前面。
键盘：← → 单步 ·空格 播放/暂停 · R 重置 ·Home/End 到两端
LRU 要把两件事同时做到常数时间：给定 key 立刻找到它的节点，以及随时问出「谁最久没被用过」。前者只有哈希表能给，后者只有链表能给，所以这页画的是两个结构一起动：上面那排格子是双向链表，左边是最近使用、右边是最久未用，尾巴那一格就是每次要淘汰的对象；中间那张表是哈希索引，行首是 key，另外三列写它此刻挂在链表第几个、值是多少、这一次做了什么。
一次命中的 get 会拆成三幕来看：查哈希定位节点、把节点从原来的位置摘出来、再插回链表头。摘与插之间链表真的少一个节点，这不是画错，是在告诉你双向链表做删除只改前后指针，不需要把后面的元素整体搬一遍。底下那排格子是操作序列，走到哪一格舞台就在处理哪一次调用，命中、未命中、淘汰、改值四种情况各有各的走法。
LRU 缓存演示怎么用
- 看两个结构对齐：哈希表的行号必须和上面链表的格子序号一致；每次搬动节点后这张表会整张重算，对不上就说明漏删了一行。
- 改容量：容量调到 1、2 会看到淘汰发生得频繁得多，同一段操作序列的命中数会明显掉下来，这是估缓存命中率的直观练习。
- 自己写操作：操作序列用 get a 与 put b 5 两种写法，逗号或分隔号隔开，最多取前 14 条；非法条目会被跳过。
- 数四个计数：命中、未命中、淘汰、更新已有各计各的。淘汰次数等于「容量满时又放进来的新 key」次数，和命中次数没有必然关系。
常见问题
为什么必须哈希表加双向链表，只用一个不行吗？
只用哈希表，O(1) 找到节点，但谁最久没用问不出来——除非每次淘汰都扫一遍全表。只用链表，顺序天然有，但按 key 查找要 O(n)。两个结构各出一半力：哈希表存 key 到节点的指针，链表维持访问顺序，于是 get、put 都只动常数量级个指针。只用一个，复杂度立刻退化到 O(n)。
要双向链表做什么，单向链表不行吗？
命中时要把节点从链表中间摘走。单向链表只知道自己的 next，不知道前驱，摘它得先从表头再走一遍找前驱，O(n) 就回来了。双向链表里节点自己握着 prev，摘它只是 prev.next = next、next.prev = prev 两次赋值。表头表尾再各挂一个哑节点，就省掉了空表和单节点的特判。
get 未命中要不要把这次算成一次使用？
不算。约定是未命中返回哨兵值（-1 或空），链表一动不动。把它当成使用会污染顺序，把 miss 当成 put 更是凭空造了一个 key，两种写法在下一轮淘汰时给出的都是错答案。put 更新已有 key 则要搬到表头——写下去就算最近用过一次。
用 Map 就能写出 LRU，还需要链表吗？
语言自带的有序字典确实能省掉手写链表：命中的做法是删掉再插回去，遍历顺序就是访问顺序。但这只是把链表藏进了 Map 的实现里，语义一个不少——「删了再插」正是「搬到表头」。要真 O(1) 且淘汰尾部，你还是得能常数拿到第一个键，并且能在常数时间删掉任意键，这两个能力就是链表节点。