LFU 缓存 - 完全指南（含交互式可视化及 LRU 对比）

LFU（最不经常使用）缓存是一种高级缓存策略，它会跟踪每个元素的访问频率。与基于时间的 LRU 缓存 不同，LFU 优先淘汰访问频率最低的元素。

为什么 LFU 很重要

在访问频率比时效性更重要的场景中，LFU 更受青睐：

使用场景	为什么 LFU 更好
CDN 缓存	热门内容即使最近没被访问也会保留在缓存中
数据库查询缓存	频繁执行的查询会保持缓存
DNS 缓存	热门域名会保持在缓存中
CPU 缓存预取	频繁访问的内存地址优先级更高

LFU vs LRU：核心区别

考虑这个场景：

缓存容量：2
操作：put(1,A), get(1), get(1), get(1), put(2,B), put(3,C)

LRU 行为（基于”最近时间”）：

put(1,A):      [1:A]
get(1) x3:     [1:A]           ← key 1 是最新的
put(2,B):      [2:B, 1:A]      ← key 2 变成最新，key 1 变成较旧
put(3,C):      淘汰 key 1！     ← 因为 key 1 最久未访问
结果: [3:C, 2:B]

LFU 行为（基于”访问频率”）：

put(1,A):      [1:A(freq=1)]
get(1) x3:     [1:A(freq=4)]   ← key 1 访问了 4 次
put(2,B):      [1:A(freq=4), 2:B(freq=1)]
put(3,C):      淘汰 key 2！     ← 因为 key 2 频率最低 (freq=1)
结果: [1:A, 3:C]

核心区别一目了然：

• LRU 淘汰了 key 1：虽然它被访问过 4 次，但因为 key 2 是”最后访问的”
• LFU 保留了 key 1：因为它的访问频率（4次）远高于 key 2（1次）

💡 简单记忆：LRU 只关心”最后一次访问是什么时候”，LFU 关心”总共访问了多少次”

---

核心思路：HashMap + 频率桶

LFU 需要跟踪：

1. O(1) 查找 - 从 key 到节点的 HashMap
2. O(1) 频率跟踪 - 每个节点存储其频率
3. O(1) 淘汰 - 找到频率最低的，如果有多个则淘汰其中最久未使用的

┌─────────────────────────────────────────────────────────────────────────┐
│                            keyMap                                        │
│    key → Node 指针（O(1) 查找）                                           │
│                                                                          │
│    ┌───┐  ┌───┐  ┌───┐  ┌───┐                                           │
│    │ 1 │  │ 2 │  │ 3 │  │ 4 │                                           │
│    └─┬─┘  └─┬─┘  └─┬─┘  └─┬─┘                                           │
│      │      │      │      │                                              │
│      ▼      ▼      ▼      ▼                                              │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │                         freqMap                                      │ │
│ │ freq → 双向链表（每个频率内按 LRU 排序）                               │ │
│ │                                                                      │ │
│ │  freq=1: [4:D] ⟷ [2:B]                 ← minFreq（从这里淘汰）       │ │
│ │           ↑           ↑                                              │ │
│ │          MRU         LRU                                             │ │
│ │                                                                      │ │
│ │  freq=2: [3:C]                                                       │ │
│ │                                                                      │ │
│ │  freq=4: [1:A]                                                       │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────────────────┘

淘汰时：找到 minFreq 桶（freq=1），淘汰 LRU 条目（key 2）。

需要的数据结构：

1. keyMap：HashMap<key, Node> - O(1) key 查找
2. freqMap：HashMap<freq, DoublyLinkedList> - O(1) 频率桶访问
3. minFreq：跟踪最小频率以实现 O(1) 淘汰

---

交互式可视化

观察 LFU 缓存如何跟踪访问频率并根据使用模式进行淘汰：

Initializing...

---

与 LRU 缓存对比

看看 LRU 缓存的不同行为 - 它只跟踪时效性，不跟踪频率：

Initializing...

---

问题：LFU 缓存 (LC 460)

注意：这是一道 LeetCode 会员题。需要订阅才能提交。

问题：设计并实现一个 LFU（最不经常使用）缓存的数据结构。

