LRU 缓存：哈希负责找，链表负责排
「最近最少使用」要求缓存能按访问时间排序，又要 O(1) 读写——哈希表定不了顺序，链表定不了位置，两者咬合才是答案。
用哈希表（key → 链表节点）做到 O(1) 定位，用双向链表记录访问顺序：头部最新、尾部最旧。get 命中把节点移到头部；put 新增插头部，容量满则删尾部。双向链表能在 O(1) 内摘除任意中间节点，这是单向链表做不到的。每次操作 O(1)，空间 O(capacity)。
设计一个 LRU（Least Recently Used，最近最少使用）缓存：get(key) 返回对应的值，put(key, value) 写入键值；两者都要 O(1)。容量满时，put 淘汰「最久未使用」的键。
这道题是设计题里的经典。它不考你背得多熟，而考你能不能把一个抽象要求（LRU）拆成两个具体职责（定位 + 排序），再找到两个数据结构各承担一半。
读完之后你会明白：为什么是「哈希表 + 双向链表」而不是别的组合——关键在那次 O(1) 的中间摘除上。
先拆需求：两个 O(1) 意味着什么
把 LRU 的语义翻译成一句话：缓存里的每个 key 都有一个「最近被访问」的时间戳，get 或 put 命中都会刷新这个时间戳；容量满时，删除时间戳最旧的 key。
于是任何一次操作都要回答两个问题：这个 key 在哪？它现在应该排到多前？
第一个问题指向「按 key 定位」——哈希表是天然的答案，O(1)。第二个问题指向「按时间排序」——数组排序做不到 O(1) 更新，链表可以。
所以设计的主线是：两个数据结构，各管一个问题。剩下的难点只有一个——链表怎么在 O(1) 内把任意一个节点移到头部。
为什么是双向链表，不是单向
假设链表按「最近使用」排序，头是最新、尾最旧。get(2) 命中后，节点 2 不在头部，要把它移到头部。
单向链表只能从 head 向后找节点 2 的前驱——那是 O(n)。双向链表每个节点记得 prev 和 next，摘除自己只需要两次指针改写：prev.next = next、next.prev = prev。
这就是「双向」的全部意义：它让「从链表中间摘掉一个节点」变成 O(1)，而不是 O(n)。
记住这句话：哈希表把「找到节点」从 O(n) 变 O(1)，双向链表把「摘除节点」从 O(n) 变 O(1)。两个 O(1) 拼起来，整个操作才是 O(1)。
职责哈希表负责「找」，链表负责「排」。单向链表只会排，不会在 O(1) 里挪人。
·
·
·
完整跑一遍操作序列
用深度资产里的标准序列验证模型：put(1,1)、put(2,2)、get(1)、put(3,3)、get(2)，容量 2。
put(1,1)：空缓存，插入 1，头部 = 1。put(2,2)：插入 2 到头部，链表 2 → 1。
get(1)：命中，把 1 移到头部，链表 1 → 2——注意 1 变最新，2 变最旧。
put(3,3)：插入 3 到头部，链表 3 → 1 → 2，容量满（2），删除尾部 2。链表 3 → 1。
get(2)：缓存里已经没有 2，返回 -1。
请特别观察：get(1) 之后，最旧的 key 从 1 变成了 2——如果漏掉「命中要移到头部」这一步，下一次淘汰就会删错对象。
·
一个隐藏的坑：更新值也要动链表
很多第一次写的实现，put 命中已存在的 key 时只更新 value 就返回了——链表顺序不动。这看起来省了一步，其实是错的。
因为 put 命中同样是一次「使用」，会刷新该 key 的最近访问时间。如果链表顺序不动，它留在旧位置，可能被误判为「最久未使用」而提前淘汰。
正确做法：put 命中 = 更新 value + moveToHead，与 get 命中完全同构。
拿这个反例验证：容量 2，put(1,1)、put(2,2)、put(1,3)（更新 1）、put(3,3)。如果更新 1 时不移到头部，链表是 2 → 1，put(3) 会删最旧的 2——对。但如果先 put(2,2) 再 put(1,1) 再 put(2,9)，链表是 1 → 2，漏移动的话 put(3,3) 会删 2，而 2 明明刚被更新过，应该删 1。
反例「命中即使用」是 LRU 的定义。get 和 put 命中都必须刷新最近访问时间，漏掉就是 bug。
·
·
边界条件
容量为 0：任何 put 都不能存，get 永远返回 -1。实现里可以在 put 开头直接 return，或初始化时不建缓存。
空缓存 get：返回 -1。
get 不存在的 key：返回 -1，且不改变链表顺序。
重复 put 相同 key：这是上一节的坑，必须更新值并移到头部。
容量满时 put 新 key：先删尾部，再插头部。注意「先删后插」的顺序——如果先插导致 size > cap，再删，逻辑也成立，但要注意删的是最旧的那个。
面试表达先讲「命中即刷新」这个定义，再讲双向链表 O(1) 摘除，最后主动补一句容量 0 的边界——会显得考虑周全。
回到模型：为什么这样就够 O(1)
把时间账算清楚。get 命中：哈希查 O(1)，链表摘除 O(1)（双向指针），头部插入 O(1)。put 新增：哈希插 O(1)，头部插入 O(1)，必要时尾部删除 O(1)。
整条链路上没有一处是 O(n)——这就是「哈希表 + 双向链表」组合的成立条件。换成单向链表，get 命中变 O(n)；换成数组，移动元素变 O(n)。
这个「一个管定位、一个管排序」的模板不止 LRU 能用。LFU（最不经常使用）在 LRU 之上再加一层频率桶；O(1) 随机删除的数组哈希组合也是同一种思路：让两个数据结构各提供对方缺失的能力。
Go：哈希表 + 双向链表
type Node struct {key, value intprev, next *Node}type LRUCache struct {cap intcache map[int]*Nodehead, tail *Node}func (c *LRUCache) Get(key int) int {node, ok := c.cache[key]if !ok { return -1 }c.moveToHead(node)return node.value}func (c *LRUCache) Put(key, value int) {if node, ok := c.cache[key]; ok {node.value = valuec.moveToHead(node)return}node := &Node{key: key, value: value}c.cache[key] = nodec.addToHead(node)if len(c.cache) > c.cap {removed := c.removeTail()delete(c.cache, removed.key)}}func (c *LRUCache) remove(node *Node) {node.prev.next = node.nextnode.next.prev = node.prev}func (c *LRUCache) addToHead(node *Node) {node.next = c.head.nextnode.prev = c.headc.head.next.prev = nodec.head.next = node}func (c *LRUCache) moveToHead(node *Node) { c.remove(node); c.addToHead(node) }func (c *LRUCache) removeTail() *Node {node := c.tail.prevc.remove(node)return node}
1链表节点带 key 和 prev/next 双向指针。
2缓存结构：哈希表 + 双向链表的哨兵头尾。
3get 命中：移到头部再返回；未命中返回 -1。
4put 命中：更新值也必须 moveToHead——命中即使用。
5put 新增：先插入头部再检查容量。
6容量超了：删尾部最旧的节点，并从哈希表清除。
7摘除任意节点只要两次指针改写，O(1)。
8插到头部：连在 head 之后。
9moveToHead = remove + addToHead。
10removeTail 删除尾哨兵的前驱。
总结
LRU = 哈希表 O(1) 定位 + 双向链表 O(1) 调整顺序；命中必须刷新。
- 哈希表解决「在哪」，双向链表解决「排第几」——两个 O(1) 拼出整体 O(1)。
- 双向链表的全部价值：O(1) 摘除中间节点，单向链表做不到。
- get/put 命中都要 moveToHead；漏掉就是淘汰错对象的 bug。
- 容量 0、空缓存、不存在的 key：都返回 -1 且不动链表。