LRU缓存算法：双向链表与哈希表实现O(1)淘汰

链表专题一路写到第九篇，前面聊反转、聊环检测、聊合并，那些题目更像是练手感和培养指针直觉的"基础课"。但链表真正的工业级名场面，还得看 LRU 缓存。LRU 全称 Least Recently Used，中文叫最近最少使用，是缓存系统里最经典、也最普及的淘汰算法，同时也是链表和哈希表这套"组合拳"打得最漂亮的应用场景。我习惯叫它链表应用里的无冕之王——因为它从来不会出现在产品标题里，却默默跑在每一台电脑、每一个服务器、每一部手机里。

CPU 的指令缓存用它，数据库的缓冲池用它，网页静态资源的本地缓存用它，移动端图片加载库的内存层核心也是它。这篇文章，我会从"为什么需要 LRU"开始推导，一步步拆解数据结构选型，然后手写一个完整的 LRU 缓存实现，再把实操中容易踩的坑、并发改造的思路、工程上的真实形态全部交代清楚。如果你刚学完链表基础，想明白"这玩意儿到底在真实工程里能干什么"，看这一篇就够了。

1. 为什么 LRU 是链表应用的无冕之王

1.1 缓存淘汰到底在解决什么问题

任何缓存系统都绕不开一个核心矛盾：容量有限，数据无限。不管内存多大，你都不可能把所有数据全塞进去，所以必然要面对一个选择——缓存满了之后，新数据要进来，到底把谁踢出去？

这个问题在工程上有个专门的名字：缓存淘汰策略。候选人有不少：先进先出、随机淘汰、最近最少使用、最不经常使用……但几十年实践下来，绝大多数场景里大家默认的选择还是 LRU。原因在于 LRU 踩中了一个被反复验证过的规律：时间局部性。一句话解释就是——如果一个数据刚被访问过，那么它很快再被访问的概率也更高。你刚翻过的聊天记录，大概率还会再翻；刚加载完的页面资源，马上返回时大概率还要用。所以 LRU 的逻辑非常朴素：优先淘汰最久没碰过的数据，把最近碰过的留在缓存里。

1.2 为什么说它是"无冕之王"

它不像反转链表、环形链表那样只活在教科书和题目里，而是真实存在于你每天接触的每一层系统中。CPU 缓存行替换、操作系统内存页置换、数据库缓冲池、CDN 边缘节点、移动端内存缓存，把这些系统打开看，底层大多能找到 LRU 或者它的近似变体。

更重要的是，LRU 是一个完美的"组合拳"教学案例。它逼你在一个真实需求里想清楚哈希表和链表各自的能力边界：哈希表负责快，链表负责序，两者一拼，查询、插入、删除、淘汰四个操作全部变成 O(1)。这种"用空间换时间、用两种结构互补"的思路，正是工程系统设计的精髓。我始终觉得，链表专题最后一定要落到 LRU 上，才算是把链表的应用价值讲透了。

2. 先拆设计：为什么必须是"双向链表 + 哈希表"

2.1 从需求倒推数据结构

先别急着写代码，把需求列清楚。一个 LRU 缓存对外只有两个核心方法：

• get(key)：根据 key 取 value，key 不存在就返回未命中。
• put(key, value)：写入或更新 key-value。

除此之外，它还要默默维护一件事：容量上限。一旦写入后总条数超过容量，就自动淘汰"最久未被访问"的那条数据。

现在把这个需求翻译成数据结构的操作需求：

第一，get 要快。缓存里有十万条数据时，get 不能去遍历，得一步定位。这直接排除纯数组和纯链表方案——数组靠下标是 O(1)，但 key 不是连续整数；链表查找是 O(n)，十万条数据最坏要遍历十万次。能 O(1) 完成 key 定位的只有哈希表。

第二，要知道谁最久没被访问。哈希表做不到，它只维护 key 到 value 的映射，不记录访问顺序。所以还需要一个能维护先后顺序的结构。

第三，访问已有数据后，它的"新鲜度"要更新，即要从较旧位置挪到最新位置，而且挪动要快。数组挪动是 O(n)，链表挪动节点是 O(1)——前提是你已经知道节点位置。

三条需求一捋，答案几乎是唯一的：哈希表负责定位，链表负责排序。哈希表里存 key 到链表节点的映射，链表里的每个节点存一份完整的 key-value。

