如何用哈希表设计一个 LRU 缓存？

简化版

LRU（Least Recently Used，最近最少使用）缓存要求 get 和 put 都是 O(1)，还要能淘汰「最久没被用过」的元素。标准做法是哈希表 + 双向链表：哈希表存 key → 节点，负责 O(1) 定位；双向链表按访问时间排序，最近用的移到头部，淘汰时删尾部。两者配合，查找、移动、删除都是 O(1)。

详细版

为什么要两个结构配合：

只用哈希表：能 O(1) 查，但记不住「谁最久没用」，没法 O(1) 淘汰。
只用双向链表：能 O(1) 从头尾增删、能维护访问顺序，但按 key 查找要 O(n)。
合起来：哈希表管「快速找到节点」，双向链表管「维护使用顺序」，优势互补。

约定：链表头部 = 最近使用，尾部 = 最久未使用。

get(key)：

哈希表没有 → 返回 −1。
有 → 拿到节点，把它移到链表头部（刚用过），返回值。

put(key, value)：

key 已存在 → 更新值，移到头部。
key 不存在 → 新建节点插到头部，存进哈希表；若超过容量，删除尾部节点并从哈希表移除它的 key。

用双向链表是因为删除任意节点要 O(1) 地找到它的前驱，单链表做不到；加头尾哨兵（dummy）节点能免去大量边界判断。

完整版教学

一、把需求拆成两个「O(1) 能力」

LRU 的难点是同时满足两件事，且都要 O(1)：

按 key 快速存取 → 天然是哈希表的活。
维护「最近使用」顺序 + 快速淘汰最久的 → 需要一个能 O(1) 在两端和中间增删的有序结构 → 双向链表。

单独任何一个都做不到，所以答案是「哈希表 + 双向链表」的组合，这是本题的题眼。

二、为什么必须是「双向」链表 + 哨兵

双向：get 命中后要把中间某个节点移到头部，涉及「删除这个节点」。删除节点必须改它前驱的 next，单链表拿不到前驱（要 O(n) 找），双向链表有 prev 指针，O(1) 搞定。
哨兵节点（dummy head / dummy tail）：在真实头尾各放一个不存数据的假节点，这样插入头部、删除尾部时前后都保证有节点，不用反复判 null，代码干净不易错。

三、参考实现（Java）

class LRUCache {
    class Node { int key, val; Node prev, next; Node(int k,int v){key=k;val=v;} }
    private final int cap;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0,0), tail = new Node(0,0); // 哨兵

    public LRUCache(int capacity) {
        cap = capacity;
        head.next = tail; tail.prev = head;   // 空链表：head <-> tail
    }
    public int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;
        moveToHead(n);                        // 命中即刷新为最近使用
        return n.val;
    }
    public void put(int key, int value) {
        Node n = map.get(key);
        if (n != null) { n.val = value; moveToHead(n); return; }
        n = new Node(key, value);
        map.put(key, n);
        addToHead(n);
        if (map.size() > cap) {               // 超容，淘汰尾部
            Node last = tail.prev;
            remove(last);
            map.remove(last.key);
        }
    }
    private void addToHead(Node n){ n.prev=head; n.next=head.next; head.next.prev=n; head.next=n; }
    private void remove(Node n){ n.prev.next=n.next; n.next.prev=n.prev; }
    private void moveToHead(Node n){ remove(n); addToHead(n); }
}

关键细节：淘汰时要用 last.key 从哈希表里也删掉，别只删链表忘了删哈希表，否则内存泄漏且 key 残留。

四、复杂度分析

get：哈希查 O(1) + 移动节点 O(1) = O(1)。
put：哈希查/插 O(1) + 头部插入 O(1) + 可能的尾部淘汰 O(1) = O(1)。
空间：O(capacity)。

一切 O(1) 正是「哈希定位 + 链表 O(1) 增删」配合的结果。

五、延伸：现成实现与变体

Java LinkedHashMap：本身就是「哈希表 + 双向链表」，构造时传 accessOrder=true 并重写 removeEldestEntry，几行就能实现 LRU，面试可提但通常要求手写底层。
LFU（Least Frequently Used）：按「使用频率」淘汰，比 LRU 复杂，需要频率桶 + 双向链表，常作为进阶追问。

六、常见误区与追问

组件	作用	为什么需要
HashMap	key 到节点的 O(1) 定位	快速找到缓存项
双向链表	维护最近使用顺序	O(1) 移动和删除节点
头尾哨兵	简化边界	统一空链表、删头删尾
capacity	控制容量	超限淘汰最久未使用

head <-> 最近使用 <-> ... <-> 最久未使用 <-> tail
get/put 命中: 移到 head 后
超容量: 删除 tail 前一个节点

记忆钩子：LRU 的难点不是“知道谁最近用过”，而是每次访问后都要 O(1) 更新顺序。

数字例子：容量为 2，执行 put(1), put(2), get(1), put(3)。放入 1、2 后顺序是 2,1；访问 1 后变成 1,2；再放入 3 超容量，要淘汰尾部的 2，最终缓存是 3,1。如果只有 HashMap，就能 O(1) 查找，但无法 O(1) 找到并移动最近使用顺序。

误区：只用 HashMap 就能实现 LRU。 HashMap 不维护访问顺序，无法 O(1) 找到最久未使用项。
误区：单链表也一样好用。 已知节点要从链表中间删除并移动到头部，需要 O(1) 拿前驱，双向链表更合适。
误区：put 已存在 key 时只更新值即可。 访问或更新都表示最近使用，节点也要移动到头部。
追问：为什么要用哨兵节点？ 哨兵让插入头部、删除尾部、删除中间节点都不用频繁判断 null。
追问：Java 现成实现是什么？ 可以用 LinkedHashMap 的 accessOrder 模式加 removeEldestEntry。
追问：LRU 的局限是什么？ 它只看最近访问，不看访问频率；热点扫描可能把真正高频但暂时没访问的数据挤掉。

七、加强记忆

LRU 缓存 = 哈希表 + 双向链表：哈希表 key→节点 做 O(1) 定位，双向链表按使用顺序排列（头=最近、尾=最久）。get/put 命中就把节点移到头部，超容就删尾部并同步从哈希表删 key。用双向链表 + 头尾哨兵是为了 O(1) 删除任意节点、简化边界。Java 可用 LinkedHashMap 现成实现。

简化版

详细版