链表专题一路写到第九篇前面聊反转、聊环检测、聊合并那些题目更像是练手感和培养指针直觉的基础课。但链表真正的工业级名场面还得看 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 取 valuekey 不存在就返回未命中。put(key, value)写入或更新 key-value。除此之外它还要默默维护一件事容量上限。一旦写入后总条数超过容量就自动淘汰最久未被访问的那条数据。现在把这个需求翻译成数据结构的操作需求第一get 要快。缓存里有十万条数据时get 不能去遍历得一步定位。这直接排除纯数组和纯链表方案——数组靠下标是 O(1)但 key 不是连续整数链表查找是 O(n)十万条数据最坏要遍历十万次。能 O(1) 完成 key 定位的只有哈希表。候选方案查找插入删除维护访问顺序结论纯数组O(n) 扫描O(n) 移动O(n) 移动难不行纯链表O(n) 遍历O(1) 头插O(n) 找前驱可以查询太慢纯哈希表O(1)O(1)O(1)无法记录顺序不行哈希表 双向链表O(1)O(1)O(1)链表天然有序可行第二要知道谁最久没被访问。哈希表做不到它只维护 key 到 value 的映射不记录访问顺序。所以还需要一个能维护先后顺序的结构。第三访问已有数据后它的新鲜度要更新即要从较旧位置挪到最新位置而且挪动要快。数组挪动是 O(n)链表挪动节点是 O(1)——前提是你已经知道节点位置。三条需求一捋答案几乎是唯一的哈希表负责定位链表负责排序。哈希表里存 key 到链表节点的映射链表里的每个节点存一份完整的 key-value。2.2 为什么链表必须是双向的这是我第一次手写 LRU 时踩过的认知误区。我当时想既然只是把节点从中间摘下来挪到头部用单向链表也能做吧但我忽略了一个关键点删除动作发生在 get 命中那一刻我手里只有哈希表返回的那个节点指针没有它的前驱节点。单向链表想删除一个节点必须从头遍历找到它的前驱时间复杂度直接退化为 O(n)。所以必须用双向链表每个节点同时持有 prev 和 next 指针。删除任意节点时直接让 node.prev.next node.nextnode.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 LRUCacheK, V { static class NodeK, V { K key; V value; NodeK, V prev; NodeK, V next; Node() { } Node(K key, V value) { this.key key; this.value value; } } private final int capacity; private final MapK, NodeK, V map; private final NodeK, V head; private final NodeK, 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 本身这是整个设计最关键的决策。如果只存 valueget 之后你没法在 O(1) 时间内找到节点在链表里的位置更新新鲜度就无从谈起。存节点引用才能一步定位到链表节点完成摘除、头插。3.2 get 操作的实现public V get(K key) { NodeK, 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) { NodeK, 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) { NodeK, 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(NodeK, V node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } private void removeNode(NodeK, V node) { node.prev.next node.next; node.next.prev node.prev; } private void moveToHead(NodeK, V node) { removeNode(node); addToHead(node); } private NodeK, V removeTail() { NodeK, 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)。空间节点总数不超过 capacityO(capacity)。写完代码我习惯立刻跑一组手工序列验证。设 capacity 2put(1, A)缓存 [1]put(2, B)缓存 [2, 1]2 在头部1 在尾部get(1)命中1 移到头部缓存 [1, 2]put(3, C)容量满淘汰尾部最久未用的 2缓存 [3, 1]get(2)未命中返回 nullget(1)命中缓存 [1, 3]3 被推到尾部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 就是 tailmap 里查不到任何东西直接返回 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淘汰最久未访问实现简单局部性好会被一次扫描污染LRU-K访问 K 次才进主缓存抗污染能力强需要记录访问历史2Q两个队列先进观察区再晋升实现相对简单参数需要调优ARC动态调整两个队列容量比例自适应不同负载实现复杂LRU-K 的核心思想是访问次数不够 K 次的不允许进入主缓存。第一次访问只放在一个隔离的观察区访问次数达到 K 次之后才晋升到主缓存。这样批量扫描的冷数据根本进不了主缓存污染就被挡在门外了。2Q 本质上是 LRU-2 的工程简化版用两个队列实现第一个队列放首次访问的数据第二个队列放值得信任的数据。数据只有被再次访问才会从第一个队列提升到第二个队列。淘汰时优先淘汰第一个队列的冷数据。ARC 更高级它会动态地根据访问模式调整两个队列的容量比例让缓存能自适应读密集型和扫描密集型的工作负载。这些变体共同说明一件事LRU 不是终点而是一个优秀的思想起点。它抓住了时间局部性这个本质后续的所有改进都是在它的骨架上做更精细的策略调整。6. 扩展思考与我的体验6.1 不同语言里的现成实现回头看我自己手写的这个类你可能发现了它做的事情很多主流语言已经封装好了。Java 的 LinkedHashMap 设计之初就内置了访问顺序模式。构造时传 accessOrdertrue它会自动用双向链表维护访问顺序再配合 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 的理解就真正落地了。