本文概览：本文以LeetCode经典题目"LRU 缓存"为例，从普通哈希表的局限入手，分析为什么需要额外的数据结构来维护访问顺序，最终引出哈希表 + 双向链表的经典组合，实现 O(1) 时间复杂度的 LRU 缓存

一、题目

LRU缓存题目

二、题目分析

请设计一个数据结构，支持 LRU（Least Recently Used，最近最少使用）缓存机制。要实现的操作：

  • get(key)：如果关键字存在，返回其值；否则返回 -1
  • put(key, value)：如果关键字已经存在，更新它的值；如果不存在则插入。当缓存容量达到上限时，需要删除最久未使用的关键字

目标：get 和 put 都必须在 O(1) 时间内完成

核心难点：普通哈希表能做到 get 和 put 都是 O(1)，但它不记录访问顺序。而 LRU 的核心要求是：当缓存满时，要能立刻知道哪个 key 是最久没用过的，并把它删除

所以问题的关键是：怎么在 O(1) 时间内维护和查询"最久未使用"这个信息？

思路概览

Java实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
class LRUCache {
    class DLNode {
        int key;
        int value;
        DLNode prev;
        DLNode next;

        public DLNode() {
        }

        public DLNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final Map<Integer, DLNode> cache = new HashMap<>();
    private int size;
    private final int capacity;
    private DLNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLNode();
        tail = new DLNode();
        // 初始化头尾节点
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        DLNode node = cache.get(key);
        // 移动到头节点
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            // 更新值
            DLNode node = cache.get(key);
            node.value = value;
            // 移动到头节点
            moveToHead(node);
        } else {
            DLNode node = new DLNode(key, value);
            cache.put(key, node);
            // 新增节点
            addNode(node);
            size++;
            if (size > capacity) {
                DLNode removed = removeTail();   // 获取被移除的节点
                cache.remove(removed.key);       // 用正确的 key 删除 map 条目
            }
        }
    }

    /**
     * 移除尾节点
     */
    private DLNode removeTail() {
        DLNode node = tail.prev;
        node.prev.next = tail;
        tail.prev = node.prev;
        return node;  // 关键：返回被移除的节点
    }

    /**
     * 新增节点
     * @param node 要新增的节点
     */
    private void addNode(DLNode node) {
        // 1. node 的前驱指向 head
        node.prev = head;
        // 2. node 的后继指向原来的第一个真实节点(A)
        node.next = head.next;
        // 3. A 的前驱改为 node
        head.next.prev = node;
        // 4. head 的后继改为 node
        head.next = node;
    }

    /**
     * 移动节点到头节点
     * @param node 要移动的节点
     */
    private void moveToHead(DLNode node) {
        // 1. 让 node 的前驱指向后继
        node.prev.next = node.next;
        // 2. 让后继的前驱指向前驱
        node.next.prev = node.prev;
        // 3. 重新插入到头部
        addNode(node);
    }
}

思路简要说明

  1. 哈希表：负责在 O(1) 时间根据 key 查找到对应的节点

  2. 双向链表：负责维护访问顺序。链表头是"最近访问"，链表尾是"最久未访问"

  3. 访问/更新时把节点移到链表头：每次 get 或 put 命中已有 key，就把对应节点移到链表头部

  4. 超出容量时删除链表尾节点：put 一个新 key 时如果超过容量，就删除链表尾部的节点，代表最久未使用的 key 被淘汰

三、思路详解

起点：为什么普通哈希表不够？

一开始最容易想到的做法就是用哈希表：

  • put(key, value)：直接 map.put(key, value)
  • get(key)：直接 map.get(key)

这两个操作都是 O(1)，速度非常快

但 LRU 加了一个额外要求：缓存有容量上限，超出容量时要删除最久未使用的元素

这就带来问题：普通哈希表根本不记录访问顺序。它只是一个 key → value 的映射，你无法从哈希表中直接查到"哪个 key 最久没被访问过"

如果每次淘汰都要遍历整个哈希表去找最久未访问的元素，那时间复杂度就变成 O(n) 了，不满足 O(1) 的要求

所以我们需要一个额外的结构，专门用来维护访问顺序

为什么用双向链表？

要维护"访问顺序"这个信息，有几个候选结构

方案一：数组

维护一个数组，每次访问就把该元素移到最前面，淘汰时删除最后一个元素

问题：数组删除或移动某个元素后，后面所有元素都要向前移动，操作是 O(n)，完全不满足 O(1) 的要求

方案二：单向链表

单向链表插入头部是 O(1)，但要删除某个中间节点，就必须找到它的前一个节点，而单向链表只能顺着 next 找，需要 O(n) 遍历

方案三：双向链表

双向链表每个节点都有 prev 和 next 两个指针，所以：

  • 删除任意节点：拿到该节点后，直接改它 prev 和 next 的指向即可，O(1)
  • 插入到某个位置：同样只需改指针，O(1)

这正好满足 LRU 的需求。双向链表是唯一能满足 O(1) 位置调整的结构

哈希表 + 双向链表的组合

单独用双向链表也不行——如果只有链表，get(key) 需要遍历链表才能找到对应的节点，也是 O(n)

所以我们需要把哈希表和双向链表结合起来：

  • 哈希表：key → 双向链表节点
  • 双向链表：维护节点顺序

这样：

  • get(key)：通过哈希表 O(1) 拿到节点，然后把节点移到链表头，O(1)
  • put(key, value)：
    • 已存在：通过哈希表 O(1) 拿到节点，更新值，然后移到链表头
    • 不存在：创建新节点，插到链表头，同时哈希表记录映射。如果超过容量，把链表尾节点删除，同时从哈希表中移除对应 key

