LRU缓存机制：哈希表+双向链表实现与缓存淘汰策略深度解析

学链表的时候很多人心里都会打一个问号反转、环检测、合并有序链表这些题刷得再熟好像也只是为了应付笔试链表在真实的系统里真的还有用武之地吗直到我第一次去啃某个缓存组件的源码才反应过来——链表最有排面的应用之一就是LRU 缓存机制Least Recently Used最近最少使用。这道题几乎每一位后端开发都绕不开也是少数能把哈希表、双向链表、容量管理和淘汰策略全部缝在一起考察的综合题。这篇是链表专题的第九期专门把 LRU 讲透不仅讲怎么 AC更讲清楚为什么这个结构被设计成“哈希表 双向链表”、为什么删除节点必须用双链表、为什么缓存淘汰会选择 LRU而不是 FIFO 或者 LFU。不管你是刚学完链表基础的小白还是准备面试的进阶选手这篇文章都值得认真读完。1. 缓存淘汰的底层逻辑为什么是 LRU 而不是 FIFO / LFU1.1 一个你觉得没毛病、却会翻车的淘汰规则先抛开数据结构想想一个最朴素的问题缓存为什么要淘汰因为缓存的空间是有限的。不管你的内存多大也不可能把所有数据都塞进去。所以当缓存满了又来了新数据就必须把某个旧数据请出去。问题来了请谁出去最直觉的做法可能有两种。第一种是“谁来的时间早就淘汰谁”这就是 FIFOFirst In First Out。第二种是“谁最久没被使用就淘汰谁”这就是 LRU。第三种是“谁被用得最少就淘汰谁”这是 LFU。我刚接触缓存的时候觉得 FIFO 才是最简单合理的先进来的人先走排队嘛。但仔细一推演就会发现问题。假设某个热门数据用户每天都要访问它只是在很早期被加载过一次而另一些一次性数据连续被访问了两三分钟后就没用了。按照 FIFO 的规则那个每天都被访问的热门数据会被先淘汰掉而一次性数据却能赖在缓存里这不是纯折腾人吗缓存淘汰的核心目标应该是把“极有可能再次被访问”的数据留下来把“大概率不会再被访问”的数据踢出去。这样命中率才会高缓存才有意义。1.2 LRU 的直觉定义与“时间局部性”LRU 的思路很朴素如果一份数据最近被访问过那么它很可能在接下来的一段时间里还会被访问。反过来如果一份数据很长时间都没人碰那它被再次访问的概率就会越来越低。这个逻辑背后是有理论支撑的叫时间局部性。你可以把它理解成人的阅读习惯最近翻过的那页书大概率会再翻回去看一眼几百年没动过的旧报纸你基本不会去碰。计算机程序也是这个脾气某个变量刚被用完之后附近代码很快又要用它或者同一个热点数据会被反复读取。所以 LRU 的淘汰规则是缓存满时优先淘汰最长时间没有被访问的数据。要注意这里的“访问”包括了读取和写入。只要某个 key 被 get 了或者被 put 了它的“新鲜程度”就重置了成为最近使用的数据。那怎么维护一个稳定的访问顺序呢这里自然会想到一个结构——链表。每次访问一个节点就把节点拎到链表头部头部永远是最新访问的尾部自然就是最久未使用的。淘汰时直接砍掉尾部节点逻辑非常自然。1.3 和 FIFO、LFU 横向对比之后LRU 赢在哪里我们把三种策略放在一张表里对比差异就很明显了淘汰策略淘汰依据优势劣势FIFO进入缓存的时间实现极其简单几乎不需要额外结构完全无视访问频率热门数据可能被一次性数据挤出缓存LRU最近一次的访问时间实现相对简单符合时间局部性偶发的一次访问也会把数据顶到最前面可能发生“缓存污染”LFU一段时间内的访问次数对真正的热门数据很友好需要维护访问计数实现复杂冷门数据可能永远不淘汰也难处理“旧热点”滞留FIFO 的实现虽然简单但它无视了“访问”这个最关键的信号命中率通常会比较差。LFU 看起来很公平但维护每个 key 的频次会带来额外开销而且一个曾经的爆款数据即使现在没人看了只要它的历史访问次数足够高就一直占着缓存位置不挪窝这就破坏了缓存淘汰的“灵活性”。所以 LRU 是两者之间的一个绝佳平衡它足够简单只需要维护“访问顺序”这一条信息同时它又足够有效能快速响应数据热度变化。工程上大量的缓存组件、数据库缓冲池、页面置换算法都以 LRU 为底色说它是“无冕之王”绝不是夸张。2. 数据结构选型推演如何一步步锁定“哈希表 双向链表”2.1 第一个约束get 和 put 都要 O(1)先把数组淘汰掉概念想清楚了接下来就是数据结构设计。这道题最硬的条件是get 和 put 的时间复杂度都必须是 O(1)。先试数组。如果用数组来存数据并维护一个“时间戳”或者“移动标记”来表示新鲜度会出现什么问题数组支持按下标 O(1) 访问但缓存淘汰本质是“删掉一个旧元素”和“插入一个新元素”。数组的删除和插入涉及到元素搬移平均是 O(n)就算你用一个额外变量记录头尾位置也没办法在 O(1) 时间内把中间某个元素摘出来放到头部。所以数组直接出局。那纯链表行不行链表在头尾插入删除是 O(1)但它查找某个 key 只能从头遍历是 O(n)。缓存动辄几万甚至几十万个 key调用一次 get 就要全表扫描这显然不现实。所以我们需要两个能力快速找到元素和快速调整顺序。这两个能力分别指向了两种截然不同的数据结构。2.2 为什么单链表也不行删除操作暴露了“前驱问题”接下来是链表内部的选型——为什么必须是双向链表很多面试题刷多了会背答案但真被追问一句“双向链表和单链表有什么区别”就卡壳了。假设我们用单链表维护访问顺序头部是最新访问尾部是最久未使用。淘汰尾部很容易用一个 tail 指针指向末尾即可。麻烦在于如果你要删除链表中的某个节点你只能从头节点开始遍历找到它的前驱节点才能把前驱的 next 指向它的后继。也就是说虽然“查找到某个 key 对应的节点”可以通过哈希表 O(1) 完成但“把这个节点从链表中删除”这一步单链表做不到 O(1)。而 LRU 的访问操作极其频繁每打一次 get 命中就要把命中的节点挪到头部这就是一次“删除 头插”。如果每次都 O(n)整个缓存就废了。双向链表解决这个问题的方式很优雅每个节点除了 next还保留一个 prev 指针指向自己的前驱。要删除某个节点时不需要遍历直接通过node.prev.next node.next; node.next.prev node.prev;两条语句就完成了。形象地说单链表里的节点只知道“后面是谁”不知道自己“前面是谁”双链表里的每个节点都同时握着前后两个邻居的手想退出队伍只要两边的邻居把手一松就行。2.3 哈希表负责找链表负责排两个结构各司其职到这里方案已经呼之欲出哈希表负责 O(1) 查找 key双向链表负责 O(1) 调整访问顺序。具体分工是这样的哈希表的 key 存业务 keyvalue 存双向链表里的节点引用而不是直接存业务 value。双向链表的每个节点里存key value并且带prev和next指针。链表头部是最近访问的节点链表尾部是最久未使用的节点。当 get 一个 key 时先通过哈希表拿到节点引用然后把这个节点移动到链表头部。当 put 一个新 key 时如果容量已满先删除链表尾节点同时从哈希表中移除对应的 key再把新节点插入链表头部并写入哈希表。这里有一个细节值得单独点出来哈希表的 value 为什么不直接存 value而要存节点引用因为如果只存 value当你需要把某个 key 对应的节点“摘出来移到头部”时你根本不知道这个节点在链表中的位置还得从头遍历去找复杂度又是 O(n)。只有让哈希表直接指向节点对象才能以 O(1) 的成本拿到节点然后利用双向链表的特性完成删除和头插。哈希表和链表是协同关系缺一不可。2.4 哨兵节点让边界条件归零很多人在手写 LRU 时最头疼的就是空链表、只有一个节点、操作头节点尾节点这些边界条件。其实有一个经典解法能把这些边界全抹平哨兵节点dummy head / dummy tail。简单说就是在链表最前面放一个不存实际数据的哑节点dummyHead在最后面也放一个dummyTail。真正的数据节点永远夹在dummyHead和dummyTail之间。这样无论链表是空、只有一个节点、还是有一万个节点你操作的逻辑完全统一头插永远是addToHead(node)插入到dummyHead后面。删尾永远是removeNode(dummyTail.prev)最坏也就是删掉 dummyHead此时链表本来就为空。哨兵节点本身不参与业务逻辑它像两扇固定的大门把“链表为空”和“链表只有一个元素”这类问题一次性消化掉。实现的时候你只需要关心“怎么把节点往头部塞”和“怎么从任意位置把节点摘下来”代码写起来会顺很多。3. 手写实现全过程从 Node 定义到 get / put 主流程3.1 节点设计为什么节点里必须存 key先看最基础的 Node 类。手写 LRU 时节点设计看起来很简单但有同学会踩一个隐蔽的坑只存 value不存 key。class Node { int key; int value; Node prev; Node next; Node(int key, int value) { this.key key; this.value value; } }为什么节点里必须带着 key因为到了“缓存已满要淘汰尾部节点”的时候你不仅要把这个节点从链表上摘掉还要把这个 key 从哈希表里删掉。如果节点里只存 value没有 key你在删除时根本不知道哈希表里该删哪个 key那就只能遍历哈希表来找复杂度直接爆炸。所以Node里必须同时保存 key 和 value。初始化时除了容量和哈希表还要创建两个哨兵节点并让它们互相指向public class MyLRU { private final int capacity; private final MapInteger, Node map new HashMap(); private final Node dummyHead new Node(-1, -1); private final Node dummyTail new Node(-1, -1); public MyLRU(int capacity) { this.capacity capacity; dummyHead.next dummyTail; dummyTail.prev dummyHead; } }3.2 核心工具函数removeNode 与 addToHead手写 LRU 最关键的其实是两个工具函数它们是所有操作的地基。将一个节点从链表中摘除private void removeNode(Node node) { node.prev.next node.next; node.next.prev node.prev; }因为每个节点都有 prev 指针所以只管让它的前驱和后继互相连接即可被摘下来的节点自然就脱离了链表。将一个节点插入到链表头部dummyHead 之后private void addToHead(Node node) { node.prev dummyHead; node.next dummyHead.next; dummyHead.next.prev node; dummyHead.next node; }四个赋值动作顺序不能乱。先设置好新节点的前后指针再修改原头部节点的 prev最后把 dummyHead.next 指向新节点。如果先改了dummyHead.next再去拿原来的头部节点就晚了。有了这两个工具函数“把某个节点移动到头部”就变成一句组合private void moveToHead(Node node) { removeNode(node); addToHead(node); }这里有一个小技巧删除和插入必须是两个独立的小动作不要在代码里内联展开否则很容易在指针赋值顺序上翻车。封装成函数之后get 和 put 主流程会清爽得多。3.3 get 操作一次命中引发的位置调整get 的流程是先查哈希表如果没有直接返回 -1如果命中则把这个节点移动到链表头部再返回 value。为什么命中的节点要移动到头部因为“访问”这个动作意味着数据变新鲜了下一次它最可能被用到所以要把它提到最前面。public int get(int key) { Node node map.get(key); if (node null) { return -1; } moveToHead(node); return node.value; }你可能会想只是读取一下为什么要动链表结构动一下会不会有性能损耗事实是LRU 要求我们精确记录“哪次访问发生在后”如果不把命中的节点挪到头部那么刚被访问过的数据可能会因为链表顺序没有更新在下一次淘汰时被误杀。挪动节点是 O(1) 的操作比误杀热点数据带来的损失划算得多。3.4 put 操作更新、插入与淘汰put 的流程相对复杂一点分情况讨论情况一key 已存在。此时只需要把节点的 value 更新成新值然后把节点移动到头部不需要管容量因为 key 已经存在节点个数没变。public void put(int key, int value) { Node node map.get(key); if (node ! null) { node.value value; moveToHead(node); return; } // 接下来是新增 key 的逻辑 }情况二key 不存在且缓存已满。需要先把最久未使用的尾节点去掉注意要先摘节点再删哈希表。为什么先删链表再删 map顺序其实无所谓但逻辑上要保证两者操作的是同一个节点也就是dummyTail.prev。如果缓存容量是 0 呢这种情况在实现里可以直接在构造时判断或者 put 时直接 returnLeetCode 一般不会给到容量为 0 的无效用例但工程上必须防御。public void put(int key, int value) { Node node map.get(key); if (node ! null) { node.value value; moveToHead(node); return; } if (map.size() capacity) { Node removed dummyTail.prev; removeNode(removed); map.remove(removed.key); } Node newNode new Node(key, value); map.put(key, newNode); addToHead(newNode); }情况三key 不存在且容量没满。直接新建节点放入哈希表然后头插到链表中即可。这个流程看起来简单但每一步都有对应的边界场景我把它们整理成一张表场景处理方式get 一个不存在的 key返回 -1链表和哈希表均不需要变动get 一个存在的 key节点移动到链表头部返回 valueput 已存在的 key更新 value节点移动到链表头部put 新 key容量未满创建节点插入头部写入哈希表put 新 key容量已满删除尾节点删除哈希表对应 key再插入新节点容量为 0构造时直接抛异常或 put 时忽略避免空指针3.5 完整代码与验收自测把上面的片段连起来就是一个可以直接跑的完整实现import java.util.HashMap; import java.util.Map; class LRUCache { private static class Node { int key; int value; Node prev; Node next; Node(int key, int value) { this.key key; this.value value; } } private final int capacity; private final MapInteger, Node map new HashMap(); private final Node dummyHead new Node(-1, -1); private final Node dummyTail new Node(-1, -1); public LRUCache(int capacity) { this.capacity capacity; dummyHead.next dummyTail; dummyTail.prev dummyHead; } public int get(int key) { Node node map.get(key); if (node null) { return -1; } moveToHead(node); return node.value; } public void put(int key, int value) { Node node map.get(key); if (node ! null) { node.value value; moveToHead(node); return; } if (map.size() capacity) { Node tail dummyTail.prev; removeNode(tail); map.remove(tail.key); } Node newNode new Node(key, value); map.put(key, newNode); addToHead(newNode); } private void moveToHead(Node node) { removeNode(node); addToHead(node); } private void removeNode(Node node) { node.prev.next node.next; node.next.prev node.prev; } private void addToHead(Node node) { node.prev dummyHead; node.next dummyHead.next; dummyHead.next.prev node; dummyHead.next node; } }自己写完一定要手推几个用例容量为 2依次 put(1,1)、put(2,2)、get(1)、put(3,3)。这个用例会验证你不超过 15 行就能推出正确结果。如果你推出来的结果是 2 被淘汰流程就对了。这也是我每次带新人必考的一个手推用例。4. Java 一行流继承 LinkedHashMap 的实现与一个隐蔽的访问顺序坑4.1 LinkedHashMap 是怎么做出来的如果是 Java 技术栈面试官通常会再多问一句“你知不知道 JDK 自带一个可以当 LRU 用的 Map”答案就是 LinkedHashMap。Java 里的 LinkedHashMap 是在 HashMap 的基础上额外维护了一条双向链表用来记录键值对的顺序。它有两种模式插入顺序模式和访问顺序模式。默认是插入顺序也就是遍历时按 put 的顺序输出但如果构造时把accessOrder设为 true它对链表的调整就会变成每当某个 key 被访问就把它挪到链表尾部。这几乎就是我们手写的 LRU 的“访问时移动节点”逻辑。那为什么 LinkedHashMap 把头部的数据变成最旧的、尾部变成最新的呢这只是它的实现约定——它把最新访问的元素放到最后。反着看尾部就是最新访问头部就是最久未访问。我们做 LRU要么把它内部的双链表反向理解要么借助它的淘汰钩子方法来实现。4.2 三行继承实现与 removeEldestEntryLinkedHashMap 留了一个受保护的方法removeEldestEntry(Map.Entry eldest)每次 put 之后都会自动调用它。默认返回 false表示“永远不淘汰旧数据”。我们只要重写这个方法当 size 超过容量时返回 true它就会自动把双向链表首部的那个元素也就是最久未访问的删掉。所以用 LinkedHashMap 实现 LRU核心代码短到不可思议import java.util.LinkedHashMap; import java.util.Map; class LRUCache extends LinkedHashMapInteger, Integer { private final int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true); this.capacity capacity; } public int get(int key) { Integer value super.get(key); return value null ? -1 : value; } Override protected boolean removeEldestEntry(Map.EntryInteger, Integer eldest) { return size() capacity; } }这里super(capacity, 0.75f, true)的第三个参数就是accessOrdertrue告诉 LinkedHashMap访问顺序模式最近访问的移到末尾。get方法必须调用super.get不能自己加访问标记因为 LinkedHashMap 已经重写了get访问动作会触发内部链表调整。我们只是把get的返回值语义改成“不到返回 -1”。4.3 隐蔽坑点getOrDefault 不会触发访问顺序更新用这个版本写 LeetCode 时很多人会图省事把 get 写成public int get(int key) { return super.getOrDefault(key, -1); }这个写法看起来很优雅但它是错的。为什么因为getOrDefault是HashMap的方法它内部走的是getNode逻辑而并没有调用 LinkedHashMap 为了维护访问顺序而覆写的afterNodeAccess钩子。也就是说你用getOrDefault读取一个 key这个 key 不会被移动到链表末尾访问顺序不会被刷新后续淘汰时它可能被误判成“长期未访问”而提前淘汰。这种 bug 在单测里很容易被漏掉因为小规模数据很难察觉。等你把缓存容量调大、并发压力上来时命中率会莫名地低但代码看起来又毫无问题。所以用 LinkedHashMap 实现 LRU 时get 必须老老实实走super.get然后自己做空值判断。工程上“优雅写法”和“正确写法”打架时优先选正确。4.4 继承 vs 组合 vs 手写从工程到面试的选择很多文章直接给出继承写法但实际工程中我更推荐组合而不是继承内部持有一个 LinkedHashMap 成员变量对外只暴露 get/put 两个方法。继承要小心父子类方法互相覆盖组合的边界清楚得多也方便替换实现。至于面试我建议还是能手写就手写。理由很简单LinkedHashMap 一行流虽然快它只是“结果正确”但面试官想考察的是你对双向链表指针操作、哈希表与链表协同、边界条件容错的理解。你把手写实现讲明白了再加一句“如果 Java 环境可以直接用 LinkedHashMap 的 accessOrder removeEldestEntry 简化”这反而是加分项反之只会背 LinkedHashMap 版本追问一句“为什么用 getOrDefault 不对”就露馅了。5. 面试追问与升级并发、缓存污染与 LFU 那些事5.1 并发环境下的 LRU加锁还是另选方案面试到这里面试官通常会开始往深处挖。第一条就是你的 LRU 是线程安全的吗显然不是。HashMap 在多线程并发 put 时可能死循环老版本或者丢数据双向链表的指针操作在多线程下更是重灾区。那如果要做一个线程安全的 LRU怎么办最简单直接的做法是给 get 和 put 加上锁比如 synchronized 或者 ReentrantLock。代价是同一时刻只有一个线程能操作缓存并发吞吐量上不去。改善的办法是分段锁或者读写锁——get 操作加读锁put 操作加写锁。读多写少的缓存场景里读写锁的表现会好不少。但更现实的做法是很多大流量的中间件并不会用一把粗锁保护整个 LRU而是采用“哈希分片”的思路把缓存分成多个片段每个片段独立维护一个小 LRU根据 key 的哈希值决定它落到哪一片。这样并发操作不同的 key 时它们锁的是不同的片段互不干扰。理解到这一层你就从“会做题”变成了“能设计”。5.2 LRU 的致命弱点顺序扫描导致的缓存污染再来一个经典追问LRU 有没有缺陷有而且很出名缓存污染。想象一个场景你缓存了 100 个 hot key这时候程序做了一次全量扫描顺序读取了 1000 个只读一次的冷数据。每读到一条冷数据它都会被放到链表头部成为“最新访问”。于是那些冷数据会像洪水一样把原本真正热门的 key 从链表尾部挤掉。扫描一结束缓存里全是没人再用的冷数据命中率瞬间跌到谷底。针对这个问题工程上最常见的优化就是“分段 LRU”。把链表分成两个区域不活跃段和活跃段。新数据先进入不活跃段只有快速被二次访问的数据才升级到活跃段。淘汰时优先淘汰不活跃段的尾部。这种设计能有效防止一次性的顺序扫描把热点数据全部冲掉。如果你学过某个知名数据库的缓冲池管理它的内部页面置换算法本质上也是类似的思路。5.3 换个赛道LFU 为什么能解决热度问题接着面试官还可能问既然 LRU 会被冷数据冲击那有没有更好的方案这就引出了 LFULeast Frequently Used最不经常使用。LFU 的核心是“看频率”每个 key 维护一个访问次数淘汰时优先干掉访问次数最少的。它非常适合那些访问频次极度不均匀的场景比如某个商品详情页被疯狂点击无论时间怎么推移它的频次都遥遥领先就不会被偶尔路过的一次访问挤掉。但 LFU 也有自己的问题需要维护频次数据结构复杂新数据刚进来时频次很低很容易被误杀。很多 LFU 实现加了一个“新数据不参与淘汰”的保护期或者引入“衰减”机制让历史频次随着时间流逝逐步减少。面试时你能讲到这一层面试官会知道你真正理解缓存淘汰策略的演进逻辑。5.4 面试官眼中这道题的“评分点”最后总结一下LRU 缓存机制在面试里为什么这么受欢迎因为它可以分层考察面试表现对应能力能写出正确代码逻辑清晰基本功扎实能讲清楚为什么选双向链表 哈希表数据结构选型能力能主动提到哨兵节点、边界条件代码质量意识能说出 LinkedHashMap 与手写实现的差异语言栈熟悉度能延伸到并发、缓存污染、LFU系统设计视野这道题是一个完美的“由浅入深”探针。你停在哪一层你的真实水平基本就暴露在哪一层。这也是我为什么一直强调LRU 看起来是一道中等难度的题却值得反复打磨把它当成一个小型系统设计题来对待。我自己反复写这道题的体会是手写一遍获得的收益远大于看十遍解析。尤其是指针操作那四行赋值只有自己亲手写错几次再对照调试才能真正理解为什么顺序不能乱。如果你正在刷链表专题建议把 LRU 放到最后再练因为它几乎是前面所有链表技巧的集大成者——你会很快发现之前练的头插法、哨兵、双向遍历全都在这里派上了用场。最后分享一个小技巧写完后别急着去跑 OJ先拿笔在纸上按“容量 2、依次 put/get”的用例推演三遍这一步比任何调试器都管用。等逻辑彻底在脑中跑通了LRU 这道“无冕之王”才算真正收入囊中。