LFU 缓存——从 LRU 到 LFU，设计题的“频率革命“

摘要：LRU 问"你多久没被用"，LFU 问"你被用了几次"。缓存满了，LFU 淘汰最不常被访问的项。这篇从 LRU 的局限讲起，手写 LeetCode 460（Hard）双哈希表 + 频率桶的 O(1) 实现，用 895 最大频率栈展示"频率索引"的对称思想，附三语言、手算推演与对比表。

关键词：LFU 缓存、LeetCode 460、LeetCode 895、频率桶、双向链表、缓存淘汰策略、LRU

引子：缓存满了，谁该被请出去？

8 月的 LRU 篇（DSA 第20篇）讲了一个答案：最久没被用的滚蛋。但假设你的系统里有一个"每周五 10 点被大批量访问"的热点数据——它平时很冷，只在固定时刻爆热。LRU 可能刚把它请出去，下一秒访问就来了。

LFU（Least Frequently Used）给出另一个答案：用得最少的滚蛋。它不问"你多久没来"，而问"你来了几次"。这篇从 LRU 的局限讲起，手写 LeetCode 460（Hard）的双哈希表 + 频率桶实现，再用 895 最大频率栈展示"频率索引"思想的对称面。

---

一、为什么需要 LFU？

1.1 LRU 的局限：时间 ≠ 重要

LRU 的核心假设是时间局部性：刚被访问过的，很快还会被访问。但真实场景里：

• 周期性热点（每周五 10 点的报表）平时很冷，LRU 会提前淘汰它

• 批量扫描任务会"污染"缓存：一次性访问大量数据，把真正的高频热点挤出去

LRU 只记得"最后一次"，记不住"总共几次"——这就是 LFU 的动机[3]。

1.2 LFU 的直觉：次数才是真爱

LFU 给每个 key 记一个访问频率，容量满时淘汰频率最低的。它更适合"访问模式稳定"的场景（CDN 热点、数据库查询缓存）——高频项长期驻留，低频项快速清退[3]。

---

二、LFU 淘汰规则

2.1 主淘汰 + 兜底

容量满时： ① 先找频率最低的桶（min_freq） ② 桶内按"最近使用时间"排序 → 淘汰最久未用的 → LFU 主淘汰 + LRU 兜底 = 双保险[1]

为什么需要 LRU 兜底？因为同频率的 key 可能有多个，必须有个规则决定谁先走——"最久未使用"是最自然的仲裁者[1]。

---

三、460 三件套实现

3.1 三个映射，全是 O(1)

要做到 get/put 均摊 O(1)，需要三个结构互相配合[1][4]：

• 哈希表①key → (value, freq)：get 查值 O(1)

• 哈希表②freq → 双向链表：同频率项按访问时间排序，尾部最旧

• 节点存 key：哈希表①能定位节点，从而 O(1) 从链表删除（不存 key 就得 O(n) 找）

3.2 Python 实现（核心逻辑）

class Node: __slots__ = ('key', 'value', 'freq', 'prev', 'next') def __init__(self, key=0, value=0): self.key, self.value, self.freq = key, value, 1 self.prev = self.next = None class DLinked: """频率桶：双向链表，头 = 最新，尾 = 最旧""" def __init__(self): self.head, self.tail = Node(), Node() self.head.next, self.tail.prev = self.tail, self.head self.size = 0 def push_front(self, node): nxt = self.head.next self.head.next, node.prev = node, self.head node.next, nxt.prev = nxt, node self.size += 1 def remove(self, node): node.prev.next, node.next.prev = node.next, node.prev self.size -= 1 def pop_back(self): node = self.tail.prev self.remove(node) return node def empty(self): return self.size == 0 class LFUCache: def __init__(self, capacity: int): self.cap = capacity self.min_freq = 0 self.kv = {} # key -> Node self.freqs = {} # freq -> DLinked def _touch(self, node): """访问节点：频率 +1，移入下一桶""" f = node.freq self.freqs[f].remove(node) if self.freqs[f].empty() and f == self.min_freq: self.min_freq += 1 # 桶空且是最小频率 → 最小频率上移 node.freq += 1 self.freqs.setdefault(node.freq, DLinked()).push_front(node) def get(self, key: int) -> int: if key not in self.kv or self.cap == 0: return -1 node = self.kv[key] self._touch(node) return node.value def put(self, key: int, value: int) -> None: if self.cap == 0: return if key in self.kv: node = self.kv[key] node.value = value self._touch(node) return if len(self.kv) >= self.cap: victim = self.freqs[self.min_freq].pop_back() # 最冷桶的最旧节点 del self.kv[victim.key] node = Node(key, value) self.kv[key] = node self.freqs.setdefault(1, DLinked()).push_front(node) self.min_freq = 1

