LeetCode 146. LRU 缓存：哈希表 + 双向链表的经典组合拳

题意与约束

LeetCode 146 是设计类题目的常青树：设计一个 LRU（Least Recently Used，最近最少使用）缓存，容量上限为 capacity，要求 get(key) 与 put(key, value) 都是 O(1) 时间；容量满时写入新键，要淘汰「最久未被使用」的键。所谓使用，既包括读取也包括写入——每次 get 或 put 命中已有键，都把它标记为「刚被使用」。

这道题的现实背景是：缓存的容量永远小于它服务的数据集，淘汰策略必然存在，而 LRU 的直觉依据是时间局部性——刚被访问过的数据，大概率很快会再次被访问。

用一个小例子过一遍流程：容量为 2 的缓存，依次 put(1, a)、put(2, b) 后，使用顺序是 2、1（2 刚用过）；get(1) 之后 1 挪到最新位置，顺序变为 1、2；此时 put(3, c) 触发淘汰，最久未使用的 2 被移出，缓存内容变为 1 和 3。整条流程里不允许出现任何一次 O(n) 的查找或移动。

为什么两个数据结构缺一不可

O(1) 的要求把答案逼向数据结构的组合。逐个审视：只用哈希表可以 O(1) 定位任意键，但哈希表内部无序，淘汰时找不到「最久未使用」的键，除非全表扫描，O(n)。只用链表可以用节点顺序天然维护使用程度（刚用过的放头部，尾部就是淘汰候选），但链表查找是 O(n)；更致命的是，即使知道要删哪个节点，单向链表也拿不到它的前驱——删尾或者把中间节点摘下来挪到头部，都得先走到它前一个节点，又是 O(n)。

组合起来恰好互补：哈希表存 key 到链表节点的映射，负责 O(1) 定位；双向链表负责 O(1) 维护使用顺序。双向是硬要求——拿到节点本身后，node.prev 让我们 O(1) 摘除它，单向链表做不到这一点。

设计细节：哨兵节点

有两个细节能让代码干净一半。第一是头尾哨兵：设立不存数据的 head 与 tail 两个哑节点，真实数据夹在中间。这样「插到最新位置」「删除最旧节点」都不需要判空——新节点永远插在 head 之后，淘汰候选永远是 tail.prev，边界条件全部消失。第二是哈希表里存节点引用而不是值：get 命中后要把该节点摘下挪到头部，如果表里只存值，还得遍历链表找节点，前功尽弃。

参考实现

Python 版（可直接提交）：

class Node:
    __slots__ = ("key", "val", "prev", "next")

    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}                            # key -> node
        self.head, self.tail = Node(), Node()    # 哨兵
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):                     # 从链表摘除
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_front(self, node):                  # 头插，标记「刚使用」
        node.next, node.prev = self.head.next, self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            node = self.map[key]
            node.val = value
            self._remove(node)
            self._add_front(node)
        else:
            if len(self.map) >= self.cap:        # 满容量，淘汰 tail.prev
                lru = self.tail.prev
                self._remove(lru)
                del self.map[lru.key]
            node = Node(key, value)
            self.map[key] = node
            self._add_front(node)

Java 版：

class LRUCache {
    private static class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }

    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;
    }

    private void remove(Node n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    private void addFirst(Node n) {
        n.next = head.next;
        n.prev = head;
        head.next.prev = n;
        head.next = n;
    }

    public int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;
        remove(n);
        addFirst(n);
        return n.val;
    }

    public void put(int key, int value) {
        Node n = map.get(key);
        if (n != null) {
            n.val = value;
            remove(n);
            addFirst(n);
        } else {
            if (map.size() >= capacity) {
                Node lru = tail.prev;
                remove(lru);
                map.remove(lru.key);
            }
            Node fresh = new Node(key, value);
            map.put(key, fresh);
            addFirst(fresh);
        }
    }
}

注意两版实现的节点里都存了 key——淘汰时要从哈希表里删掉对应条目，节点不记 key 就找不回来了。这是这道题最高频的失分点。

实现中的三个易错点

易错一：命中已有键的 put 只更新值、不挪位置。 LRU 里的「使用」包括写入，更新之后它就是最新的键，必须同时执行摘除与头插；只改 val 不动链表，淘汰顺序就会错乱，用例一跑便知。

易错二：淘汰时只删链表、不删哈希表。 残留的 key 仍能查到已被淘汰的节点，缓存出现「幽灵条目」，后续读到过期数据。反过来，节点里不存 key，想删也找不到对应表项——两头必须一起顾到。

易错三：手工处理头尾边界。 容量为 1、链表只剩单节点、被删的恰好是头或尾——这些分支若靠判空逐一处理，代码会膨胀一倍且极易漏。哨兵节点的价值正是把这些边界消灭在结构层面，让任何删除与插入都是同一段代码。

复杂度分析

get 与 put 都只做一次哈希表查询加常数次指针操作，时间复杂度均为 O(1)；空间上哈希表与链表各存一份容量上限内的条目，为 O(capacity)。

延伸三句

其一，LRU 按「多久没用」淘汰，LFU（Least Frequently Used）按「用得多频繁」淘汰：LFU 能扛住偶发的大批量扫描把热数据冲掉的毛病，但要处理频次随时间衰减的问题，实现复杂得多。其二，真实系统里的 Redis 用的不是严格 LRU，而是近似 LRU——每次淘汰时随机采样少量键、从中挑最久未用的删掉，省掉了为全库维护链表的内存开销，工程效果与严格 LRU 相差无几。其三，如果只是「用」而不是「考」，Java 的 LinkedHashMap 就是这个组合的现成实现，构造时传 accessOrder=true 并重写 removeEldestEntry 即可：

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);   // accessOrder=true：按访问顺序排列
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

小结

LRU 缓存是「数据结构组合拳」的教科书案例：哈希表管定位，双向链表管顺序，各补对方的短板；哨兵节点消灭边界判断，节点里回存 key 保障淘汰时能反向删除。这套思想远不止于刷题——从 Redis 的近似 LRU 到操作系统与数据库的各种页面置换，「维护使用顺序加 O(1) 淘汰」是缓存系统永恒的母题。