Appearance
LRU 缓存：哈希表与双向链表如何同时满足 O(1)
主题边界
- LRU 缓存要求最近使用的数据保留，最久未使用的数据在容量满时被淘汰。
- 高频问法是如何把
get/put都做到 O(1)。
机制与流程
- 哈希表负责 O(1) 找到节点；双向链表负责 O(1) 把节点移动到头部并淘汰尾部。
- 访问或更新一个 key 时，需要把对应节点移动到链表头部表示最近使用。
- 容量超限时删除尾节点，并同步从哈希表移除映射。
关键差异
- 只用数组维护访问顺序会导致移动和删除退化到 O(n)。
- LFU、FIFO 与 LRU 解决的是不同的淘汰策略，不应混淆。
边界条件
- 真实缓存系统还要考虑过期时间、并发访问、脏数据和内存上限，这超出基础题范围。
- 语言自带的
Map虽然保持插入顺序，但直接改造为严格 LRU 仍要注意更新时的删除重插代价。
工程落点
- 理解 LRU 有助于阅读浏览器缓存、状态缓存和后端缓存组件的设计。
- 很多“手写缓存”失败点不在语法，而在数据结构选型与不变量维护。