LFU 缓存如何用哈希表做到 O(1)？
简化版
LFU 按访问频次淘汰，频次相同再淘汰最久未使用。O(1) 设计常用两层哈希：key -> 节点 快速定位，freq -> 双向链表 管理同频节点的 LRU 顺序，再维护 minFreq 找到最低频次。
详细版
get 命中后要把节点频次加 1，并从旧频次链表移动到新频次链表头部；put 超容量时，从 minFreq 对应链表尾部删除最旧节点。哈希表负责 O(1) 定位，双向链表负责 O(1) 删除和插入。
keyMap: key -> node(key,val,freq)
freqMap: freq -> linked list of nodes, head = newest
minFreq: 当前最小频次LFU 比 LRU 多了频次维度，所以不能只用一个链表。
完整版教学
一、LFU 和 LRU 的差别
LRU 看“最近有没有用”，LFU 看“总共用得频不频繁”。如果缓存满了，LFU 要淘汰访问次数最低的 key；若最低频次有多个，再按 LRU 淘汰其中最久未访问的。
例如容量 2，操作 put(1), put(2), get(1), put(3)：key1 频次 2，key2 频次 1，所以淘汰 key2。
二、为什么一个 HashMap 不够
一个 HashMap 能 O(1) 找到 key，但不知道哪个 key 频次最低、同频里谁最旧。若每次淘汰都扫描所有节点找最低频，put 会退化到 O(n)。
LFU 需要同时支持三种 O(1) 能力：
| 能力 | 结构 |
|---|---|
| 按 key 找节点 | key -> node |
| 按频次找一组节点 | freq -> list |
| 同频内淘汰最旧 | 双向链表尾部 |
这就是两层哈希加链表的来源。
三、节点里需要存什么
节点至少存 key、value、freq，以及链表前后指针。存 key 是为了淘汰时能从 keyMap 中删除对应项；存 freq 是为了 get 时知道它当前在哪个频次链表。
class Node {
int key, val, freq = 1;
Node prev, next;
}如果不在节点里存 freq，每次提升频次都得反查它所在链表，O(1) 设计会变复杂。
四、get 命中时发生什么
get(key) 命中后，不只是返回 value，还要提升频次。步骤是：从旧频次链表删除节点；如果旧频次等于 minFreq 且链表空了，minFreq++；把节点 freq 加 1；插入新频次链表头部。
freq=1: [A, B]
get(B)
freq=1: [A]
freq=2: [B]插入头部表示 B 在 freq=2 这一组里最近被访问。
五、put 超容量时怎么淘汰
新 key 插入时频次为 1，所以如果缓存超过容量，要先淘汰 minFreq 链表尾部的节点。尾部代表该频次下最久未使用的节点，满足“频次最低 + 同频 LRU”。
minFreq = 1
freq=1 链表: head [newer ... older] tail
淘汰 tail.prev插入新节点后，minFreq 应设为 1，因为新节点频次就是 1。
六、常见误区与追问
记忆钩子：LFU 是“先按频次分桶，再在桶内按最近使用排序”。
- 误区：LFU 只要记录访问次数即可。 淘汰时还要在最低频次中找最旧节点，需要链表维护顺序。
- 误区：一个全局链表能解决。 全局链表只能表达最近使用顺序，不能快速定位最低频次组。
- 误区：get 不改变缓存状态。 LFU 中 get 会增加频次并移动节点。
- 追问：capacity 为 0 怎么办？ put 直接返回，不能插入任何节点。
- 追问：为什么要
minFreq？ 避免淘汰时扫描所有频次，保持 O(1)。 - 追问：LFU 的缺点是什么？ 老热点可能因历史频次过高长期不淘汰，工程中常配合衰减或窗口策略。
七、加强记忆
LFU 的 O(1) 设计要背结构关系：keyMap 管定位，freqMap 管频次桶，桶内双向链表管同频 LRU，minFreq 管最低频次入口。每次 get 是“从旧桶搬到新桶”，每次淘汰是“删 minFreq 桶尾”。这比 LRU 多的正是频次分桶这一层。