LRU 缓存：HashMap + 双向链表 = O(1) get/put

一句话结论（30s）

LRU 缓存能做到 get/put 都 O(1)，是因为让 HashMap 和双向链表各管一件事：HashMap 负责 O(1) 快速查到节点，双向链表负责 O(1) 维护访问顺序（最近在头、最久在尾），淘汰时直接从链尾摘掉即可。

核心原理（2min）

两个数据结构的职责分工：

HashMap：key → Node，O(1) 定位任意节点。
双向链表：按”最近使用 → 最久未使用”排序，移动节点是 O(1)。
get/put：把被访问节点移到链表头；容量满时删除链尾节点并同步删 HashMap。
虚拟头尾节点：让头/尾的插入删除无需判空。

底层深入（5-10min）

问题的三个操作

get(key)：返回 value 并标记为”最近使用”
put(key, value)：插入 / 更新，容量满时淘汰”最久未使用”的 key
所有操作 O(1)

数据结构设计

HashMap → O(1) 快速查找。双向链表 → O(1) 移动节点。

HashMap<Integer, Node>    双向链表 (最近 → 最久)
  key → Node               head → N1 → N2 → ... → Nk → tail
                            (最近)                    (最久)

每次 get 或 put 时，将节点移到链表头部（标记为最近使用）。淘汰时，从链尾删除最久未使用的节点，同时从 HashMap 中删除。

💭 思考：看到什么信号该想到”HashMap + 链表”这种组合？——题目要的是三个 O(1)：get 定位 O(1)、put 移动 O(1)、淘汰最久 O(1)。拆开看，“按 key 立刻找到节点”是哈希表的活，“维护一条有序序列并支持任意位置 O(1) 删除”是链表的活，单靠任何一个都缺一半。所以看到”既要随机查、又要维护顺序”两个诉求同时出现，就基本锁定”哈希 + 链表”的组合拳。

为什么必须是双向链表？

如果单向链表，删除中间节点需要找到其前驱（O(n)），双向链表的 node.prev.next = node.next 是 O(1) 的。怎么想到”让两个结构各管一件事”的？ 因为 O(1) 的两个能力天然分属两处——“按 key 定位”是 HashMap 的强项，“维护顺序 + 任意位置 O(1) 删除”是链表的强项，单独任何一者都做不到，叠加就互补了。

💭 思考：为什么必须”双向”而不是单向？——淘汰操作要删”最久未用”的那个节点，如果它恰好是中间节点，单向链表得从头扫一遍找它的前驱（O(n)），O(1) 就破了。双向链表每个节点自带 prev，删除只需 node.prev.next = node.next，一步到位。反向验证：一旦发现某个操作需要”找前驱”，单向结构就危险了。

虚拟头尾节点

class LRUCache {
    Node head, tail;  // 虚拟节点，不存数据
    
    void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
    
    void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

虚拟头尾让”链表头删除/插入”和”链表尾删除/插入”不需要判空——头尾就摆在那里，添加和删除永远是对虚拟节点之间的”真实节点”操作。不设虚拟节点会怎样？ 删除头或尾时要判 head == null、插入空链表时要单独处理，代码里到处是 if-else；虚拟节点把”边界”变成”中间”，所有操作统一成一套逻辑。

💭 思考：为什么要加虚拟头尾节点？——没有虚拟节点时，删头/删尾要判 head == null、空链表插入要走特殊分支，代码里到处 if-else。加两个不存数据的哨兵后，“空链表”和”只剩一个节点”这些边界全变成”在 head 和 tail 之间插删”，一套 addToHead/removeNode 通吃。看到链表题里 if-else 越写越多，就该想到哨兵节点。

完整实现

class LRUCache {
    Map<Integer, Node> map = new HashMap<>();
    Node head, tail;
    int capacity;
    
    LRUCache(int cap) {
        capacity = cap;
        head = new Node(0, 0); tail = new Node(0, 0);
        head.next = tail; tail.prev = head;
    }
    
    int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        removeNode(node);      // 从链中移除
        addToHead(node);       // 移到链头
        return node.val;
    }
    
    void put(int key, int val) {
        Node node = map.get(key);
        if (node != null) {
            node.val = val;
            removeNode(node);
            addToHead(node);
        } else {
            node = new Node(key, val);
            map.put(key, node);
            addToHead(node);
            if (map.size() > capacity) {
                Node last = tail.prev;
                removeNode(last);
                map.remove(last.key);
            }
        }
    }
}

Java 内置：LinkedHashMap

LinkedHashMap<Integer, Integer> lru = new LinkedHashMap<>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > capacity;  // 自动淘汰
    }
};

第三个参数 accessOrder=true：按访问顺序（而非插入顺序）排序——每次 get/put 都会将被访问节点移到队尾。重写 removeEldestEntry 返回 size() > capacity 时自动淘汰最旧节点。

总结

HashMap + 双向链表 = O(1) get + O(1) put + O(1) 淘汰。这个组合的核心洞察：“O(1) 查”用 HashMap，“O(1) 维护顺序”用双向链表。 两个数据结构各管各的领域，完美互补。

章末提问

为什么单用 HashMap 或单用链表都实现不了 O(1) 的 LRU？ 结论：因为 HashMap 只有定位没有顺序、链表只有顺序没有随机定位；淘汰”最久未用”既要能 O(1) 找到它、又要能 O(1) 摘除它，必须两者配合。
为什么要双向链表而不是单向链表？ 结论：因为删除中间节点需要 O(1) 拿到它的前驱；单向链表得从头遍历找前驱是 O(n)，双向链表通过 prev 指针一步到位。
put 时容量已满，为什么删的是链尾而不是链头？ 结论：因为约定链表头是”最近使用”、链尾是”最久未使用”；淘汰要踢最久没碰的那个，所以删链尾并同步从 HashMap 移除。

LRU缓存——HashMap+双向链表实现O(1)淘汰