cache eviction · O(1) get / set / evict

O(1) LFU · 从动机到频率链表

LFU(Least Frequently Used)是一种缓存淘汰策略：容量满时，踢掉累计访问次数最少的条目。它和只看「最近用没用过」的 LRU 不同——LFU 看的是整段时间里的访问频率。朴素实现用 min-heap 维护频率，每次操作 $O(\log n)$ ；而一篇 2010 年的论文给出了一个巧妙的结构，让 get / set / 淘汰全部降到 $O(1)$ 。本页从动机讲到那套 $O(1)$ 结构，每个 demo 都能改输入、点单步，看频率链表如何随访问移动。

1 · 为什么需要 LFU：它和 LRU 差在哪

motivation · LFU vs LRU · 朴素代价

cache 容量有限，满了就得淘汰一个。挑哪个，是淘汰策略的事。两种最常见的策略：

LRU(Least Recently Used) 看时间：踢掉最久没被访问的那个。只关心「最近用没用过」。

LFU(Least Frequently Used) 看次数：踢掉累计访问最少的那个。关心「整段时间里用了多少次」。

差别在访问模式稳定时最明显。设想一个 CDN:Google logo 这种长期高频资源应当一直留着；某个短时间访问激增、随后迅速回落的资源则应在热度消失后被淘汰。LRU 容易被一批突发的一次性访问冲掉真正的热点——而 LFU 因为记着累计次数，能抵抗这种冲刷。下面这个频率计数器演示了 LFU 的核心动作：记次数、淘汰最低频。

1.1 · 朴素实现：维护频率不难，「取最低频」才贵

记次数很简单——一张 $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)$	见下面「频率链表 + bucket + hash 表」一节

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

2 · 核心：频率链表 + bucket + hash 表

core · O(1) 结构 + 单步 get / set / evict

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

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

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

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

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

下面输入 key / value 点 set 写入、或输入 key 点 get 读取，然后反复点「下一步」，看 item 在频率节点间移动、空节点被摘除、cache 满时如何淘汰最低频项。右侧代码逐行点亮。

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

3 · 对比与软肋：LFU 不是银弹

compare · 同序列对比 + LFU 的软肋

同一段访问序列、同样的容量，LFU 与 LRU 会淘汰不同的条目。下面并排跑两种策略，单步推进访问序列，看每一步各自的 cache 内容与淘汰记录。改序列或容量都会重算。

3.1 · LFU 的两个软肋

其一 cache pollution（缓存污染）——一个曾经被高频访问、如今再没人碰的旧条目，凭着高 count 长期占用 cache 空间。纯 LFU 没有遗忘机制，旧热点不会自动降温。

其二缺少 aging（老化）——新来的条目频率从 1 起步，哪怕它正在快速变热，也很容易在「热身」阶段就被那些 count 很高的旧条目挤掉（冷启动劣势）。

实践中的缓解办法：LFU with aging（给 count 定期衰减，或记「频率随时间的滑动窗口」）、LFUDA（LFU with Dynamic Aging，给计数加一个随淘汰推进的全局年龄基准）、以及现代的 TinyLFU / W-TinyLFU（用 count-min sketch 近似频率 + admission policy + 一个小 LRU 窗口吸收突发流量）——后者正是 Caffeine、Ristretto 等高性能缓存库的默认策略。一句话：纯 LFU 是地基，生产级缓存普遍在它之上加老化与准入控制。

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