登录
LRU 缓存实现详解：双向链表 + 哈希表
LRU 缓存实现详解：双向链表 + 哈希表
摘要：本文深入剖析使用“双向链表 + 哈希表”实现 LRU（Least Recently Used）缓存的标准方法。从核心思想到代码实现，再到边界处理与复杂度分析，完整展示一个 O(1) 时间复杂度的 LRU 缓存如何工作。
1. 概述
LRU（最近最少使用）是一种常见的缓存淘汰策略：当缓存容量达到上限时，优先淘汰最长时间未被访问的数据。每次访问（读或写）都会将对应数据标记为“最近使用”。
为了支持 get 和 put 操作均为 O(1) 时间复杂度，必须同时满足：
- 快速查找：给定 key，能在 O(1) 时间内找到对应的数据。
- 快速维护顺序：能够 O(1) 地将任意数据移动到“最近使用”的位置，并且 O(1) 删除“最久未使用”的数据。
数据结构组合：哈希表 + 双向链表 完美达成上述要求。
为什么不能用数组或单向链表？
- 数组移动元素 O(N)
- 单向链表删除尾部需要遍历到前驱 O(N)
- 双向链表 + 哈希表完美 O(1)
2. 核心数据结构
2.1 双向链表节点
每个节点存储键、值以及前驱和后继指针。其中存储 key 是为了在淘汰节点时能从哈希表中删除对应的键。
class ListNode {
constructor(key, value) {
this.key = key; // 存储 key 是为了淘汰时能从哈希表删除
this.value = value;
this.prev = null; // 前驱指针
this.next = null; // 后继指针
}
}
2.2 LRU 缓存类成员
class LRUCache {
constructor(capacity) {
this.capacity = capacity; // 最大容量
this.size = 0; // 当前存储的节点数
this.map = new Map(); // 哈希表：key -> 节点引用
// 虚拟头尾节点（哨兵），简化边界操作
this.head = new ListNode(0, 0);
this.tail = new ListNode(0, 0);
this.head.next = this.tail;
this.tail.prev = this.head;
}
}
为什么使用虚拟头尾？
- 避免对空指针的判断（如
if (node.prev) ...） - 插入头部时，
head.next一定存在；删除尾部时，tail.prev一定存在 - 统一代码逻辑，减少边界错误
2.3 链表状态示意图
初始状态：
head <-> tail
插入一个有效节点后：
head <-> node1 <-> tail
多个节点按最近使用顺序排列：头部是最近使用的，尾部是最久未使用的。
3. 辅助方法（链表操作）
所有辅助方法的时间复杂度均为 O(1)。
3.1 _addToHead(node)：在头部插入节点
_addToHead(node) {
node.prev = this.head;
node.next = this.head.next;
this.head.next.prev = node;
this.head.next = node;
}
执行步骤（假设当前 head <-> A <-> ...）：
node.prev = this.head-
node.next = this.head.next（即 A） -
this.head.next.prev = node（A 的前驱指向 node） -
this.head.next = node（head 的后继指向 node）
结果：head <-> node <-> A <-> ...
3.2 _removeNode(node)：删除任意节点
_removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
原理：让 node 的前驱直接指向 node 的后继，node 的后继直接指向 node 的前驱，从而将 node 从链表中移除。node 自身的指针无需修改（因为节点即将被丢弃或移动）。
3.3 _moveToHead(node)：将已有节点移到头部
_moveToHead(node) {
this._removeNode(node);
this._addToHead(node);
}
先删除，再插入头部，使该节点成为“最近使用”节点。
3.4 _removeTail()：删除尾部真实节点（最久未使用）
_removeTail() {
const tailNode = this.tail.prev; // 虚拟 tail 的前一个才是真正的尾节点
this._removeNode(tailNode);
return tailNode;
}
返回被删除的节点，以便从哈希表中删除其键。
4. 主要操作实现
4.1 get(key)
get(key) {
if (!this.map.has(key)) return -1;
const node = this.map.get(key);
this._moveToHead(node); // 标记为最近使用
return node.value;
}
流程：
- 哈希表查找 → O(1)
- 不存在则返回 -1
- 存在则移动节点到链表头部 → O(1)
- 返回节点值
4.2 put(key, value)
put(key, value) {
if (this.map.has(key)) {
// 情况1：key 已存在 → 更新值并移到头部
const node = this.map.get(key);
node.value = value;
this._moveToHead(node);
} else {
// 情况2：key 不存在 → 创建新节点
const newNode = new ListNode(key, value);
this.map.set(key, newNode);
this._addToHead(newNode);
this.size++;
if (this.size > this.capacity) {
// 淘汰最久未使用的节点
const removed = this._removeTail();
this.map.delete(removed.key);
this.size--;
}
}
}
情况2详细步骤：
- 创建新节点，存入哈希表
- 插入链表头部（成为最近使用）
- 缓存大小 +1
- 若超过容量：删除尾部真实节点，并从哈希表中删除其键，大小 -1
注意：先插入新节点，再淘汰旧节点，确保淘汰的一定是最久未使用的。
5. 完整代码
class ListNode {
constructor(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.size = 0;
this.map = new Map();
this.head = new ListNode(0, 0);
this.tail = new ListNode(0, 0);
this.head.next = this.tail;
this.tail.prev = this.head;
}
_addToHead(node) {
node.prev = this.head;
node.next = this.head.next;
this.head.next.prev = node;
this.head.next = node;
}
_removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
_moveToHead(node) {
this._removeNode(node);
this._addToHead(node);
}
_removeTail() {
const tailNode = this.tail.prev;
this._removeNode(tailNode);
return tailNode;
}
get(key) {
if (!this.map.has(key)) return -1;
const node = this.map.get(key);
this._moveToHead(node);
return node.value;
}
put(key, value) {
if (this.map.has(key)) {
const node = this.map.get(key);
node.value = value;
this._moveToHead(node);
} else {
const newNode = new ListNode(key, value);
this.map.set(key, newNode);
this._addToHead(newNode);
this.size++;
if (this.size > this.capacity) {
const removed = this._removeTail();
this.map.delete(removed.key);
this.size--;
}
}
}
}
6. 执行示例
假设 capacity = 2：
| 操作 | 链表状态（头部最近） | 哈希表内容 | 说明 |
|---|---|---|---|
put(1, 1) |
head <-> 1 <-> tail |
{1→node1} |
插入节点1 |
put(2, 2) |
head <-> 2 <-> 1 <-> tail |
{1→node1, 2→node2} |
插入节点2，成为最近使用 |
get(1) |
head <-> 1 <-> 2 <-> tail |
{1→node1, 2→node2} |
访问1，1移到头部 |
put(3, 3) |
head <-> 3 <-> 1 <-> tail |
{1→node1, 3→node3} |
容量满，淘汰尾部的2 |
get(2) |
不变 | 不变 | 返回 -1 |
7. 边界情况处理
| 情况 | 处理方式 |
|---|---|
capacity ≤ 0 |
通常题目保证 capacity ≥ 1；若需处理，可在构造时抛出错误或使所有 put 无效 |
get 不存在的 key |
返回 -1
|
put 更新已存在的 key |
更新 value，移到头部，不改变 size
|
put 时容量已满 |
先插入新节点，再淘汰尾部节点（确保淘汰的是最久未使用的） |
| 链表中只有一个有效节点 | 虚拟头尾仍然存在，所有辅助方法正常工作 |
重复 put 同一 key 且值不变 |
依然执行 _moveToHead，更新使用顺序 |
8. 复杂度分析
-
时间复杂度：
-
get：O(1)（哈希查找 + 链表移动） -
put：O(1)（哈希查找/插入 + 链表操作） - 所有辅助方法均为 O(1)
-
-
空间复杂度：
- O(capacity)，哈希表存储最多 capacity 个节点，链表同样存储 capacity 个节点。
9. 与“纯 Map”实现的对比
| 维度 | 双向链表 + 哈希表 | 纯 Map 版本（依赖插入顺序） |
|---|---|---|
| 实现原理 | 手动维护链表顺序，完全可控 | 利用 Map 的键顺序特性 |
| 代码复杂度 | 较高（约60行） | 极低（约20行） |
| 时间复杂度 | 严格 O(1) | 也是 O(1)，但淘汰时需获取迭代器 |
| 空间开销 | 每个节点额外存储两个指针 | 无额外指针 |
| 可移植性 | 任何支持哈希表和指针的语言均可实现 | 依赖特定语言特性（如 JavaScript 的 Map 顺序） |
结论：虽然纯 Map 版本更简洁，但双向链表 + 哈希表是标准、通用的实现，更能体现 LRU 的核心思想。
10. 常见问题
Q1：为什么必须用双向链表？单向链表不行吗？
A：单向链表删除一个节点时，如果只有该节点的引用，无法 O(1) 获得它的前驱。双向链表可以通过 node.prev 直接修改前驱的 next 指针，实现 O(1) 删除。
Q2：节点中为什么要存储 key？
A：淘汰尾部节点时，需要通过 removed.key 从哈希表中删除对应的键。如果节点不存 key，则无法知道删除哈希表中的哪个条目。
Q3：虚拟头尾节点占用额外空间，会影响容量计算吗？
A：不影响。size 只统计实际存储的数据节点，虚拟节点不计入容量。
Q4：如果 capacity = 0 怎么办？
A：可以规定构造时抛出异常，或者在 put 方法中直接返回（不存储任何数据）。实际工程中通常不会允许容量为0的缓存。
Q5：能否用其他数据结构代替双向链表？
A：可以使用有序字典（如 Python 的 OrderedDict 或 Java 的 LinkedHashMap），但这些本质上也是哈希表+双向链表的封装。手写双向链表更能理解底层机制。
11. 总结
- LRU 缓存的核心是 哈希表 提供 O(1) 查找，双向链表 提供 O(1) 顺序维护。
- 虚拟头尾节点极大简化了链表边界操作。
- 所有操作（
get/put）时间复杂度 O(1)，空间复杂度 O(capacity)。 - 该实现不依赖特定语言特性，具有很好的可移植性和教学意义。
