频率链表 · bucket · O(1) evict

LFU：频率链表把淘汰做到 O(1)

淘汰策略是在猜未来 §3 把在线策略能用的历史信息压成 recency 与 frequency 两个标量，本页落实其中的 frequency。纯 LFU 的规则一句话说完：容量满时踢掉累计访问次数最少的条目。难的不是规则而是代价——朴素实现用 min-heap 维护频率，每次访问都要 sift 一次， $O(\log n)$ 恰好压在 cache 中最高频的那个操作上。2010 年的一篇论文给出一个不需要排序的结构，把 get、set 与淘汰全部降到 $O(1)$ [1]。

1 · 朴素实现的代价

motivation · 记次数容易 · 取最低频难

记次数很简单——一张 $key \to count$ 的 hash 表即可。真正的成本在淘汰时要找出 count 最小的那个。三种做法的代价分布并不相同：

实现	记一次访问	找最低频 / 淘汰	问题
hash 表 + 淘汰时线性扫描	$O(1)$	$O(n)$	每次淘汰扫全表
hash 表 + min-heap（按 count）	$O(\log n)$	$O(\log n)$	访问后要 sift 维护堆序
频率链表 + bucket（ $O(1)$ 方案）	$O(1)$	$O(1)$	见 §2

用 min-heap 是最直觉的做法，但每次访问令某个 key 的 count 加一，都要在堆里 sift 一次维护堆序。访问是 cache 里最高频的操作，给它套上 $O(\log n)$ 并不划算。关键观察是：每次访问只会让频率加一——频率的变化是「相邻」的，不需要堆那种任意比较。顺着这个观察，就有了 §2 的频率链表。

图 1-1 · 频率计数器：每次访问让计数加一，淘汰时踢掉计数最低的条目。可改访问序列观察计数分布与淘汰对象的变化。

2 · 频率链表与 bucket

core · 三个结构组合 · 谁都不用排序

难点是「每次访问后，如何 $O(1)$ 地更新频率并随时取到最低频项」。答案是把三个结构组合起来，谁都不用排序：

其一 bykey——一张 $key \to item$ 的 hash 表，负责 $O(1)$ 定位 item。

其二频率链表——一条按 freq 递增的双向链表，节点只在被用到时存在（所以频率是 1、2、5 这样跳着的）。

其三 bucket——每个频率节点挂一组处于该频率的 item，按访问新旧排序（头为最旧，尾为最新）。item 自己存一个指向所属频率节点的指针。

有了 item 的 parent 指针，「频率加一」只是把 item 从当前节点搬到相邻的 freq + 1 节点——全是指针操作，不需要遍历或排序。

图 2-1 ·

O(1)

结构的单步执行。可输入 key 与 value 执行 set、输入 key 执行 get，逐步观察 item 在频率节点间移动、空节点被摘除，以及 cache 满时最低频桶的队尾被淘汰，右侧代码同步点亮当前行。

为什么是 $O(1)$ ：整个 increment 没有任何循环或排序——靠 item 的 parent 指针直接拿到当前频率节点，只看「相邻的下一个节点」是不是 freq + 1，是就复用、不是就插一个新节点，再把 item 搬过去。淘汰同理：链表头永远是最低频节点，取它 bucket 的头部即可。图 2-1 为了排版用数组画 bucket，真实实现里节点是双向链表、bucket 是 hash set，增删都是 $O(1)$ 。

3 · 纯 LFU 的边界

compare · 同序列对比 · 两个软肋

同一段访问序列、同样的容量，LFU 与 LRU 会淘汰不同的条目。两者的分歧点正是 recency 与 frequency 这两个信号的分歧点。

图 3-1 · 同一段访问序列下 LFU 与 LRU 的命中对照。可切换访问模式与容量，观察两者各自失效的场景与逐步的淘汰记录。

淘汰策略是在猜未来 §4 已把这两个信号的失效场景摆开，落到纯 LFU 身上是两条：cache pollution——曾经高频、如今无人访问的旧条目凭高 count 长期占位，纯 LFU 没有遗忘机制；以及缺少 aging——新条目从频率 1 起步，哪怕正在快速变热，也容易在热身阶段被高 count 的旧条目挤掉。

两条都指向同一个缺口：计数器只累加、不衰减。补法有三代。LFU with aging 给 count 定期衰减，LFUDA 给计数加一个随淘汰推进的全局年龄基准，而 W-TinyLFU：准入判定与频率草图换掉了整个记账方式——用 Count-Min sketch 近似全体 key 的频率、周期性减半实现老化，再把 frequency 从「该踢谁」挪去回答「该放谁进来」。它是 Caffeine 与 Ristretto 的默认策略。纯 LFU 因此是地基而非成品：本页这套 $O(1)$ 结构给出了 frequency 信号的精确记法，此后几页讨论的都是如何让这个信号别失真。

和别的系列串起来看：朴素 LFU 里那个按频率取最小的 min-heap，正是 priority queue 与 binary heap；而 $O(1)$ 结构靠的是双向链表的 $O(1)$ 节点增删——此处把两者组合成了一个不需要堆的方案。

4 · 参考文献

Shah, K., Mitra, A., & Matani, D. (2010). An O(1) algorithm for implementing the LFU cache eviction scheme. 技术报告。