LRU 缓存为什么常用哈希表加双向链表实现？

简化版

LRU 需要 O(1) 查找、O(1) 删除任意节点、O(1) 移到最近使用位置。哈希表负责通过 key 找到节点，双向链表负责维护访问顺序；访问或更新就把节点移到头部，容量满了淘汰尾部节点。

详细版

单靠数组或单链表很难同时做到 O(1)。哈希表能 O(1) 找到 key 对应节点，但不能维护最近使用顺序；双向链表能 O(1) 删除已知节点并移动到头部，也能 O(1) 删除尾部最久未使用节点。

hash: key -> node
list: head <-> recent ... old <-> tail

面试要强调双向链表的价值：已知节点时，可以通过 prev 和 next 在 O(1) 时间把它摘掉；单链表没有前驱，删除任意节点不方便。

完整版教学

一、LRU 要维护最近使用顺序

LRU 是 Least Recently Used，淘汰最久没有被访问的数据。缓存容量固定时，每次 get 或 put 都会改变某个 key 的“最近使用”状态。

目标操作：

get(key): 查到后变成最近使用
put(key,value): 新增或更新后变成最近使用
evict: 容量满时删除最久未使用

如果这些操作不能做到 O(1)，缓存高频访问时就会成为瓶颈。

记忆钩子：哈希表管找到，双向链表管顺序。

二、哈希表解决 O(1) 查找

通过哈希表，可以从 key 快速找到节点。

map["A"] -> nodeA
map["B"] -> nodeB

如果没有哈希表，只靠链表查 key，需要从头扫到尾，时间 O(n)。缓存每次 get 都 O(n)，容量一大就不可接受。

但哈希表本身没有“谁最近、谁最旧”的顺序信息，所以还需要链表。

三、双向链表维护使用顺序

常见约定是头部表示最近使用，尾部表示最久未使用。

head <-> A <-> C <-> B <-> tail
recent              old

访问 B 后，要把 B 移到头部：

head <-> B <-> A <-> C <-> tail

容量满时，淘汰 tail.prev，也就是最久未使用节点。这个操作 O(1)。

四、为什么必须是双向链表

如果哈希表给你 nodeB，想从链表里删除 B：

A <-> B <-> C

双向链表可以直接：

B.prev.next = B.next;
B.next.prev = B.prev;

单链表节点没有 prev。即使你拿到了 B，也不知道 A 是谁，删除 B 仍然麻烦。除非哈希表存前驱，但移动节点后前驱会频繁变化，维护复杂。

这就是 LRU 高频追问“为什么不是单链表”的答案。

五、dummy head 和 dummy tail 简化边界

LRU 实现常用虚拟头尾节点。

head <-> real nodes <-> tail

插入到头部：

node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;

删除节点：

node.prev.next = node.next;
node.next.prev = node.prev;

有 dummy 后，空链表、只有一个节点、删除尾部真实节点都不需要特殊分支。

六、get 和 put 的完整逻辑

get(key)：

1. map 查不到 -> 返回 -1
2. map 查到 node -> 从链表摘除 node
3. node 插到头部
4. 返回 node.value

put(key,value)：

1. key 已存在 -> 更新 value，移动到头部
2. key 不存在 -> 新建节点，插到头部，放入 map
3. 如果 size > capacity -> 删除 tail.prev，并从 map 删除 key

所有步骤都能做到 O(1)，前提是哈希表和双向链表配合。

七、常见误区与追问

误区：哈希表一个结构就能实现 LRU。 哈希表能查找，但不能维护最近使用顺序和 O(1) 淘汰最旧。
误区：单链表也一样方便。 单链表删除已知节点缺少前驱，移动任意节点到头部不够方便。
误区：只有 put 才算使用。 LRU 中 get 命中也要刷新最近使用状态。
追问：为什么要 dummy head/tail？ 统一插入删除边界，避免空链表和首尾节点特殊处理。
追问：容量满淘汰谁？ 淘汰尾部真实节点，也就是 tail.prev。
追问：时间复杂度为什么是 O(1)？ map O(1) 定位节点，双向链表 O(1) 摘除和头插。

八、加强记忆

LRU 结构记成“map 找人，双链排队”。哈希表让 key 到节点 O(1)，双向链表让已知节点 O(1) 删除、O(1) 移到头部、O(1) 淘汰尾部。get 命中和 put 更新都要刷新最近使用，容量满删 tail.prev，dummy 头尾负责把边界处理变简单。

简化版

详细版