上个月的题解写过 LRU 缓存（哈希表加双向链表的经典组合），但面试官的追问往往不止于此：「如果我希望缓存记住的是『最常用』而不是『最近用过』呢？」——这就是 LeetCode 460，LFU 缓存，一道把设计题难度推到顶的 Hard。它只比 LRU 多记一本「使用频率」的账，却让 O(1) 的实现需要两层嵌套的链表结构。本文从题意与朴素方案的瓶颈讲起，一步步推出双字典结构，给出一份可完整运行的 Python 实现（本地跑通边界用例），最后聊聊 Redis 是怎么把 LFU 思想塞进 24 个比特的。
一、题意：多一本账，多一条驱逐规则
先把题目要求翻译清楚。设计一个支持 get 与 put 的缓存结构，两个操作都要求平均 O(1) 时间复杂度：
get(key)：key 存在则返回其值，并把该 key 记为「使用过一次」；不存在返回 −1。put(key, value)：写入或更新。更新视为使用一次；插入新 key 时，若容量已满，必须驱逐一个 key。
驱逐规则是本题的灵魂，共两层：优先驱逐使用频次最低的 key；频次并列时，驱逐其中最久未使用的那个。每个 key 的频次从插入时的 1 起算，之后每次 get 或 put 命中都加一。数据范围：容量 0 到 10⁴，get/put 合计至多调用 2×10⁴ 次——操作次数不算大，但复杂度量级答错（比如给出 O(n) 驱逐）在面试里就是一票否决，题目考的正是结构设计而非常数优化。
先想清楚 LRU 为什么不够用。LRU 只维护「最近使用」的单维度排序，它有一个著名的软肋——扫描污染：一次偶然的全量批处理扫过几万个冷 key，LRU 链表被瞬间填满，真正的热数据全被挤到链表尾部、随后陆续被驱逐。LFU 引入频次维度后，扫一遍的冷 key 频次只有 1，而真正的热 key 频次早已很高，缓存扛得住这种偶发冲击。代价同样明显：LRU 只需维护一条按时间排序的链表，LFU 却要回答「全局频次最小的 key 是谁，且它里面最久未用的是谁」——如果每次驱逐都全表扫描找最小值，那是 O(n)，题目要求 O(1)，朴素方案当场出局。顺带一提，题目把容量为 0 也写进了约束：此时 get 恒返回 −1、put 什么都不做，实现里必须有显式的防御分支，否则驱逐逻辑会在空桶上崩掉。
二、O(1) 的钥匙：两层字典，桶里挂链
要做到三个 O(1)——查找 O(1)、更新频次 O(1)、找驱逐对象 O(1)——需要把三种信息各存在最合适的地方：
key → node字典：负责 O(1) 定位。node 里存值、频次，以及链表指针。freq → 频次桶字典：每个频次一个「桶」，桶内是一条双向链表，按使用时间排序——同频次的 key 天然按 LRU 序排列。这一个结构同时回答了「频次最小的桶在哪」（再配一个minFreq变量）与「并列时谁最久未用」（桶内链表头部）。minFreq整数：当前全局最小频次，驱逐时直接定位桶，不需要扫描。
三个操作各自动作如下。get：字典定位节点；把节点从原频次桶摘下，追加到 freq+1 桶尾部；更新 node 的频次；若原桶空了且 minFreq 等于原频次，把 minFreq 加一。put 已存在的 key：等价于一次 get（晋升频次）再加更新值。put 新 key：若超容量，先到 minFreq 桶的头部摘掉一个节点驱逐（头部即同频次中最久未用）；再插入新节点到频次 1 的桶尾，并把 minFreq 重置为 1——这一步是整个结构的点睛之笔：访问只会让频次升不会降，所以 minFreq 的变化只有两种可能：新 key 插入时归 1，或某桶被访问空了时上浮。绝不可能是别的值，因此永远不需要搜索。
不妨对照两个「看起来也行」的方案，理解这套结构为什么长成这样。方案甲：一个堆。把（频次，时间戳）压进小顶堆，驱逐时弹堆顶——单次驱逐 O(log n)，看似够用，问题出在更新：每次访问都要改堆内元素的频次，而堆不支持 O(1) 定位与调整，只能惰性处理（旧条目作废、新条目入堆），堆会膨胀且驱逐时可能弹出一串过期条目，均摊复杂度劣化。方案乙：一条全局链表。把所有 key 按频次排进一条链表——同频次内的时间序和全局最小频次的定位都解决了，但「访问一次频次加一」意味着节点要在链表里向前移动若干位，双向链表无法 O(1) 跳跃到目标位置。频次桶结构的巧思正在于把这两个方案各取一半：全局最小频次用变量记（免搜索），桶内顺序用链表存（免排序），桶间跳跃用字典查（免遍历）——三种信息各自放进最擅长保存它的容器。
三、代码实现（Python，本地验证通过）
class Node:
__slots__ = ("key", "value", "freq", "prev", "next")
def __init__(self, key=0, value=0):
self.key, self.value, self.freq = key, value, 0
self.prev = self.next = None
class DLinkedList:
# 带头尾哨兵的双向链表；头部是最久未用，尾部是最近使用
def __init__(self):
self.head, self.tail = Node(), Node()
self.head.next, self.tail.prev = self.tail, self.head
self.size = 0
def append(self, node): # 尾部插入 = 最近使用
node.prev, node.next = self.tail.prev, self.tail
self.tail.prev.next = node
self.tail.prev = node
self.size += 1
def remove(self, node):
node.prev.next, node.next.prev = node.next, node.prev
self.size -= 1
return node
def pop_front(self): # 头部弹出 = 同频次中最久未用
return self.remove(self.head.next)
class LFUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.kv = {} # key -> Node
self.buckets = {} # freq -> DLinkedList
self.min_freq = 0
def _touch(self, node): # 频次晋升：从旧桶摘下挂进新桶
old = self.buckets[node.freq]
old.remove(node)
if old.size == 0 and node.freq == self.min_freq:
self.min_freq += 1
node.freq += 1
self.buckets.setdefault(node.freq, DLinkedList()).append(node)
def get(self, key: int) -> int:
if self.cap <= 0 or key not in self.kv:
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: # 驱逐：minFreq 桶头 = 最低频 + 最久未用
victim = self.buckets[self.min_freq].pop_front()
del self.kv[victim.key]
node = Node(key, value)
node.freq = 1
self.kv[key] = node
self.buckets.setdefault(1, DLinkedList()).append(node)
self.min_freq = 1
这段实现需要说明三个细节。其一，DLinkedList 的头尾哨兵让「摘除任意节点」「头部弹出」都是纯指针操作，没有边界判断。其二，桶内链表头是最久未用、尾是最近用：新晋升的节点挂尾部，驱逐从头弹出——同频次内的 LRU 语义不花钱地搭了链表顺序的便车。其三，minFreq 的维护严格对应第二节的两种变化，没有任何搜索成分，三个操作因此都是 O(1)。
四、本地验证：边界用例跑通
设计题最怕「看起来对」。按题目约束（容量可为 0；get/put 合计至多 2×10⁴ 次）写一组本地测试，覆盖四个高危边界：容量 0 直接短路；同频次驱逐必须选最久未用；晋升后 minFreq 上浮；更新已有 key 不新增频次桶、只晋升。测试脚本如下（发布前已本地运行，全部断言通过）：
c = LFUCache(2)
c.put(1, 1); c.put(2, 2) # {1:1, 2:2}，均频次 1
assert c.get(1) == 1 # 1 晋升到频次 2
c.put(3, 3) # 容量满，驱逐频次 1 且最久未用的 2
assert c.get(2) == -1 # 2 已被驱逐
assert c.get(3) == 3 # 3 频次 1 -> 2
c.put(4, 4) # 驱逐 1（频次 2 中最久未用）
assert c.get(1) == -1 and c.get(3) == 3 and c.get(4) == 4
z = LFUCache(0) # 容量 0：put 直接忽略，get 恒 -1
z.put(1, 1)
assert z.get(1) == -1
t = LFUCache(2) # 更新已有 key 也算一次使用
t.put(1, 1); t.put(2, 2); t.put(1, 10) # 1 晋升
t.put(3, 3) # 驱逐 2（频次 1 最久未用）
assert t.get(1) == 10 and t.get(2) == -1
print("all assertions passed")
运行输出 all assertions passed。四个边界分别验证了：驱逐优先级（频次第一、时间第二）、minFreq 上浮、容量 0 的防御，以及「更新也算使用」这条最容易被忽略的题意。除了这组手工用例，我还做了一层更狠的验证：与朴素实现随机对拍——写一个每次驱逐时全表扫描找「（频次，时间）」最小值的 O(n) 参考实现，两个实现喂同一串随机操作序列（固定随机种子，5000 步，key 空间大于容量制造频繁驱逐），逐步断言两者 get 返回值完全一致。手工用例测的是「想到的边界」，对拍测的是「想不到的路径」——随机序列会自然踩到「晋升后桶空导致 minFreq 连续上浮」「同频次驱逐与晋升交错」这类容易漏写的组合。对照数据范围评估常数：2×10⁴ 次操作 × O(1) 每次，完全在限内。
把这道题真正吃透的标志，是能回答三个延伸问题。其一，为什么每个频次一个桶而不是一棵平衡树？平衡树也能按（频次，时间）排序并 O(log n) 完成删除，但实现复杂度高一个数量级，且本题要求 O(1)——频次的取值范围有限（至多等于总操作数），用「字典 + 桶」空间换时间正合适。其二，桶内为什么用双向链表而不是数组？因为晋升操作要把节点从桶中任意位置摘除，数组摘除是 O(n)，双向链表配合节点内指针是纯指针操作。其三，这套结构在并发下怎么活？标准答案是对整个缓存加一把锁——这正是工程题的开始：分段锁、近似 LFU、或者像 Redis 那样干脆放弃精确性，都是并发压力下的合法退让。算法题给的是理想世界里的最优结构，工程师的功课是把理想结构在现实约束下用到「足够好」。
五、实战回声：Redis 怎么把 LFU 塞进 24 个比特
面试之外，LFU 在工业界最有名的落地是 Redis 4.0 起的 LFU 淘汰策略（allkeys-lfu 等模式）。它没有照搬本题的精确账本，而是做了两步工程化近似：频次用 Morris 概率计数器压缩进 8 个比特（对数式增长，0–255 封顶，越往上越难加一）；同时给计数器加按时间衰减（lfu-decay-time 配置，单位分钟），让「昨天的热点」不霸占今天的频次优势；增长速度再由 lfu-log-factor 调节。另外，Redis 的 LFU 也复用了 LRU 的候选采样框架——不维护全局排序，而是在采样中比较近似频次，用统计换内存。
Redis 的两个近似恰好是本题精确结构的两面镜子。概率计数承认「精确频次不重要，量级才重要」，换来了每对象 8 比特的极致成本——本题的双字典结构每个节点要维护五个字段加两个指针，在千万级 key 的内存账上完全不划算。时间衰减则修补了精确 LFU 的一个理论缺陷：纯频次是历史累计的，一个「曾经很热、已经冷了」的 key 频次高高挂起，永远不被驱逐——教科书标准里这叫 LFU 的「缓存污染」变体，Redis 用衰减让频次随时间退潮。对照本题可以发现工程与算法题的取舍差异：题目追求精确 O(1) 与严格语义，Redis 追求的是「用最少比特抓住大致的热点」——思想同源，精度与成本各取所需。
结语
LFU 缓存是设计题里「一层抽象换一个维度」的典范：LRU 回答「最近」，LFU 在它上面叠了一层「经常」。双字典加频次桶的结构拆开看毫无魔法，难点全在「minFreq 只会两种变化」这类不变量的发现与维护上——而这恰恰是系统设计中最可迁移的能力。最后留一个思考题：如果要求支持「过期时间」或「带权重的频次」，这套结构该在哪里动刀？
参考资料
- LeetCode 460. LFU Cache——题目原文与约束
- 460. LFU Cache - In-Depth Explanation（AlgoMonster）——双字典结构的逐段讲解
- LFU Cache Solution（NeetCode）——频次桶思路的另一视角
- Key eviction（Redis 官方文档）——Morris 计数器、lfu-log-factor 与衰减配置
读者留言
COMMENTS 暂无还没有留言，来说第一句？