3.3 C++ 要点

class LFUCache { struct Node { int key, val, freq; list<Node>::iterator it; }; unordered_map<int, Node> kv; unordered_map<int, list<Node>> freqList; // freq -> 双向链表 int cap, minFreq; public: // get/put 与 Python 逻辑一致；链表用 std::list 天然 O(1) 删除 };

3.4 手算推演

capacity=2 put(1,1): 1号桶=[1(f1)] min_freq=1 put(2,2): 1号桶=[1(f1),2(f1)] min_freq=1 get(1): 1→f2：1号桶=[2] 2号桶=[1] min_freq=1 put(3,3): 满 → 淘汰 1 号桶尾部 2(f1) → 3(f1)入 1号桶 → [3, 1号桶], 2号桶=[1] get(1): 1→f3 get(3): 3→f2 get(4)= -1（不存在）

每一步验证："最小频率桶的最旧节点"就是牺牲品——2只被访问过一次，最先出局。

---

四、895 最大频率栈：对称的另一极

4.1 问题与直觉

LeetCode 895：实现一个栈，pop()返回频率最高且最接近栈顶的元素[2]。

注意对称性：

• LFU（460）：淘汰min_freq（最冷）

• 895：弹出max_freq（最热）

实现同样简单：元素→频率+频率→栈（同频率用栈天然满足"后进先出"）[2]。

4.2 Python 实现

from collections import defaultdict class FreqStack: def __init__(self): self.freq = defaultdict(int) # 元素 -> 频率 self.stacks = defaultdict(list) # 频率 -> 栈 self.max_freq = 0 def push(self, val: int) -> None: self.freq[val] += 1 f = self.freq[val] self.stacks[f].append(val) self.max_freq = max(self.max_freq, f) def pop(self) -> int: val = self.stacks[self.max_freq].pop() self.freq[val] -= 1 if not self.stacks[self.max_freq]: self.max_freq -= 1 # 栈空则最高频率下移 return val

4.3 为什么值得一起学

460 的桶是双向链表（要淘汰最旧），895 的桶是栈（要弹出最新）——同一个"频率→容器"索引，容器按需求换形态。这就是数据结构迁移：理解了频率索引思想，两题一起拿下[2]。

---

五、LRU vs LFU + 我的心得

5.1 对比表

维度	LRU（146）	LFU（460）
淘汰依据	最久未使用	使用频率最低
核心假设	时间局部性	频率稳定性
数据结构	哈希+双向链表	双哈希+频率桶
复杂度	O(1)	O(1)（均摊）
适合场景	通用缓存	热点稳定（CDN/DB 缓存）
变体	—	Redis volatile-lfu

5.2 三条心得

心得一：缓存淘汰没有银弹。LRU 怕"突发热点被误杀"，LFU 怕"历史热点僵死"。Redis 默认组合策略说明工程上从不迷信单一算法[3]。

心得二：O(1) 的实现代价是"索引套索引"。460 用三个映射互相定位——这是设计题的核心考点：能用 O(1) 的前提是每一步都有索引。

心得三：频率思想可以反向用。895 证明"频率"不仅能淘汰最冷，还能弹出最热——一个概念，两个出口。

LFU 是 LRU 的"频率革命"：把缓存从"时间记忆"升级到"频率记忆"。当你再遇到"淘汰谁"的设计题，就拥有了两套完整的武器库。

---

参考资料

信源编号对应02-情报.md信源清单。

• [1] LeetCode 460 官方题解（一级）

• [2] LeetCode 895 官方题解（一级）

• [3] 系统设计教材：缓存淘汰策略（二级）

• [4] 力扣讨论区：460 复杂度证明（三级）