2.2 为什么链表必须是双向的

这是我第一次手写 LRU 时踩过的认知误区。我当时想，既然只是"把节点从中间摘下来挪到头部"，用单向链表也能做吧？但我忽略了一个关键点：删除动作发生在 get 命中那一刻，我手里只有哈希表返回的那个节点指针，没有它的前驱节点。单向链表想删除一个节点，必须从头遍历找到它的前驱，时间复杂度直接退化为 O(n)。

所以必须用双向链表：每个节点同时持有 prev 和 next 指针。删除任意节点时，直接让 node.prev.next = node.next，node.next.prev = node.prev，前后一接，O(1) 摘除。这正是双向链表在工程里最核心的价值——不是为了炫技，而是"删除已知节点"这个需求天然需要前驱指针。

2.3 哨兵节点：省掉一半边界判断

链表操作还有一个老生常谈的痛点：空链表判断。头插要判断 head 是否为空，尾删要判断 tail 是否为空，稍不留神就空指针。LRU 里的头尾都在高频变化，这种判断会出现在每一条路径上，写起来非常烦。

工程上的标准解法是引入哨兵节点。申请两个永远不存真实数据的节点 head 和 tail，初始化时让 head.next = tail、tail.prev = head，这样链表在"空"的状态下也是连着的。所有插入删除都变成纯粹的四条指针操作，完全不用判断空引用。

你可以把它理解成公路上起点和终点的标志桩。路上没有车时，两个桩子也立在原地，所有操作围绕它们展开，就永远不会有"找不到参照物"的问题。这个技巧在写各种链表题时都通用，建议养成习惯。

3. 完整实现：手写一个 LRU 缓存

3.1 节点定义与类骨架

下面用 Java 写一个泛型版本。为了把注意力集中在核心机制上，先做成单线程正确，线程安全放后面单独讨论。

import java.util.HashMap; import java.util.Map; public class LRUCache<K, V> { static class Node<K, V> { K key; V value; Node<K, V> prev; Node<K, V> next; Node() { } Node(K key, V value) { this.key = key; this.value = value; } } private final int capacity; private final Map<K, Node<K, V>> map; private final Node<K, V> head; private final Node<K, V> tail; public LRUCache(int capacity) { this.capacity = Math.max(capacity, 0); this.map = new HashMap<>(); this.head = new Node<>(); this.tail = new Node<>(); head.next = tail; tail.prev = head; } }

几个设计点说明一下。

capacity 用 Math.max 做了一层防御，传入负数时统一当 0 处理，避免后续 put 时越界。哨兵节点在构造器里就初始化好，空链表也满足 head.next == tail、tail.prev == head。

哈希表的值类型存的是 Node 而不是 value 本身，这是整个设计最关键的决策。如果只存 value，get 之后你没法在 O(1) 时间内找到节点在链表里的位置，更新新鲜度就无从谈起。存节点引用，才能一步定位到链表节点，完成摘除、头插。

3.2 get 操作的实现

public V get(K key) { Node<K, V> node = map.get(key); if (node == null) { return null; } moveToHead(node); return node.value; }

逻辑很短，但有两处容易被忽略。

第一，get 命中之后必须把节点移到头部。很多人会想，我只是读一下，为什么要动链表结构？因为 LRU 的"最近使用"既包括写入，也包括读取。读了一次的数据说明现在正热，应该给它更高的保留优先级。如果读了不更新位置，这个缓存实际上退化成了"按写入时间淘汰"，语义就不对了。我在帮别人 review 代码时，这几乎是必抓的点。

第二，未命中返回什么需要约定。返回 null 在业务里有个隐患：如果缓存里确实存了 null 值，就无法区分"不存在"和"值为 null"。通用组件里返回 null 是 JVM 系最常见的习惯，但业务侧最好约定用 Optional 或单独的状态码包裹，避免歧义。

3.3 put 操作的实现

public void put(K key, V value) { Node<K, V> node = map.get(key); if (node != null) { node.value = value; moveToHead(node); return; } node = new Node<>(key, value); map.put(key, node); addToHead(node); if (map.size() > capacity) { Node<K, V> removed = removeTail(); map.remove(removed.key); } }

