缓存淘汰
01 / 共享的机制
容量固定的存储,get 和 put 都要 O(1)。 关键是数据结构 —— 每种淘汰策略都是在回答同一个问题:缓存满了之后,该丢哪个? 两个经典策略共享同一套 O(1) 套路 ——LRU 用「哈希表 + 双向链表」让刚访问的 key 在常数时间内移到表头;LFU 按频次分桶,使最低频桶的尾节点始终能 O(1) 取出。
02 / 一句话本质
刚被访问的节点移到表头;表尾就是下一个淘汰对象。 哈希表负责 O(1) 定位,双向链表负责 O(1) 摘接。合起来:每次操作 O(1)。
题目设计一个 LRU 缓存,get / put 均 O(1)容量4操作数8
空缓存,容量 4。即将执行 8 次操作。
步
0 / 12
当前操作
—
大小 / 容量
0 / 4
0 / 12
03 / 模式骨架
# 状态:capacity、map: key → node、list: head ↔ … ↔ taildef get(k):if k not in map: return −1node ← map[k]splice(node); pushFront(node)return node.valdef put(k, v):if k in map:node ← map[k]; node.val ← vsplice(node); pushFront(node); returnnode ← Node(k, v); map[k] ← nodepushFront(node)if len(map) > capacity: # 超容evicted ← popBack(); del map[evicted.key]
04 / 什么时候用这个模式
"容量固定 + O(1) get/put"
LRU 缓存的标准签名。如果题目暗示要做缓存但又坚持两个操作都得是常数时间,这就是信号 —— 单靠哈希表或者单靠链表都做不到。必须二者合一,相互连接。
"最久未访问淘汰"
访问近期性是由链表顺序携带的,不是任何时间戳。每次读写都把被访问的节点移到表头, 所以表尾自然是最久未访问的那个。不需要时间戳,也不需要扫描 —— 顺序由链表本身维护。
"move-to-front 的味道"
LC 432(All O`one)、LC 1756(Most Recently Used Queue) —— 题目不同,节奏相同: 哈希表指向链式结构里的某个节点,使得被访问的元素能 O(1) 跳到指定的一端。这种套路远不止用在 LRU。
05 / 常见坑
淘汰后忘了删除哈希表里的条目。
表尾节点被弹出时,务必同步
del map[evicted.key] —— 否则哈希表仍声称缓存里有这个 key,后续的 get 会愉快地返回一个早已不在链表里的陈旧节点。 链表和哈希表必须步调一致。容量判断写错(off-by-one)。
淘汰的触发条件是
size > capacity,不是 ≥。先插入,再判断是否超容 —— 这样始终有位置容纳新节点。 顺序或比较符颠倒,要么丢掉刚插的条目,要么永远不淘汰。put 更新已有 key 时漏掉了移到表头。
更新已有 key 也算一次「触碰」—— LRU 策略不在乎是读还是写,只在乎发生了。 忘了把它挪到表头,淘汰顺序就会悄悄偏离真实的访问顺序。 这种 bug 只在后续的 put 触发超容时才暴露出来。
06 / 去 LeetCode 上练习
四道题。LRU Cache 是教科书级别的实现。LFU Cache 沿用「哈希表 + 链表」这一套,再叠一层频次跟踪。All O`one 把 move-to-front 推广到能同时 O(1) 取最大最小。First Unique Number 把同样的哈希 + 链式结构用到了流式唯一性问题上。
— / 什么时候用哪个
LRU
当信号是 访问近期性 时用 —— 最近用过的最可能再用。 哈希表把 key 映到链表节点,双向链表维持访问顺序。 每次 get/put 只动几个指针 + 一次哈希查找,稳稳 O(1)。
哈希表 + 双向链表 · LC 146
LFU
当信号是 访问频次 时用 —— 热门 key 即使最近没动过也不该被新插入的冷 key 挤掉。 哈希表 → 节点;每个频次一个桶链表;一个 `minFreq` 指针指向下次淘汰候选所在的桶。 仍是 O(1),代价是更多的簿记。
哈希表 + 频次桶 · LC 460