本文概览本文以LeetCode经典题目LRU 缓存为例从普通哈希表的局限入手分析为什么需要额外的数据结构来维护访问顺序最终引出哈希表 双向链表的经典组合实现 O(1) 时间复杂度的 LRU 缓存一、题目二、题目分析请设计一个数据结构支持 LRULeast Recently Used最近最少使用缓存机制。要实现的操作get(key)如果关键字存在返回其值否则返回 -1put(key, value)如果关键字已经存在更新它的值如果不存在则插入。当缓存容量达到上限时需要删除最久未使用的关键字目标get和put都必须在O(1)时间内完成核心难点普通哈希表能做到get和put都是 O(1)但它不记录访问顺序。而 LRU 的核心要求是当缓存满时要能立刻知道哪个 key 是最久没用过的并把它删除所以问题的关键是怎么在 O(1) 时间内维护和查询最久未使用这个信息思路概览Java实现代码如下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 MapInteger, 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); } }思路简要说明哈希表负责在 O(1) 时间根据key查找到对应的节点双向链表负责维护访问顺序。链表头是最近访问链表尾是最久未访问访问/更新时把节点移到链表头每次get或put命中已有 key就把对应节点移到链表头部超出容量时删除链表尾节点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对应代码中成员字段就是这两个结构private final MapInteger, DLNode cache new HashMap(); private DLNode head, tail;一个cache承担 key 到节点的映射一个双向链表由head和tail组成负责维护访问顺序链表结构哨兵头尾节点为了让代码写起来更简洁链表使用两个哨兵节点head 虚拟头节点真正的第一个节点是head.nexttail 虚拟尾节点真正的最后一个节点是tail.prev结构类似这样head ⇄ 节点1 ⇄ 节点2 ⇄ 节点3 ⇄ tail head.next 是最近访问 tail.prev 是最久未访问在构造函数中完成初始化head new DLNode(); tail new DLNode(); head.next tail; tail.prev head;为什么用哨兵无论插入还是删除都不用单独判断要操作的是不是头节点或尾节点所有位置的操作都能用统一的代码处理关键操作一插入节点到链表头addNode新节点插入或某节点重新变为最近访问时都需要把节点插到链表头即head后面分为四步node.prev head; node.next head.next; head.next.prev node; head.next node;图示插入前 head ⇄ A ⇄ B ⇄ tail 插入 X 到头部 head ⇄ X ⇄ A ⇄ B ⇄ tail四步操作严格按顺序进行最后再让head.next node确保过程中不会断链关键操作二删除链表尾节点removeTail当容量满时链表尾部的节点就是最久未访问的直接删除并返回DLNode node tail.prev; node.prev.next tail; tail.prev node.prev; return node;为什么要返回被删除的节点因为哈希表中还保留着removed.key → 节点的映射如果不同步把这个映射从哈希表里删掉哈希表就会有死键所以put中会这样处理DLNode removed removeTail(); cache.remove(removed.key);关键操作三把节点移到链表头moveToHeadget或put命中已有 key 时都要把它对应的节点移到链表头表示最近刚访问过分成两步先把节点从当前位置删除改 prev 和 next 指针再调用addNode插入到 head 后面node.prev.next node.next; node.next.prev node.prev; addNode(node);移动前 head ⇄ A ⇄ B ⇄ C ⇄ tail 把 B 移到头 1. 把 B 从当前位置断开 head ⇄ A ⇄ C ⇄ tail 2. 调用 addNode(B) 插入到头部 head ⇄ B ⇄ A ⇄ C ⇄ tail两步都是 O(1)完整流程示例以容量为 2 的 LRU 缓存为例初始 head ⇄ tail cache: {}操作 1put(1, 1)不存在创建新节点 (1,1)调用addNode插入到头哈希表记录 1 → 节点(1,1)size 1head ⇄ (1,1) ⇄ tail cache: {1 → (1,1)}操作 2put(2, 2)不存在创建新节点 (2,2)调用addNode插入到头size 2head ⇄ (2,2) ⇄ (1,1) ⇄ tail cache: {1 → (1,1), 2 → (2,2)}操作 3get(1)哈希表命中返回值 1调用moveToHead把 (1,1) 移到链表头head ⇄ (1,1) ⇄ (2,2) ⇄ tail cache: {1 → (1,1), 2 → (2,2)}操作 4put(3, 3)不存在创建新节点 (3,3)插入头部size 变成 3超出容量 2触发淘汰removeTail返回被删除的 (2,2)cache.remove(2)head ⇄ (3,3) ⇄ (1,1) ⇄ tail cache: {1 → (1,1), 3 → (3,3)}操作 5get(2)哈希表没有 2返回 -1操作 6put(4, 4)不存在创建新节点 (4,4)插入头部超出容量淘汰链表尾 (1,1)cache.remove(1)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 个节点