先说更新分支。如果 key 已存在，只需要更新节点里的 value 值，再移到头部。注意不能 new 一个新节点再链进去，否则旧节点会残留在链表中，导致链表和哈希表各指各的，状态彻底错乱。直接复用同一个节点，保证两个结构始终引用同一个对象。

再说新增分支。节点创建好后，要同时完成两件事：哈希表放入 key 到节点的映射、链表头插入节点。两个操作必须都执行，少一个就是事故。先 map.put 还是先 addToHead 其实无所谓，但一定要在逻辑上把它们看成一个整体。

最后是核心的淘汰逻辑：map.size() 超过 capacity 时，删除 tail.prev 这个最久未使用的节点，同时把它对应的 key 从哈希表删掉。这里最容易犯的错，就是只删链表不删 map。哈希表里残留了指向游离节点的引用，表面看起来缓存没有超容量，内存里却挂着一堆孤立对象等着 GC 背锅。我后面专门用一节讲这个坑。

三个辅助方法也一并给出：

private void addToHead(Node<K, V> node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void removeNode(Node<K, V> node) { node.prev.next = node.next; node.next.prev = node.prev; } private void moveToHead(Node<K, V> node) { removeNode(node); addToHead(node); } private Node<K, V> removeTail() { Node<K, V> node = tail.prev; removeNode(node); return node; }

addToHead 的指针顺序建议固定成四行：先交代 node 自己的 prev 和 next，再改后一个节点的 prev，最后改 head 的 next。如果你先改了 head.next，再拿 head.next.prev 就会拿到 node 自己，指针就全乱了。我早期在这个顺序上栽过跟头，后来给自己立了规矩：任何链表指针操作，先处理孤立节点本身的两端，再处理邻居节点的引用，最后才动头尾指针。

3.4 复杂度分析与手工验证

整个实现的时间复杂度：

• get：一次哈希查询 + 一次链表摘除 + 一次头插，O(1)。
• put：一次哈希查询 + 常数次指针操作 + 可能一次淘汰，O(1)。
• 空间：节点总数不超过 capacity，O(capacity)。

写完代码我习惯立刻跑一组手工序列验证。设 capacity = 2：

1. put(1, A)：缓存 [1]
2. put(2, B)：缓存 [2, 1]，2 在头部，1 在尾部
3. get(1)：命中，1 移到头部，缓存 [1, 2]
4. put(3, C)：容量满，淘汰尾部最久未用的 2，缓存 [3, 1]
5. get(2)：未命中，返回 null
6. get(1)：命中，缓存 [1, 3]，3 被推到尾部
7. put(4, D)：淘汰 3，缓存 [4, 1]

这组序列几乎覆盖了 get 命中、put 新增、put 更新、容量淘汰四个核心场景。建议你跟着在纸上画一遍链表和哈希表的变化过程，比看十遍代码都管用。画完再跑一个测试程序逐个断言结果，正确性就有保障了。

4. 实操路上的坑与排查实录

4.1 哈希表和链表不同步的经典事故

我在第三节提到过：淘汰节点时只做链表删除，忘记 map.remove。这个事故非常隐蔽。代码跑起来看似正常，但运行一段时间后内存开始异常增长；更诡异的是，get 一个已经被淘汰的 key，居然还能返回旧值——因为 map 里还留着节点的引用，节点虽然被摘出链表，但对象还活着，value 也没有被回收。

排查这类问题，我的套路很简单：暴露状态。在类里临时加一个 debug 方法，打印 map.size() 和链表真实长度。链表真实长度要从 head 哨兵沿着 next 遍历到 tail 哨兵计数，不能直接用 map.size() 代替。两个数字一旦不一致，基本可以断定是某条路径只操作了其中一个结构。

LRU 的正确性建立在"哈希表和链表指向同一批节点"这个不变式上，所有逻辑 bug 都能归结为破坏了这个不变式。这个思路可以推广到任何多结构协作的代码里，排查效率会高很多。

4.2 容量边界的三个刁钻场景

容量边界问题在实际使用中经常出现，尤其是把 LRU 封装成通用组件后，调用方会传来各种意想不到的参数。

capacity = 0 时，put 任何 key 都必须立即淘汰自己。我见过一些实现在 addToHead 之前先判断 capacity，直接 return，也见过先插入再淘汰的操作方式。两种都行，但要确保 put(1, A) 之后 get(1) 返回 null，而不是把 0 容量当成无限容量处理。

capacity = 1 时，每次 put 新 key 都会把上一个 key 挤掉。链表里永远只有一个真实节点，你需要确认 head.next.next == tail 这条路径的删除不会把自己删串，也不会出现删除后再访问残留节点的问题。

get 空缓存时，head.next 就是 tail，map 里查不到任何东西，直接返回 null，不能有任何空指针出现。

这三个场景建议直接写进单元测试。尤其是 capacity = 0，正常人写代码时根本不会想到，但一旦做成通用工具，就一定有调用方传 0。

4.3 并发改造的思路与锁的选择

单线程版本很容易，但缓存组件基本都是被多线程共享的。一并发就露馅：两个线程同时 put，都发现容量未满，同时插入；或者一个线程 get 时正在 moveToHead，另一个线程同时淘汰尾部节点，链表直接断成两截。

初级方案是给 get 和 put 都加上 synchronized。简单粗暴，但读多写少的场景里锁竞争会很疼。更麻烦的是，get 本身虽然是读操作，却要修改链表结构，所以没法做成真正意义上的纯读操作。

想提升并发度，工程上有几条路：

• 读写锁：需要 get 拿写锁来修改链表，收益有限。
• 分段锁：按 key 的哈希值把缓存分成若干段，段内独立加锁。代价是全局容量淘汰时要做跨段协调，复杂度高。
• 直接使用现成的并发缓存组件：很多工程库内部把链表分片、锁分离优化得很极致，性能远超自己拼的版本。

我的建议是：学习阶段一定要自己手写，把机制吃透；工程阶段优先用成熟组件，不要重复造轮子。业务代码里能用现成的高质量组件，就不要自己维护一个容易出并发问题的轮子。

4.4 指针错乱的排查方法：轨迹法

链表指针出错，运行时通常抛异常或者在遍历时死循环。我自己排查的经验是不要空想，把"当前节点的 prev 和 next 分别是谁"画出来。

具体做法：写一个临时的 toList() 方法，从 head 哨兵开始沿着 next 走，把所有 key 打印成一条链。跑出 bug 后，把打印出来的链和你预想的链对照，很快就能定位是哪一步指针接错了。

尤其是 addToHead 的四行赋值，一旦顺序颠倒，打印出来的链会出现自环——某个节点的 next 指向了自己。看到自环先别慌，去检查赋值顺序，多半是某一步把本该指向邻居的指针指回了自己。这个技巧我用了很多年，排查链表问题的效率提升非常明显。

5. 真实世界的 LRU：从手写组件到工程实现

5.1 大规模场景下的"近似 LRU"

我手写的这个 LRU 类，在单个进程里管理十几万条数据完全没问题。但到了大规模分布式系统里，精确 LRU 会遇到两个坎：一是每个节点都要维护 prev 和 next 指针，内存开销变大；二是每次访问都要动链表指针，极高并发下锁竞争非常激烈。

所以很多底层系统用的是近似 LRU。比如某主流开源内存数据库，它的淘汰策略不维护严格的全局访问链表，而是采用采样淘汰：每次需要淘汰时，从所有 key 里随机抽一批，比较这批 key 的空闲时间，把其中最久没被访问的那个淘汰掉。

这个策略的聪明之处在于，用抽样代替全局排序，把精确 LRU 的维护成本和内存开销都省掉了，淘汰效果在统计意义上已经很接近理想 LRU。工程实践里"差不多好"往往比"精确最优"更划算，这是 LRU 给我上的第一课。

5.2 移动端图片缓存里的两级 LRU

移动端开发最常见的缓存场景是图片加载。网络图片不能每次都从远端拉，必须做本地缓存，但缓存又不能无限占内存，否则直接内存溢出。

主流的图片加载组件基本都采用两级缓存策略：内存层用 LRU 控制总字节数，磁盘层再用 LRU 控制落盘图片的数量和空间。内存层的 LRU 和我在第三节写的结构几乎一样，只是容量单位不是条数而是总字节数。每次 put 之前先累加字节数，淘汰时持续删尾部节点，直到总字节数降到阈值以下。

这里有个细节：删除节点后要把缓存总字节数减掉对应 value 的字节数。这个"计数器同步"和"map 同步"是同一类问题，漏一次整体就全乱。我在实际开发里见过线上内存缓慢增长，最后定位到的根因就是释放节点时忘了扣减字节数。

5.3 缓存污染与更聪明的变体

精确 LRU 有一个被诟病多年的弱点，叫缓存污染。举个例子：一个数据任务一次性扫描了一百万个不重复的 key，这一百万个 key 会把缓存里原本的热点数据全部挤出去。问题是，这一百万个 key 很可能只被扫描一次，之后再也不碰。等到真正的高频用户回来，需要的热数据已经没了，缓存命中率断崖式下跌。

为了解决这个问题，工业界陆续出现了几个变体：

LRU-K 的核心思想是：访问次数不够 K 次的，不允许进入主缓存。第一次访问只放在一个隔离的观察区，访问次数达到 K 次之后才晋升到主缓存。这样批量扫描的冷数据根本进不了主缓存，污染就被挡在门外了。

2Q 本质上是 LRU-2 的工程简化版，用两个队列实现：第一个队列放首次访问的数据，第二个队列放"值得信任"的数据。数据只有被再次访问，才会从第一个队列提升到第二个队列。淘汰时优先淘汰第一个队列的冷数据。

ARC 更高级，它会动态地根据访问模式调整两个队列的容量比例，让缓存能自适应读密集型和扫描密集型的工作负载。这些变体共同说明一件事：LRU 不是终点，而是一个优秀的思想起点。它抓住了时间局部性这个本质，后续的所有改进都是在它的骨架上做更精细的策略调整。

6. 扩展思考与我的体验

6.1 不同语言里的现成实现

回头看我自己手写的这个类，你可能发现了，它做的事情很多主流语言已经封装好了。

Java 的 LinkedHashMap 设计之初就内置了访问顺序模式。构造时传 accessOrder=true，它会自动用双向链表维护访问顺序；再配合 JDK 预留的 removeEldestEntry 钩子方法，重写这个方法返回 size() > capacity 即可。一个 LRU 缓存可以精简到几十行，底层结构就是我手写的 head/tail 加双向链表的翻版。

Python 标准库同样有 OrderedDict，语义是"记住插入顺序的字典"。每次访问后调用 move_to_end(key) 也能拼出 LRU；更省事的是 functools.lru_cache 装饰器，函数级缓存可以直接用。

不过语言内置版本易用，定制能力有限。一旦需要做过期时间、按字节数淘汰、淘汰回调这些扩展，还是要回到手写这条路上。这也是我建议把基础实现吃透的原因——你只有在需要扩展时才明白底层的每一行在干什么。

6.2 从本地缓存到分布式缓存

再往前走一步，单机 LRU 在分布式系统里只扮演"本地近端缓存"的角色，全局缓存还要考虑一致性哈希、节点间同步、崩溃恢复这些更复杂的问题。我做过一个模拟项目，把 LRU 组件加上过期时间和序列化能力之后，作为每个服务节点的本地二级缓存使用，才真正体会到"算法是内核，工程是外延"这句话。

分布式缓存的细节不是这一篇文章能讲完的，但核心思想不变：越靠近业务侧的数据越热，越热的数据越要优先保留。这也是 LRU 能在任何缓存层反复出现的原因。

6.3 写在最后的实操建议

链表专题写到第九篇，我真心觉得 LRU 是最值得亲手实现三遍的内容。第一遍照着代码抄，理解结构；第二遍关掉代码自己写，卡住了再回头看；第三遍用笔在纸上画链表和哈希表的联动过程。三遍下来，你收获的不只是一个缓存类，而是理解了两个数据结构如何协作解决实际问题的方法论。

我个人的体会是，LRU 之所以成为面试和工程的双重常客，是因为它在一道题里同时考察了：你是否知道哈希表只擅长查、链表只擅长改；你能不能写出无 bug 的指针操作；你想不想得到容量边界和并发竞争这些真实世界的约束。这些都是"代码能跑"和"代码能在生产环境活着"之间的差距。

如果你读到这里，我建议马上做一件事：打开编辑器，把第三节的代码关上，自己从头写一遍。写完跑一下容量边界的用例，再想想如果要给这个类加一个"按字节数淘汰"的功能，需要改动哪里。这一套走完，你对 LRU 的理解就真正落地了。