LeetCode 146. LRU 缓存
题目描述
题意分析
实现一个最多保存
capacity个键值对的缓存。get(key)在键存在时返回它的值，不存在时返回-1；put(key, value)在键已存在时更新值，不存在时新增键值对。新增导致容量超限时，删除最久没有被使用的那一项。LRU 的“最近使用”包括成功读取、更新已有键和新增键；读取一个不存在的键不改变使用顺序。淘汰依据是最后一次使用的先后，而非插入顺序或累计访问次数。
get和put都要求平均 $O(1)$，因此不能每次遍历缓存来查找或决定淘汰谁。
解法：哈希表 + 双向链表
核心思路
[!blue]
缓存需要同时维护两种信息：根据键快速找到数据，以及知道谁最久没有使用。哈希表保存
key → Node，解决按键定位；双向链表保存这些节点的使用顺序，越靠头部越新，越靠尾部越旧。两者引用同一批节点，哈希表找到节点后，可以直接调整它在链表中的位置。选择双向链表，是因为访问的节点可能位于中间。已知节点后，只需让它的前驱跳过它、让它的后继接回前驱，就能在常数时间内摘下该节点；随后把它插到头部，表示刚刚使用过。单向链表无法直接找到前驱，数组中的移动则可能牵动许多元素，都不适合这里频繁更新顺序的要求。
get命中时，将节点移到头部并返回值；put更新已有键时，修改同一个节点的值并移到头部，缓存项数不变。新增键时，创建节点，同时加入哈希表和链表头部。只有新增才可能超出容量，此时尾部节点就是最久未使用项，直接删除它即可，无需比较时间戳或扫描整条链表。每个节点既存
value也存key。读取时从键定位节点；淘汰时方向相反，先从链表尾部拿到节点，再用其中的键删除哈希表记录。每次插入和淘汰都必须同步维护两处，保证哈希表能查到的节点恰好就是链表中保留的缓存项。
head、tail是不存实际数据的哨兵，初始直接相连。最新节点始终是head.next，最旧节点始终是tail.prev；真实节点两侧都有邻居，因此空缓存、首节点、尾节点都能使用同一套摘除和插入操作。移动节点只改变使用顺序，不创建新节点，也不增加缓存项数。
解题步骤
- 初始化哈希表、容量和两个哨兵，连接
head.next = tail、tail.prev = head。- 写出摘除节点的
remove与头部插入的addToHead，再用二者组成moveToHead。get未命中直接返回-1；命中则移到头部，再返回节点值。put已有键时，更新原节点的值并移到头部；新键则创建节点，同时加入哈希表与链表。- 新增后若超过容量，摘除
tail.prev，并从哈希表删除它的键。
代码实现
class LRUCache {
private static class Node {
int key;
int value;
Node prev;
Node next;
Node() {}
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Map<Integer, Node> cache = new HashMap<>();
private final Node head = new Node();
private final Node tail = new Node();
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 oldest = tail.prev;
remove(oldest);
cache.remove(oldest.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;
}
}
type Node struct {
key, value int
prev, next *Node
}
type LRUCache struct {
capacity int
cache map[int]*Node
head, tail *Node
}
func Constructor(capacity int) LRUCache {
head, tail := &Node{}, &Node{}
head.next, tail.prev = tail, head
return LRUCache{capacity: capacity, cache: map[int]*Node{}, head: head, tail: tail}
}
func (c *LRUCache) Get(key int) int {
node, ok := c.cache[key]
if !ok {
return -1
}
c.moveToHead(node)
return node.value
}
func (c *LRUCache) Put(key, value int) {
if node, ok := c.cache[key]; ok {
node.value = value
c.moveToHead(node)
return
}
node := &Node{key: key, value: value}
c.cache[key] = node
c.addToHead(node)
if len(c.cache) > c.capacity {
oldest := c.tail.prev
c.remove(oldest)
delete(c.cache, oldest.key)
}
}
func (c *LRUCache) moveToHead(node *Node) {
c.remove(node)
c.addToHead(node)
}
func (c *LRUCache) addToHead(node *Node) {
node.prev = c.head
node.next = c.head.next
c.head.next.prev = node
c.head.next = node
}
func (c *LRUCache) remove(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev
}
复杂度分析
- 时间复杂度：
get、put均为平均 $O(1)$。哈希表平均常数时间查找，链表每次只修改固定数量的指针。- 空间复杂度：$O(capacity)$，哈希表和链表保存同一批缓存节点，两个哨兵只占常数空间。
关键点总结
[!green]
- 定位与顺序分工明确：哈希表保存节点引用，链表保存使用顺序；淘汰前无需遍历。
- 先写指针操作，再写业务分支：摘除只连接节点的前后邻居，头插只修改节点与头部邻居，
get和put复用这些操作。- 使用顺序始终更新：成功读取、修改已有值和新增都会把对应节点放到头部，尾部才会始终代表最久未使用项。
易错点总结
[!yellow]
- 更新不等于新增：已有键必须修改原节点并调整顺序，不增加缓存大小，也不创建重复节点。
- 头插顺序不能乱：先设置
node.next = head.next，再修改原首节点的prev，最后令head.next = node；过早覆盖head.next容易连成自环。- 淘汰要同时改两处：摘除链表节点后还要删除哈希表中的键，否则已淘汰的键仍然可以被查到。
- 命中才调整顺序：
get返回-1时不改变链表；容量为1时，更新同一个键不能误淘汰，新增另一个键才淘汰旧键。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 460. LFU 缓存 | 困难 | 同样需要常数时间定位与更新淘汰顺序，LFU按频率分组，LRU只按最近使用顺序。 |
| 432. 全 O(1) 的数据结构 | 困难 | 同样结合哈希定位与双向链表维护动态顺序，原题维护频次桶，本题维护访问顺序。 |