缓存淘汰
01 / 共享的机制
容量固定的存储,get 和 put 都要 O(1)。 关键是数据结构 —— 每种淘汰策略都是在回答同一个问题:缓存满了之后,该丢哪个? 两个经典策略共享同一套 O(1) 套路 ——LRU 用「哈希表 + 双向链表」让刚访问的 key 在常数时间内移到表头;LFU 按频次分桶,使最低频桶的尾节点始终能 O(1) 取出。
02 / 一句话本质
用按频次分桶的方式追踪每个 key 的访问次数;minFreq 指针始终指向当前最低频的桶 —— 「找出 LFU 条目」从 O(N) 扫描降到 O(1)。同频时按桶内 LRU淘汰。题目实现一个 O(1) 的 LFU 缓存容量4操作8
空的 LFU 缓存,容量 4。共有 8 个操作。
步
0 / 13
当前操作
—
minFreq
—
大小
0 / 4
0 / 13
03 / 模式骨架
# 状态:map[k] → 节点;buckets[freq] = 双链表;minFreqdef get(k):if k not in map: return −1node ← map[k]buckets[node.freq].remove(node)if buckets[minFreq] 为空 and node.freq == minFreq: minFreq += 1node.freq += 1; buckets[node.freq].push_head(node)return node.val def put(k, v):if k in map: map[k].val ← v; get(k); returnif size == capacity:victim ← buckets[minFreq].pop_tail()map.delete(victim.key)node ← Node(k, v, freq=1)buckets[1].push_head(node); map[k] ← node; minFreq ← 1
04 / 什么时候用这个模式
"频次优先于近期性"
选 LFU 而不是 LRU,意味着你认为工作负载有稳定的「热点集」—— 少数 key 被反复访问,即便有阵子没碰也想留住它们。频次计数器是核心信号,近期性只用来打破平局。
"同频按近期性淘汰"
同一频次桶内,双向链表记录插入 / 提升的次序:新人入表头,淘汰出表尾。 因此同频两个 key 按「上次访问的远近」排序 —— 桶内就是纯 LRU。 LFU 是按频次分层的 LRU。
"minFreq 指针"
单个整数支撑整个 O(1)。每次提升要么不动
minFreq, 要么把它 +1(如果刚把 buckets[minFreq] 清空)。 每次新插入直接重置为 1。无需扫描、无需堆、无 log 因子 —— 纯簿记。05 / 常见坑
插入新节点忘记
minFreq = 1。新插入的节点频次必然是 1,落入
buckets[1] —— 无论 minFreq 原先是多少,都必须重置为 1。漏掉这一步,下一次淘汰就会从错误的桶里挑节点, 把一个更热的 key 当成冷门给删掉。提升后没有把
minFreq 推进。当一次
get 把 buckets[minFreq] 的最后一个节点提走了,这个桶就空了 —— minFreq 必须前进到下一个非空频次(通常就是 minFreq + 1)。 忘了这件事,下一次淘汰对着空桶取节点 —— 要么崩,要么把错的删掉。 检查应放在「从旧桶移除」之后的同一个位置。没判断容量就先淘汰。
淘汰只在「
size == capacity 且 key 是新的」时才发生。 无条件淘汰的话,每次 put(包括更新已有 key、未满时插入)都会丢一个节点 —— 缓存装不满,命中率暴跌。分支顺序:先更新?再淘汰?最后插入? 顺序必须严格如此。06 / 去 LeetCode 上练习
四道题。LFU Cache 是这套结构的标准实现题。 其余三道在不同形式下都要求同样的「频次簿记」肌肉 —— 哈希表 + 桶链表的架构不变,只是不变量换了。
— / 什么时候用哪个
LRU
当信号是 访问近期性 时用 —— 最近用过的最可能再用。 哈希表把 key 映到链表节点,双向链表维持访问顺序。 每次 get/put 只动几个指针 + 一次哈希查找,稳稳 O(1)。
哈希表 + 双向链表 · LC 146
LFU
当信号是 访问频次 时用 —— 热门 key 即使最近没动过也不该被新插入的冷 key 挤掉。 哈希表 → 节点;每个频次一个桶链表;一个 `minFreq` 指针指向下次淘汰候选所在的桶。 仍是 O(1),代价是更多的簿记。
哈希表 + 频次桶 · LC 460