实现 LFUCache 类：

• LFUCache(int capacity) - 以正整数容量初始化
• int get(int key) - 如果存在返回值（增加频率），否则返回 -1
• void put(int key, int value) - 更新或插入。如果容量超限，淘汰最不经常使用的元素。如果存在平局，淘汰其中最久未使用的。

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

算法步骤

1. 初始化：创建 keyMap、freqMap，设置 minFreq = 0
2. get(key)：
   • 如果 key 不在 keyMap 中 → 返回 -1
   • 否则 → 增加频率，移到新的频率桶，返回值
3. put(key, value)：
   • 如果 key 存在 → 更新值，增加频率
   • 如果 key 不存在：
     • 如果已满 → 从 minFreq 桶中淘汰（LRU 条目）
     • 创建 freq=1 的新节点 → 插入 freq=1 桶，设置 minFreq=1

---

代码模板

JavaPythonJavaScript

Loading...

---

完整示例演示

让我们追踪：LFUCache(2)，然后 put(1,10), put(2,20), get(1), put(3,30), get(2), get(3)

步骤 1: LFUCache(2)
freqMap: 空 | keyMap: {} | minFreq: 0

步骤 2: put(1, 10)
freqMap:
  freq=1: [1:10]
           ↑
minFreq: 1

步骤 3: put(2, 20)
freqMap:
  freq=1: [2:20] ⟷ [1:10]    ← 两者都是 freq=1
           ↑           ↑
          MRU         LRU
minFreq: 1

步骤 4: get(1) → 返回 10
freqMap:
  freq=1: [2:20]              ← 现在只有 key 2
  freq=2: [1:10]              ← key 1 升级了！
minFreq: 1（仍有条目）

步骤 5: put(3, 30) → 需要淘汰！淘汰谁？
Key 1: freq=2
Key 2: freq=1 ← 最低！淘汰它！

freqMap:
  freq=1: [3:30]              ← 新条目在 freq=1
  freq=2: [1:10]
minFreq: 1

❌ key 2 被淘汰（它是最不经常使用的）

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

步骤 7: get(3) → 返回 30
freqMap:
  freq=2: [3:30] ⟷ [1:10]    ← key 3 移到 freq=2
minFreq: 2（freq=1 桶现在空了）

---

LFU vs LRU：详细对比

方面	LRU（最近最少使用）	LFU（最不经常使用）
淘汰依据	自上次访问的时间	访问次数
复杂度	O(1)，1 个 HashMap + 1 个双向链表	O(1)，2 个 HashMap + 频率双向链表
空间开销	较低	较高（频率跟踪）
抗扫描性	差（全表扫描会淘汰所有）	好（频繁使用的元素能保留）
一次性访问	淘汰较老的元素	保留较老但热门的元素
突发访问	偏好最近访问的	可能淘汰最近访问但不频繁的
实现难度	较简单	较复杂

何时使用 LRU

• 时间局部性很重要（最近访问的 = 可能再次访问）
• 需要更简单的实现
• 内存开销是个问题
• 工作集频繁变化

何时使用 LFU

• 频率比时效性更重要
• 热门元素应该保持缓存，即使最近没被访问
• 工作集相对稳定
• 抗扫描性很重要

---

时间和空间复杂度

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

为什么是 O(1)？

• keyMap 提供 O(1) key 查找
• freqMap 提供 O(1) 频率桶访问
• 每个双向链表在有节点指针时提供 O(1) 插入/删除
• minFreq 提供 O(1) 访问淘汰候选桶

---

关键要点和常见错误

1. 正确更新 minFreq

什么时候 minFreq 会变化？

• 插入新 key 时：minFreq = 1（始终如此）
• 更新频率时：检查旧频率桶是否变空

private void updateFreq(Node node) {
    int oldFreq = node.freq;
    DLinkedList oldList = freqMap.get(oldFreq);
    oldList.remove(node);
    
    // 关键：只在以下情况更新 minFreq：
    // 1. 节点在 minFreq 桶中
    // 2. 且该桶现在为空
    if (oldFreq == minFreq && oldList.size == 0) {
        minFreq++;  // 下一个 minFreq 保证是 oldFreq + 1
    }
    
    node.freq++;
    freqMap.computeIfAbsent(node.freq, k -> new DLinkedList()).addFirst(node);
}