对应代码中，成员字段就是这两个结构：

1
2
private final Map<Integer, DLNode> cache = new HashMap<>();
private DLNode head, tail;

一个 cache 承担 key 到节点的映射，一个双向链表由 head 和 tail 组成，负责维护访问顺序

链表结构：哨兵头尾节点

为了让代码写起来更简洁，链表使用两个哨兵节点：

  • head 虚拟头节点：真正的第一个节点是 head.next
  • tail 虚拟尾节点：真正的最后一个节点是 tail.prev

结构类似这样：

1
2
3
4
head ⇄ 节点1 ⇄ 节点2 ⇄ 节点3 ⇄ tail

head.next 是最近访问
tail.prev 是最久未访问

在构造函数中完成初始化：

1
2
3
4
head = new DLNode();
tail = new DLNode();
head.next = tail;
tail.prev = head;

为什么用哨兵？

  • 无论插入还是删除，都不用单独判断"要操作的是不是头节点或尾节点"
  • 所有位置的操作都能用统一的代码处理

关键操作一：插入节点到链表头（addNode）

新节点插入或某节点重新变为最近访问时，都需要把节点插到链表头（即 head 后面）

分为四步：

1
2
3
4
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;

图示：

1
2
3
4
5
插入前：
head ⇄ A ⇄ B ⇄ tail

插入 X 到头部：
head ⇄ X ⇄ A ⇄ B ⇄ tail

四步操作严格按顺序进行，最后再让 head.next = node，确保过程中不会断链

关键操作二：删除链表尾节点（removeTail）

当容量满时，链表尾部的节点就是最久未访问的，直接删除并返回：

1
2
3
4
DLNode node = tail.prev;
node.prev.next = tail;
tail.prev = node.prev;
return node;

为什么要返回被删除的节点？

因为哈希表中还保留着 removed.key → 节点 的映射，如果不同步把这个映射从哈希表里删掉，哈希表就会有"死键"

所以 put 中会这样处理：

1
2
DLNode removed = removeTail();
cache.remove(removed.key);

关键操作三：把节点移到链表头（moveToHead）

get 或 put 命中已有 key 时，都要把它对应的节点移到链表头，表示"最近刚访问过"

分成两步：

  • 先把节点从当前位置删除（改 prev 和 next 指针）
  • 再调用 addNode 插入到 head 后面
1
2
3
node.prev.next = node.next;
node.next.prev = node.prev;
addNode(node);
1
2
3
4
5
6
7
8
移动前：
head ⇄ A ⇄ B ⇄ C ⇄ tail

把 B 移到头：
1. 把 B 从当前位置断开：
   head ⇄ A ⇄ C ⇄ tail
2. 调用 addNode(B) 插入到头部：
   head ⇄ B ⇄ A ⇄ C ⇄ tail

两步都是 O(1)

完整流程示例

以容量为 2 的 LRU 缓存为例：

1
2
3
初始：
head ⇄ tail
cache: {}

操作 1：put(1, 1)

  • 不存在，创建新节点 (1,1)
  • 调用 addNode 插入到头
  • 哈希表记录 1 → 节点(1,1)
  • size = 1
1
2
head ⇄ (1,1) ⇄ tail
cache: {1 → (1,1)}

操作 2：put(2, 2)

  • 不存在，创建新节点 (2,2)
  • 调用 addNode 插入到头
  • size = 2
1
2
head ⇄ (2,2) ⇄ (1,1) ⇄ tail
cache: {1 → (1,1), 2 → (2,2)}

操作 3：get(1)

  • 哈希表命中，返回值 1
  • 调用 moveToHead 把 (1,1) 移到链表头
1
2
head ⇄ (1,1) ⇄ (2,2) ⇄ tail
cache: {1 → (1,1), 2 → (2,2)}

操作 4：put(3, 3)

  • 不存在，创建新节点 (3,3)，插入头部
  • size 变成 3，超出容量 2，触发淘汰
  • removeTail 返回被删除的 (2,2)，cache.remove(2)
1
2
head ⇄ (3,3) ⇄ (1,1) ⇄ tail
cache: {1 → (1,1), 3 → (3,3)}

操作 5：get(2)

  • 哈希表没有 2，返回 -1

操作 6：put(4, 4)

  • 不存在，创建新节点 (4,4)，插入头部
  • 超出容量，淘汰链表尾 (1,1)，cache.remove(1)
1
2
head ⇄ (4,4) ⇄ (3,3) ⇄ tail
cache: {3 → (3,3), 4 → (4,4)}

可以看到，通过哈希表 + 双向链表的组合，LRU 需要的所有操作都在 O(1) 时间内完成

一些关键设计说明

  • DLNode 内部同时保存 key 和 value：淘汰链表尾节点时，需要根据 key 从哈希表移除映射。如果节点只有 value，就没法反向找到 key

  • 哨兵头尾节点：addNode 和 moveToHead 都不用判断头尾特殊情况，代码更简洁

  • **moveToHead 复用 addNode**：先断开原位置，再调用 addNode 完成插入，减少重复代码

  • removeTail 返回被移除节点：让 put 可以用 removed.key 同步删除哈希表映射，避免脏数据

  • 时间复杂度：get 和 put 都是 O(1)。哈希表查找 O(1)，双向链表的插入、删除、移动都是 O(1)

  • 空间复杂度：O(capacity)，哈希表和双向链表都最多存 capacity 个节点