LRU 缓存 - HashMap + 双向链表完全指南

LRU（最近最少使用）缓存是顶级科技公司面试中最常被问到的问题之一。它考察你对数据结构设计和实际系统组件的理解。

为什么面试官喜欢这道题

1. 考察数据结构设计 - 你必须组合多种数据结构来实现 O(1) 操作
2. 具有实际意义 - LRU 缓存无处不在：浏览器、数据库、CDN、操作系统
3. 考察权衡思维 - 为什么不只用 HashMap？为什么需要链表？
4. 有很多追问 - 线程安全、分布式缓存、TTL 过期等

核心思路：HashMap + 双向链表

难点在于实现 get 和 put 操作都是 O(1) 时间，同时还要跟踪访问顺序。

┌─────────────────────────────────────────────────────────────┐
│                        HashMap                              │
│    key → Node 指针（O(1) 查找）                               │
│                                                             │
│    ┌───┐  ┌───┐  ┌───┐  ┌───┐                               │
│    │ 1 │  │ 2 │  │ 3 │  │ 4 │                               │
│    └─┬─┘  └─┬─┘  └─┬─┘  └─┬─┘                               │
│      │      │      │      │                                 │
│      ▼      ▼      ▼      ▼                                 │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │              双向链表                                    │ │
│ │  HEAD ⟷ [1:A] ⟷ [2:B] ⟷ [3:C] ⟷ [4:D] ⟷ TAIL           │ │
│ │   ↑                                  ↑                  │ │
│ │  MRU                                LRU                 │ │
│ │  (最近使用)                        (最久未使用)           │ │
│ └─────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────┘

关键洞察：

• HashMap → O(1) 按 key 查找
• 双向链表 → O(1) 删除和插入（当我们有节点指针时）

访问一个元素时，我们把它移到头部。需要淘汰时，我们从尾部删除。

---

交互式可视化

观察 LRU 缓存如何处理一系列 get 和 put 操作。注意元素被访问时如何移动到头部：

Initializing...

---

问题：LRU 缓存 (LC 146)

问题：设计一个遵循 LRU（最近最少使用）缓存约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) - 以正整数容量初始化
• int get(int key) - 如果存在返回值，否则返回 -1
• void put(int key, int value) - 更新或插入。如果容量超限，淘汰最近最少使用的元素。

两个操作都必须在 O(1) 平均时间内完成。

算法步骤

1. 初始化：创建 HashMap 和带有哨兵头尾节点的双向链表
2. get(key)：
   • 如果 key 不在 HashMap 中 → 返回 -1
   • 否则 → 将节点移到头部，返回值
3. put(key, value)：
   • 如果 key 存在 → 更新值，移到头部
   • 如果 key 不存在：
     • 如果已满 → 删除 LRU（tail.prev），从 HashMap 中删除
     • 创建新节点 → 插入头部，添加到 HashMap

---

代码模板：HashMap + 双向链表

JavaPythonJavaScript

Loading...

---

替代方案：使用内置有序集合

大多数语言都有有序数据结构可以简化实现：

JavaPythonJavaScript

Loading...

⚠️ 面试警告：很多面试官希望你使用 HashMap + 双向链表从头实现，而不是使用内置解决方案。一定要先问清楚！

---

完整示例演示

让我们追踪：LRUCache(2)，然后 put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4)

步骤 1: LRUCache(2)
缓存: 空  |  HashMap: {}

步骤 2: put(1, 1)
缓存: [1:1]  |  HashMap: {1→node}
       ↑
      MRU

步骤 3: put(2, 2)
缓存: [2:2] ⟷ [1:1]  |  HashMap: {1→node, 2→node}
       ↑        ↑
      MRU      LRU

步骤 4: get(1) → 返回 1
缓存: [1:1] ⟷ [2:2]  |  把 1 移到头部！
       ↑        ↑
      MRU      LRU

步骤 5: put(3, 3) → 淘汰 LRU（key 2）！
缓存: [3:3] ⟷ [1:1]  |  HashMap: {1→node, 3→node}
       ↑        ↑
      MRU      LRU       ❌ key 2 被淘汰

步骤 6: get(2) → 返回 -1（已被淘汰！）

步骤 7: put(4, 4) → 淘汰 LRU（key 1）！
缓存: [4:4] ⟷ [3:3]  |  HashMap: {3→node, 4→node}
                         ❌ key 1 被淘汰

步骤 8: get(1) → 返回 -1（已被淘汰！）

步骤 9: get(3) → 返回 3
缓存: [3:3] ⟷ [4:4]  |  把 3 移到头部！

步骤 10: get(4) → 返回 4
缓存: [4:4] ⟷ [3:3]  |  把 4 移到头部！

---

时间和空间复杂度

操作	时间	空间
get(key)	O(1)	-
put(key, value)	O(1)	-
总体空间	-	O(capacity)

为什么是 O(1)？

