LeetCode 面试题 16.25. LRU 缓存
目录
题目描述
题意分析
要实现一个固定容量的缓存类，对外暴露两个操作：
get(key)返回对应的值，键不存在时返回 -1；put(key, value)写入或更新一个键值对，缓存写满之后再写入新键时，必须淘汰掉「最久未被使用」的那个键。约束里的关键信号是操作次数可以到 $10^5$ 量级，而且题目明确要求两个操作都在平均 $O(1)$ 内完成。这条要求同时封死了两条看起来可行的路：用数组或链表按 key 线性查找是 $O(n)$；给每个条目挂一个「最近访问时间戳」再每次扫描找最小值，同样是 $O(n)$。换句话说，「按 key 定位」和「维护使用顺序」这两件事必须同时是常数时间，任何一件退化成线性都不达标。
还要看清什么算一次「使用」：
get命中算，put写入新键算，put更新已有键同样算。这三种情况都要把对应的键顶到「最近使用」的位置，漏掉任何一种，之后淘汰的都会是错的对象。边界包括：容量为 1 时每写一个新键都要淘汰；
get未命中只能返回 -1 且不得改动任何顺序；更新已有 key 不增加缓存规模，因此不该触发淘汰；被淘汰的 key 必须彻底查不到，不能只从顺序结构里摘掉。
解法：哈希表 + 双向链表
核心思路
LRU 同时需要两种能力：按 key 在 $O(1)$ 时间定位节点，以及在 $O(1)$ 时间更新、淘汰使用顺序。哈希表负责前者，双向链表负责后者：
- 哈希表保存
key -> node，直接定位缓存项。- 链表从头到尾按“最近使用”到“最久未使用”排列。
链表必须是双向的，因为命中的节点可能位于中间，只有同时持有前驱和后继才能常数时间摘除。节点还要保存 key，淘汰尾节点后才能同步删除哈希表条目。
使用两个哨兵
head、tail：真实节点始终位于两者之间，head.next是最新节点，tail.prev是最旧节点。这样头插、摘除和删尾都不需要为空链表或单节点单独分支。全程维持两个不变量：哈希表中的节点集合与链表中的真实节点集合完全一致；链表顺序与最近访问顺序一致。
get命中和put新增、更新都会把节点移到头部；超容量时同时从链表尾部和哈希表删除。因此每次操作后不变量都成立，尾部自然就是应淘汰的 LRU 节点。
解题步骤
- 初始化哈希表和首尾哨兵，并令
head.next = tail、tail.prev = head。get未命中返回 -1；命中则把节点移到头部再返回值。put命中已有 key 时更新值、移到头部并结束，缓存数量不变。- 新 key 创建节点，同时写入哈希表并插到链表头部。
- 若数量超过容量，删除
tail.prev，再用该节点的 key 清理哈希表。容量为 2 时，执行
put(1,1), put(2,2), get(1)后链表顺序为1,2；再执行put(3,3)，尾部 2 被淘汰。若get(1)命中时没有移动节点，这里就会错误淘汰 1。
代码实现
import java.util.HashMap;
import java.util.Map;
class LRUCache {
private final int capacity;
private final Map<Integer, Node> cache = new HashMap<>();
private final Node head = new Node(0, 0);
private final Node tail = new Node(0, 0);
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
if (node != null) {
node.value = value;
moveToHead(node);
return;
}
node = new Node(key, value);
cache.put(key, node);
addToHead(node);
if (cache.size() > capacity) {
Node removed = tail.prev;
remove(removed);
cache.remove(removed.key);
}
}
private void moveToHead(Node node) {
remove(node);
addToHead(node);
}
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private static class Node {
final int key;
int value;
Node prev;
Node next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
}
type LRUCache struct {
capacity int
cache map[int]*lruNode
head *lruNode
tail *lruNode
}
type lruNode struct {
key, value int
prev, next *lruNode
}
func Constructor(capacity int) LRUCache {
head, tail := &lruNode{}, &lruNode{}
head.next = tail
tail.prev = head
return LRUCache{
capacity: capacity,
cache: make(map[int]*lruNode),
head: head,
tail: tail,
}
}
func (cache *LRUCache) Get(key int) int {
node := cache.cache[key]
if node == nil {
return -1
}
cache.moveToHead(node)
return node.value
}
func (cache *LRUCache) Put(key int, value int) {
if node := cache.cache[key]; node != nil {
node.value = value
cache.moveToHead(node)
return
}
node := &lruNode{key: key, value: value}
cache.cache[key] = node
cache.addToHead(node)
if len(cache.cache) > cache.capacity {
removed := cache.tail.prev
cache.remove(removed)
delete(cache.cache, removed.key)
}
}
func (cache *LRUCache) moveToHead(node *lruNode) {
cache.remove(node)
cache.addToHead(node)
}
func (cache *LRUCache) addToHead(node *lruNode) {
node.prev = cache.head
node.next = cache.head.next
cache.head.next.prev = node
cache.head.next = node
}
func (cache *LRUCache) remove(node *lruNode) {
node.prev.next = node.next
node.next.prev = node.prev
}
复杂度分析
- 时间复杂度：
get、put平均都是 $O(1)$。哈希定位、摘链、头插和删尾都只做固定次数操作。- 空间复杂度：$O(capacity)$，哈希表和链表各保存至多
capacity个真实节点。
关键点总结
- 哈希表解决定位，双向链表解决顺序，两个结构引用同一批节点。
get命中、put更新和新增都算一次使用，必须移到头部。- 节点保存 key 是为了删尾时同步清理哈希表。
- 哨兵统一空表、单节点与首尾操作，避免分支和空指针。
- 面试时应先说清两个不变量，再写
remove、addToHead两个基础操作。
易错点总结
get命中后不移动节点，会导致后续淘汰顺序错误。- 更新已有 key 后继续执行新增逻辑，会产生重复节点并错误扩容。
- 淘汰时只断开链表、不删除哈希条目，被淘汰 key 仍会命中。
addToHead的四次赋值顺序错误，可能形成自环或丢失原首节点。- 节点不保存 key，删尾时只能反向扫描哈希表，复杂度退化为 $O(capacity)$。
- 不用双向链表时，删除中间节点需要查找前驱，无法保证 $O(1)$。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 146. LRU 缓存 | 中等 | 哈希表 + 双向链表 |
| LCR 031. LRU 缓存 | 中等 | 哨兵节点消边界 |
| 460. LFU 缓存 | 困难 | 频次分桶淘汰 |
| 432. 全 O(1) 的数据结构 | 困难 | 计数分组链表 |
| 380. O(1) 时间插入、删除和获取随机元素 | 中等 | 数组加下标映射 |
| 1472. 设计浏览器历史记录 | 中等 | 双向链表导航 |