LeetCode LCR 031. LRU 缓存
目录
题目描述
题意分析
设计一个固定容量的缓存，支持
get(key)与put(key, value)，容量满时淘汰最久未使用的那个键。题目要求两个操作的时间复杂度都是 $O(1)$。「最久未使用」需要精确定义：
get命中和put（无论新增还是覆盖）都算一次使用，都要把该键提升为最近使用；get未命中不算。所以缓存内部必须维护一个按最近使用时间排序的序列，队首是最新的，队尾是最旧的。$O(1)$ 这条约束把可选结构压得很窄。逐条拆需求：按键查值要求哈希；把任意一个已存在的元素「提到最前」要求能在常数时间内把它从当前位置摘下来并插到头部；淘汰要求能在常数时间内拿到最尾的元素。
「从中间摘除一个节点」这件事，只有在已知该节点本身且它有前驱指针时才是 $O(1)$。数组做不到（要搬移），单链表也做不到（拿不到前驱），只有双向链表可以。而「已知该节点」这一前提，恰好可以由哈希表提供——让哈希表的值直接存节点引用。
边界：容量为正数，
get未命中返回 -1；put已存在的键只更新值并提升位置，不增加计数、也不触发淘汰；淘汰时要同时从链表和哈希表里清理，两处漏一处就会内存泄漏或读到脏数据。
解法：哈希表统计状态
核心思路
先看单结构方案的瓶颈。只用哈希表：查值 $O(1)$，但无法知道谁最久未用。哈希表配数组记录使用顺序：提升位置要搬移元素，$O(n)$。哈希表配单链表：能 $O(1)$ 插头，但从中间摘除节点必须先找前驱，仍是 $O(n)$。
于是组合出标准解：哈希表 + 双向链表。链表按最近使用顺序排列，头部最新、尾部最旧；哈希表存「键 → 链表节点引用」，让任意一次查找都能直接跳到对应节点。
核心不变量是：哈希表的键集恰好等于链表中节点的键集，链表长度等于缓存中的元素个数，且链表从头到尾严格按最近使用时间递减排列。每个公开方法返回前都必须恢复这条不变量。
有了这两份结构，三个基本动作都成了常数时间。查找：哈希一次命中拿到节点。提升：靠节点自身的
prev与next把它从原位置摘下（node.prev.next = node.next; node.next.prev = node.prev;），再接到头部。淘汰：直接取尾部节点，摘除并用它的key反查哈希表删除——节点里必须同时存key和val，只存val的话拿到尾节点也不知道该删哈希表里的哪个键，这是本题最容易漏的设计点。链表两端各放一个哨兵节点
head与tail，初始时互相指向。这样任何真实节点都必然有前驱和后继，摘除与插入的四行指针操作不需要任何判空分支，「链表为空」「只有一个元素」「插在头部」全都走同一条路径。
get的逻辑是：查不到返回 -1；查到就把节点提升到头部再返回值。put分两种情况：键已存在则更新值并提升；键不存在则新建节点、插到头部、写入哈希表，然后检查是否超容，超了就摘掉尾部节点并从哈希表里删掉它的键。
解题步骤
- 定义节点：
Node同时保存key、val、prev、next。存key是为了淘汰时能反查哈希表，这一步在写代码之前就要想清楚。- 构造函数建哨兵：
head.next = tail; tail.prev = head;。两个哨兵不存任何真实数据，只用来消灭边界判断；size从 0 开始单独计数（Go 版直接用len(cache)等价）。removeNode：node.prev.next = node.next; node.next.prev = node.prev;。两句成对出现，双向链表任何一次改动都必须同时修好正反两个方向。因为有哨兵，node.prev与node.next永远非空。addToHead：node.next = head.next; node.prev = head; head.next = node; node.next.prev = node;。四句的顺序必须保证「在覆盖掉head.next之前先把它接到node.next上」，否则原来的首节点会丢失。moveToHead= 先摘再插：复用上面两个私有方法，避免把八行指针操作重复写两遍——把原子操作拆成小函数，白板上出错概率显著下降。get：cache.containsKey(key)为假直接返回 -1；否则取节点、moveToHead、返回node.val。返回值必须取自节点，别忘了提升这一步，否则顺序不再反映真实使用情况。put命中分支：更新node.val后moveToHead，不要新增节点也不要动size，覆盖不是插入。put未命中分支：新建节点 → 写哈希 →addToHead→++size→ 若size > capacity则removeTail，用返回的节点的key从哈希表删除，并--size。淘汰必须同时清理链表和哈希表两处。removeTail：取tail.prev（真正的最旧节点，而不是哨兵tail本身），摘除后返回它。以容量 2 的缓存走一遍标准序列。初始链表是
head ↔ tail，哈希为空。
put(1,1)：未命中，新建节点插到头部，链表为head ↔ 1 ↔ tail，哈希{1}，size = 1，未超容。
put(2,2)：未命中，插头，链表为head ↔ 2 ↔ 1 ↔ tail，哈希{1,2}，size = 2，仍未超容。
get(1)：命中节点 1，先摘除（此时链表变成head ↔ 2 ↔ tail），再插到头部得head ↔ 1 ↔ 2 ↔ tail，返回 1。注意这一步把 2 变成了最旧的。
put(3,3)：未命中，插头得head ↔ 3 ↔ 1 ↔ 2 ↔ tail，size = 3超过容量 2，触发淘汰：tail.prev是节点 2，摘除它得head ↔ 3 ↔ 1 ↔ tail，再用它的key = 2删哈希，得{1,3}，size = 2。
get(2)：哈希里没有 2，返回 -1，链表不动。put(4,4)：未命中，插头后超容，淘汰tail.prev即节点 1，链表变成head ↔ 4 ↔ 3 ↔ tail，哈希{3,4}。
get(1)返回 -1；get(3)命中，提升后链表为head ↔ 3 ↔ 4 ↔ tail，返回 3；get(4)命中，提升后为head ↔ 4 ↔ 3 ↔ tail，返回 4。全部结果与 LRU 语义一致。再看覆盖的情形：在
head ↔ 4 ↔ 3 ↔ tail上执行put(3, 30)，命中分支只更新值并提升，链表变成head ↔ 3 ↔ 4 ↔ tail，size仍是 2，不触发淘汰。如果误走了未命中分支，链表里会出现两个 key 为 3 的节点，且会错误淘汰掉 4。
代码实现
class Node {
int key;
int val;
Node prev;
Node next;
Node() {
}
Node(int key, int val) {
this.key = key;
this.val = val;
}
}
class LRUCache {
private Map<Integer, Node> cache = new HashMap<>();
// 头尾哨兵：任何真实节点都有前驱后继，摘除与插入无需判空。
private Node head = new Node();
private Node tail = new Node();
private int capacity;
private int size;
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!cache.containsKey(key)) {
return -1;
}
Node node = cache.get(key);
// 命中也算一次使用，必须提升。
moveToHead(node);
return node.val;
}
public void put(int key, int value) {
if (cache.containsKey(key)) {
// 覆盖不是插入：不新增节点，也不改 size。
Node node = cache.get(key);
node.val = value;
moveToHead(node);
} else {
Node node = new Node(key, value);
cache.put(key, node);
addToHead(node);
++size;
if (size > capacity) {
// 节点里存了 key，才能反查哈希表把它一并删掉。
node = removeTail();
cache.remove(node.key);
--size;
}
}
}
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addToHead(Node node) {
node.next = head.next;
node.prev = head;
head.next = node;
node.next.prev = node;
}
private Node removeTail() {
Node node = tail.prev;
removeNode(node);
return node;
}
}
type node struct {
key, val int
prev, next *node
}
type LRUCache struct {
capacity int
cache map[int]*node
head, tail *node
}
func Constructor(capacity int) LRUCache {
// 头尾哨兵：任何真实节点都有前驱后继，摘除与插入无需判空。
head := new(node)
tail := new(node)
head.next = tail
tail.prev = head
return LRUCache{
capacity: capacity,
cache: make(map[int]*node, capacity),
head: head,
tail: tail,
}
}
func (this *LRUCache) Get(key int) int {
n, ok := this.cache[key]
if !ok {
return -1
}
// 命中也算一次使用，必须提升。
this.moveToFront(n)
return n.val
}
func (this *LRUCache) Put(key int, value int) {
n, ok := this.cache[key]
if ok {
// 覆盖不是插入：不新增节点。
n.val = value
this.moveToFront(n)
return
}
if len(this.cache) == this.capacity {
// 节点里存了 key，才能反查哈希表把它一并删掉。
back := this.tail.prev
this.remove(back)
delete(this.cache, back.key)
}
n = &node{key: key, val: value}
this.pushFront(n)
this.cache[key] = n
}
func (this *LRUCache) moveToFront(n *node) {
this.remove(n)
this.pushFront(n)
}
func (this *LRUCache) remove(n *node) {
n.prev.next = n.next
n.next.prev = n.prev
n.prev = nil
n.next = nil
}
func (this *LRUCache) pushFront(n *node) {
n.prev = this.head
n.next = this.head.next
this.head.next.prev = n
this.head.next = n
}
复杂度分析
- 时间复杂度：
get与put均为平均 $O(1)$。哈希查找是常数时间，摘除与插头各是固定四次指针赋值，淘汰只访问tail.prev一个节点，全程没有任何遍历。- 空间复杂度：$O(capacity)$。哈希表与双向链表各存不超过
capacity个元素，且两者存的是同一批节点的引用而非拷贝，因此常数因子很小，与总的访问次数无关。
关键点总结
- 「$O(1)$ 定位 + $O(1)$ 调整顺序」这对需求，标准答案就是哈希表加双向链表；选双向而非单向的唯一理由是「从中间摘除需要前驱」，面试时要把这句话说出来。
- 链表节点必须同时保存
key和val，否则淘汰时拿到尾节点却无法反查哈希表，会留下永远清不掉的脏键——这是设计阶段就要定好的细节，写到一半才发现往往要推倒重来。- 头尾哨兵把「空链表」「单元素」「插在头部」统一成同一条路径，四行指针操作里一个判空都不需要，这是双向链表题的通用套路。
- 把
removeNode与addToHead拆成独立小函数，moveToHead直接复用，比在两处各抄一遍八行指针操作可靠得多。- 「覆盖已有键」不能走插入分支，它不改变元素个数也不触发淘汰，这条语义区分是判题用例的常客。
- 面试视角：面试官通常会追问「能不能直接用语言自带的有序哈希结构」。可以答 Java 的
LinkedHashMap继承后重写removeEldestEntry三行就能实现，但那等于跳过考点；本题考的就是手写双向链表，所以现场应当手写，同时点明库实现的内部原理与手写版完全一致。
易错点总结
- 节点里不存
key：容量 2 的缓存执行put(1,1)、put(2,2)、put(3,3)时，淘汰拿到尾节点却不知道该删哈希表里的哪个键，get(1)会返回一个已被摘出链表的脏值。get命中后不提升：容量 2 时put(1,1)、put(2,2)、get(1)、put(3,3)会淘汰掉 1 而不是 2，后续get(1)错误返回 -1。put覆盖已有键时走了插入分支：容量 2 时put(1,1)、put(2,2)、put(2,20)会让size变成 3 并淘汰掉 1，而正确行为是缓存里仍有 1 和 2。- 淘汰时只摘链表不删哈希：哈希里残留旧键，
put(1,1)、put(2,2)、put(3,3)后get(1)会命中一个已经脱离链表的节点，返回旧值而非 -1。- 淘汰取的是
tail而不是tail.prev：摘掉的是哨兵本身，链表结构被破坏，之后任何一次addToHead或removeNode都会空指针。addToHead先写head.next = node再接node.next：原首节点丢失，容量 2 时put(1,1)、put(2,2)之后链表里只剩节点 2。removeNode只改一个方向：只写node.prev.next = node.next而漏掉反向那句，反向遍历时链表断裂，淘汰阶段会取到已被摘除的节点。- 构造函数忘记把两个哨兵互相连接：第一次
addToHead访问head.next.prev直接空指针异常。- 用单链表加哈希实现：
moveToHead必须从头遍历找前驱，get退化成 $O(n)$，大量操作的用例会超时。size与实际元素个数不同步：例如淘汰后忘记--size，容量 2 的缓存会在第三次插入后每次都触发淘汰，缓存实际只留得住一个元素。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 146. LRU 缓存 | 中等 | 与本题同题，可直接套用哈希加双向链表 |
| 面试题 16.25. LRU 缓存 | 中等 | 与本题同题，可直接套用 |
| 460. LFU 缓存 | 困难 | 淘汰依据从「最久未用」变成「使用次数最少」，需要按频次再分一层桶 |
| 432. 全 O(1) 的数据结构 | 困难 | 同样用哈希加双向链表，但链表按计数值分组，还要支持查最大最小键 |
| 707. 设计链表 | 中等 | 双向链表增删改的基本功，本题四行指针操作的手感来源 |
| 1472. 设计浏览器历史记录 | 中等 | 同样用双向链表维护访问序列，但需要前进后退而非淘汰 |