• HashMap 提供 O(1) 查找
• 双向链表在有节点指针时提供 O(1) 插入/删除
• 我们总是能从 HashMap 获取节点指针！

---

关键要点和常见错误

1. 哨兵头尾节点

为什么使用哨兵节点？

不使用哨兵节点：
- 删除前必须检查节点是否是头
- 删除前必须检查节点是否是尾
- 到处都是边界情况！

使用哨兵节点：
- 统一的删除/插入逻辑
- 没有边界情况！

常见错误：忘记初始化 head.next = tail 和 tail.prev = head。

2. 在节点中存储 Key

为什么要在节点中存储 key？

淘汰 LRU 节点时，我们也需要从 HashMap 中删除它。但我们只有节点引用！如果不在节点中存储 key，就无法从 HashMap 中删除。

// 错误 - 无法从 HashMap 删除
Node lru = tail.prev;
remove(lru);
// map.remove(???) - 我们不知道 key 是什么！

// 正确 - key 存储在节点中
Node lru = tail.prev;
remove(lru);
map.remove(lru.key); // ✓

3. 更新 vs 插入的顺序

常见错误：更新已存在的 key 时忘记将节点移到头部。

// 错误
public void put(int key, int value) {
    if (map.containsKey(key)) {
        map.get(key).val = value; // 只更新了值，没有移动！
    }
    // ...
}

// 正确
public void put(int key, int value) {
    if (map.containsKey(key)) {
        Node node = map.get(key);
        node.val = value;
        remove(node);       // 从当前位置删除
        insertFront(node);  // 移到头部！
    }
    // ...
}

4. 淘汰检查时机

常见错误：在检查 key 是否存在之前就淘汰。

// 错误 - 可能在只是更新时也淘汰
public void put(int key, int value) {
    if (map.size() == capacity) {
        evict(); // 错误！key 可能已经存在
    }
    // ...
}

// 正确 - 先检查是否存在
public void put(int key, int value) {
    if (map.containsKey(key)) {
        // 更新已存在的 - 不需要淘汰
    } else {
        if (map.size() == capacity) {
            evict(); // 只在添加新 key 时淘汰
        }
    }
}

5. 指针更新顺序

常见错误：以错误的顺序更新指针，破坏链表。

// 错误 - 破坏了链表！
private void insertFront(Node node) {
    head.next = node;        // 丢失了对旧 head.next 的引用！
    node.prev = head;
    node.next = head.next;   // 这现在是 node 自己了！
    head.next.prev = node;
}

// 正确 - 先保存引用
private void insertFront(Node node) {
    node.next = head.next;   // 1. 指向旧的第一个节点
    node.prev = head;        // 2. 指回 head
    head.next.prev = node;   // 3. 旧的第一个节点指回新节点
    head.next = node;        // 4. head 指向新节点
}

---

面试追问

1. 线程安全

问：如何使它线程安全？

答：

• 简单方案：对所有方法使用 synchronized 或 ReentrantLock
• 更好方案：读写锁（允许并发读）
• 最佳方案：并发数据结构 + 精细锁控制

class ThreadSafeLRUCache {
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
    
    public int get(int key) {
        lock.writeLock().lock(); // 需要写锁因为我们要修改顺序
        try {
            // ... get 逻辑
        } finally {
            lock.writeLock().unlock();
        }
    }
}

2. TTL（存活时间）过期

问：如何为条目添加过期功能？

答：在每个节点中存储时间戳。访问时检查并懒惰淘汰，或使用后台线程。

3. 分布式 LRU 缓存

问：如何扩展到多台服务器？

答：

• 一致性哈希分发 key
• 每台服务器运行自己的 LRU 缓存
• 考虑跨节点的缓存失效

---

什么时候不用 LRU

场景	更好的替代方案
频率比时效性更重要	LFU（最不常使用）
需要可预测的淘汰顺序	FIFO
随机访问模式	ARC（自适应替换缓存）
非常大的缓存	近似 LRU（采样）

---

相关题目

问题	描述	链接
LFU 缓存	淘汰最不常使用的	LC 460 🔒 - 教程
设计推特	使用缓存概念	LC 355
基于时间的键值存储	带时间戳的键值	LC 981
全 O(1) 的数据结构	跟踪最大最小 key	LC 432

---

总结

核心要点

1. 数据结构组合：HashMap + 双向链表 = 一切都是 O(1)
2. 哨兵节点：大大简化边界情况
3. 节点中存储 Key：淘汰清理时必需
4. 移到头部：任何访问都使元素成为最近使用
5. 从尾部淘汰：Tail.prev 始终是 LRU 元素

需要记住的模式

LRU 缓存 = HashMap<Key, Node> + 双向链表<Node>

get(key):
  1. HashMap 查找 → O(1)
  2. 将节点移到头部 → O(1)
  
put(key, value):
  1. 如果存在：更新 + 移到头部
  2. 如果新建：
     - 如果已满：淘汰 tail.prev
     - 插入头部

这个模式是许多系统设计和数据结构问题的基础！