LRU 缓存
你将构建什么
一个 LRUCache 类,get(key) 和 put(key, value) 均为 O(1),在超出容量时淘汰最久未使用的条目。
学习目标
- 结合哈希表(O(1) 查找)与双向链表(O(1) 更新访问顺序)
- 实现带溢出淘汰的 get 和 put
- 推理操作复杂度
- 在注释中论证设计选择
前置要求
- 对象作为哈希表
- 链表概念(见 project-11)
- O(1) 复杂度推理
步骤
- 1
选择数据结构
决定如何实现 O(1) 的 get 和 put。经典做法:用 Map(或对象)做 key→node 查找,用双向链表跟踪访问顺序。在注释中记录你的选择。
提示
双向链表让你在已有节点引用时,O(1) 地将其移到头部。
- 2
定义节点与缓存骨架
定义双向链表节点(value、prev、next)和接受 capacity 的 LRUCache 构造函数。初始化 map 和链表 head/tail 哨兵。
提示
哨兵 head/tail 节点可简化边界情况(空表、单节点)。
- 3
实现 get
get(key) 存在则返回值并将该节点移到头部(最近使用);不存在返回 -1。验收标准:缺失键返回 -1;存在键返回值并标记为最近使用。
提示
在 map 中查找节点,从当前位置解除链接,移到头部。
- 4
实现带淘汰的 put
put(key, value):键存在则更新值并移到头部;新键则加到头部并增加 size。若 size 超过容量,淘汰最久未使用(尾部)并从 map 移除。验收:超出容量后最旧条目被移除。
提示
淘汰时移除尾哨兵前的节点,并从 map 删除其键。
- 5
用场景验证
编写测试:缓存容量 2; put(1,1), put(2,2), get(1)→1, put(3,3)(淘汰键 2), get(2)→-1, get(3)→3, put(4,4)(淘汰键 1), get(1)→-1, get(3)→3, get(4)→4。所有断言必须通过。
提示
若任一断言失败,请复查淘汰顺序——最近 get/put 的键不应被先淘汰。
自己动手试试
你学到了什么
你组合两种数据结构以在一个真实抽象上实现 O(1) 操作——LRU 缓存用于 CPU 缓存、浏览器缓存、Redis 及许多数据库。
相关资源
相关术语
新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。
- 缓存
近期数据的快速存储。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。