常见错误：在增加 minFreq 之前忘记检查桶是否为空。

2. 用 LRU 打破平局

当多个 key 具有相同的最小频率时，淘汰其中最久未使用的。

freq=1: [C] ⟷ [B] ⟷ [A]
        MRU         LRU
        ↑           ↑
     (最新)      (最老) ← 淘汰这个！

3. 新条目始终 freq=1

// 正确
Node node = new Node(key, value);
node.freq = 1;  // 始终从 1 开始
freqMap.get(1).addFirst(node);
minFreq = 1;    // 新条目始终是新的最小值

// 错误
minFreq = Math.min(minFreq, 1);  // 过于复杂，直接设为 1

4. 不需要删除空频率桶（可选）

你可以在 freqMap 中保留空桶 - 它们不影响正确性。但如果内存紧张：

if (oldList.size == 0) {
    freqMap.remove(oldFreq);  // 可选清理
}

---

面试追问

1. 如何处理频率衰减？

问题：旧元素累积了很高的频率，永远不会被淘汰。

解决方案：基于时间的衰减

• 定期将所有频率减半
• 或使用滑动窗口来计算频率

2. 线程安全

使用 ConcurrentHashMap 和对频率桶的细粒度锁定：

class ThreadSafeLFUCache {
    private final ConcurrentHashMap<Integer, Node> keyMap;
    private final ConcurrentHashMap<Integer, DLinkedList> freqMap;
    private final ReentrantLock lock = new ReentrantLock();
    
    public int get(int key) {
        lock.lock();
        try {
            // ... LFU 逻辑
        } finally {
            lock.unlock();
        }
    }
}

3. 用更简单的结构实现 O(1)？

替代方案：使用 HashMap + 最小堆，但这会使 put/get 变成 O(log n)。

O(1) 解决方案必须使用带双向链表的频率桶方法。

---

相关缓存策略

策略	淘汰策略	使用场景
LRU	最近最少使用	通用场景，良好的时间局部性
LFU	最不经常使用	稳定的工作集，频率很重要
LRU-K	最近 K 次未使用	LRU 和 LFU 之间的平衡
ARC	自适应（LRU + LFU）	自调整，两者优点兼顾
FIFO	先进先出	简单，可预测的淘汰顺序

---

相关题目

问题	描述	链接
LRU 缓存	淘汰最近最少使用的	LC 146
全 O(1) 的数据结构	跟踪最小/最大频率的 key	LC 432
设计排行榜	基于频率的排名	LC 1244 🔒
最大频率栈	按频率优先的栈	LC 895

---

总结

核心要点

1. 两个 HashMap：keyMap 用于 O(1) 查找，freqMap 用于 O(1) 频率访问
2. 每个频率一个双向链表：用于 O(1) 的频率内 LRU
3. minFreq 跟踪：O(1) 淘汰的关键
4. 打破平局：相同频率 → 淘汰其中的 LRU
5. 新条目：始终从 freq=1 开始，始终更新 minFreq=1

需要记住的模式

LFU 缓存 = HashMap<Key, Node> + HashMap<Freq, DLinkedList> + minFreq

get(key):
  1. keyMap 查找 → O(1)
  2. 从旧频率桶移除，添加到新频率桶 → O(1)
  3. 如果旧桶现在为空则更新 minFreq
  
put(key, value):
  1. 如果存在：更新值 + 更新频率
  2. 如果是新的：
     - 如果满了：从 freqMap[minFreq].tail 淘汰（LRU）
     - 插入到 freqMap[1]，设置 minFreq = 1

LFU vs LRU 决策指南

问题	LRU	LFU
最近访问是否能预测未来访问？	✅	❌
热门元素是否需要抗扫描保护？	❌	✅
实现简单性是否重要？	✅	❌
访问频率是否重要？	❌	✅

对于大多数通用缓存，LRU 更简单，通常足够好。当你需要抗扫描性或基于频率的淘汰对你的场景至关重要时，使用 LFU。