LEETCODE 146Medium
LRU 缓存机制
哈希表负责“找得快”，双向链表负责“挪得快”，两个 O(1) 的结构各管一半，拼出完整的 O(1)。
问题拆解
设计一个容量固定的缓存：get 读取，put 写入，容量满时淘汰最久未使用的那条，且两个操作都必须是 O(1)。
只用哈希表，查找是 O(1)，但“谁最久没被用过”得线性扫描；给每条记录挂时间戳再排序，又变成 O(log n)。换个思路：“最近使用”本质是一种顺序，把所有 key 按使用时间串成一条链——每次访问就把节点挪到链头，淘汰时摘掉链尾。要在 O(1) 内完成“从链中间摘下一个节点”，必须是双向链表；要在 O(1) 内“根据 key 找到链上的节点”，必须靠哈希表指向节点。
哈希表解决“在哪”，双向链表解决“多久没用”——单独哪个都做不到，组合起来正好互补。
哈希表 + 双向链表
两个实现细节值得先说：一是给链表加头尾两个哨兵节点，摘除和插入就不用判空；二是链表节点里除了 value 还要存 key，因为淘汰链尾节点时，需要拿它的 key 反过来删掉哈希表里的条目——这是最容易漏的一步。
class LRUCache {
// 手写双向链表节点，head/tail 为哨兵
private static class Node {
int key, value;
Node prev, next;
Node(int key, int value) { this.key = key; this.value = value; }
}
private final int capacity;
private final Map<Integer, Node> map = 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 = map.get(key);
if (node == null) return -1;
moveToFront(node);
return node.value;
}
public void put(int key, int value) {
Node node = map.get(key);
if (node != null) {
node.value = value;
moveToFront(node);
return;
}
if (map.size() == capacity) {
Node last = tail.prev; // 最久未使用的在链尾
detach(last);
map.remove(last.key); // 节点存 key 就是为了这一步
}
node = new Node(key, value);
map.put(key, node);
attachFront(node);
}
private void detach(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void attachFront(Node node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
private void moveToFront(Node node) {
detach(node);
attachFront(node);
}
}
class Node:
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.map = {}
self.head = Node() # 哨兵
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key not in self.map:
return -1
node = self.map[key]
self._move_to_front(node)
return node.value
def put(self, key: int, value: int) -> None:
if key in self.map:
node = self.map[key]
node.value = value
self._move_to_front(node)
return
if len(self.map) == self.capacity:
last = self.tail.prev # 最久未使用的在链尾
self._detach(last)
del self.map[last.key] # 节点存 key 就是为了这一步
node = Node(key, value)
self.map[key] = node
self._attach_front(node)
def _detach(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _attach_front(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def _move_to_front(self, node):
self._detach(node)
self._attach_front(node)
type node struct {
key, value int
prev, next *node
}
type LRUCache struct {
capacity int
m map[int]*node
head, tail *node // 哨兵
}
func Constructor(capacity int) LRUCache {
head, tail := &node{}, &node{}
head.next = tail
tail.prev = head
return LRUCache{capacity: capacity, m: make(map[int]*node), head: head, tail: tail}
}
func (c *LRUCache) Get(key int) int {
n, ok := c.m[key]
if !ok {
return -1
}
c.moveToFront(n)
return n.value
}
func (c *LRUCache) Put(key int, value int) {
if n, ok := c.m[key]; ok {
n.value = value
c.moveToFront(n)
return
}
if len(c.m) == c.capacity {
last := c.tail.prev // 最久未使用的在链尾
c.detach(last)
delete(c.m, last.key) // 节点存 key 就是为了这一步
}
n := &node{key: key, value: value}
c.m[key] = n
c.attachFront(n)
}
func (c *LRUCache) detach(n *node) {
n.prev.next = n.next
n.next.prev = n.prev
}
func (c *LRUCache) attachFront(n *node) {
n.next = c.head.next
n.prev = c.head
c.head.next.prev = n
c.head.next = n
}
func (c *LRUCache) moveToFront(n *node) {
c.detach(n)
c.attachFront(n)
}
use std::collections::HashMap;
// Rust 里用指针手写双向链表会陷入所有权与借用的泥潭（节点互相引用）。
// 这里换一种等价实现：所有节点放进 Vec 当“节点池”，prev/next 存下标，
// 下标 0、1 是头尾哨兵。逻辑和指针版完全一致，只是把指针换成了下标。
struct LRUCache {
capacity: usize,
map: HashMap<i32, usize>, // key -> 节点下标
keys: Vec<i32>,
vals: Vec<i32>,
prev: Vec<usize>,
next: Vec<usize>,
}
impl LRUCache {
fn new(capacity: i32) -> Self {
LRUCache {
capacity: capacity as usize,
map: HashMap::new(),
keys: vec![0, 0], // 0 是头哨兵，1 是尾哨兵
vals: vec![0, 0],
prev: vec![0, 0],
next: vec![1, 1],
}
}
fn detach(&mut self, i: usize) {
let (p, n) = (self.prev[i], self.next[i]);
self.next[p] = n;
self.prev[n] = p;
}
fn attach_front(&mut self, i: usize) {
let first = self.next[0];
self.prev[i] = 0;
self.next[i] = first;
self.next[0] = i;
self.prev[first] = i;
}
fn get(&mut self, key: i32) -> i32 {
match self.map.get(&key) {
Some(&i) => {
self.detach(i);
self.attach_front(i);
self.vals[i]
}
None => -1,
}
}
fn put(&mut self, key: i32, value: i32) {
if let Some(&i) = self.map.get(&key) {
self.vals[i] = value;
self.detach(i);
self.attach_front(i);
return;
}
let i = if self.map.len() == self.capacity {
// 容量满：直接复用最久未使用的节点（尾哨兵的前驱）
let last = self.prev[1];
self.detach(last);
self.map.remove(&self.keys[last]);
self.keys[last] = key;
self.vals[last] = value;
last
} else {
self.keys.push(key);
self.vals.push(value);
self.prev.push(0);
self.next.push(0);
self.keys.len() - 1
};
self.map.insert(key, i);
self.attach_front(i);
}
}
get 和 put 的公共动作被抽成 detach（摘下）和 attachFront（插到链头）两个原子操作，所有场景——命中后提前、更新后提前、新增、淘汰——都由它们拼出来，指针改写只出现在这两处，不容易写错。Rust 版的“节点池”是数组式双向链表：淘汰时直接复用旧节点的槽位，Vec 的长度永远不超过 capacity + 2，行为与指针版逐条对应。
复杂度
| 指标 | 复杂度 | 原因 |
|---|---|---|
| 时间 | O(1) |
get/put 各是一次哈希查找加常数次指针（下标）改写 |
| 空间 | O(capacity) |
哈希表和链表各存至多 capacity 条记录 |
可以迁移的模式
- 需要“O(1) 查找 + O(1) 调整顺序”时，哈希表指向链表节点是标准组合，LFU（460）是它的进阶版；
- 头尾哨兵让插入删除不必讨论空链、头尾等边界，凡手写链表都值得加上；
- 反向删除要留“回程票”：链表节点存 key，才能在淘汰时清掉哈希表条目。
设计题考的不是算法有多巧，而是把每个操作拆成几个原子步骤后，验证每一步都在预算之内。