做LeetCode热题100的时候我会把第146题LRU缓存放在一个特殊的位置。它不是最难的但几乎是最能串起“算法如何落地到工程”的一道题。你只要把LRU搞透后面看Redis内存淘汰、MySQL缓冲池、浏览器缓存策略都会有一种“原来都在同一个套路里”的感觉。这道题在面试里出现频率极高刷题指南里也常年霸榜。但很多人只是背了一套“哈希表双向链表”的模板能默写却说不出为什么。这很亏因为面试官最喜欢顺着“为什么不用数组”“为什么存节点而不是存值”往下追问答不上来反而会暴露底子不牢。我打算按自己实际刷题和做工程缓存的思路把这道题从原理到代码完整拆一遍再补一些踩坑记录和面试追问方向希望能帮你真正吃透它。1. 从一道题讲透LRU先搞懂它解决什么问题1.1 缓存淘汰是个躲不开的话题几乎所有系统都会用缓存。数据库前面挡一层Redis接口前面挡一层本地缓存CPU和内存之间还有各级Cache。缓存的意义就是拿空间换时间把高频访问的数据放在更近、更快的地方。但空间总是有限的Redis内存有上限本地缓存有容量限制一旦存满了就面临一个问题到底把谁踢出去把新数据放进来这个“踢谁”的决策策略就是缓存淘汰策略。LRU就是其中应用最广泛的一种。所以做题的时候别只觉得自己在写一个“类”你写的其实是一个迷你的缓存内核。理解了这层关系再看题目要求感觉会完全不一样。面试里这道题经常被安排在“设计题”类别里考的不是你会不会某个API而是你有没有在真实场景中思考过容量、命中率、并发访问这些因素。LeetCode热题100把它收纳进来就是希望程序员在刷题阶段就建立“数据结构要为业务目标服务”的意识。1.2 LRU到底是什么凭什么它能成为主流LRU全称是Least Recently Used直译过来是“最近最少使用”。这个表述有迷惑性准确理解应该是在一段时间内最久没有被访问过的数据在缓存满时优先被淘汰。它的核心依据是时间局部性。在计算机系统里刚被访问过的数据很可能在接下来一段时间又被访问。比如你写代码时反复读同一个配置项这个配置项短期热度极高而某个冷数据可能一小时前被读了一次之后再也不碰那缓存满的时候淘汰它最划算。对比一下其他策略能看得更清楚策略淘汰依据典型问题适用场景FIFO先进先出进入缓存的时间无法区分热点数据冷门数据也可能长期占用实现极其简单的场景LFU最不经常使用历史访问频率旧热点数据长期占坑新热点难以进入访问模式相对稳定的场景LRU最近最少使用最近访问时间偶发批量扫描可能冲掉热点缓存绝大多数常规业务缓存LFU看似更“合理”但要为每个数据维护访问次数成本更高而且如果一个数据昨天很热、今天降温了它会因为历史计数太高而赖在缓存里不走。LRU只认“最近有没有被用过”实现简单对绝大多数业务的突发热点也够用。这就是它成为主流的根本原因。1.3 先看一眼LeetCode上的最终目标题目要求是一眼能看懂的设计并实现一个LRU缓存数据结构要求get和put操作的平均时间复杂度是O(1)。get时如果key不存在返回-1put时如果key存在就更新值如果不存在就插入如果插入后超出容量则把最久未使用的key淘汰掉。难点就在“平均时间复杂度O(1)”这句话上。如果只要实现LRU效果用数组加标记位也能写但查询要遍历移动要遍历都是O(n)性能完全不行。工程师日常写的缓存组件每一纳秒都很关键O(n)级别的淘汰逻辑在百万QPS场景下就是灾难。所以这道题本质上是在考什么样的数据结构组合能让“查询”“更新”“淘汰”这三件事全部O(1)完成。接下来的一切讨论都是围绕这句话展开的。2. 为什么标准答案偏偏是哈希表加双向链表2.1 数组、队列和单向链表为什么差点意思先试着用直觉设计一个LRU缓存。如果有一个数组每个元素存key、value、访问时间那每次get都要遍历数组找key还要更新访问时间淘汰时又要遍历找最老的时间戳全是O(n)。数据量一大这种写法连玩具都算不上。那用队列行不行队列按访问顺序排队每次访问就把节点提到队尾淘汰队头看起来逻辑通顺。但队列一般只支持从两端操作内部节点发生访问时你没法在规定复杂度内把它“抽出来”再“放到尾部”。这就是典型的“方向对结构不对”。单向链表也有相似问题。你要把某个节点移到头部必须知道它前一个节点是谁但单向链表里想拿前驱只能从头遍历一次移动就是O(n)。很多第一次写这道题的人都会卡在这里。数组、队列、单向链表各自的短板恰恰指向一个结论我需要一种能O(1)按key找到节点的方法还需要一种能O(1)删除任意节点并移动到头部的方法。单靠一种数据结构做不到那就组合使用。2.2 哈希表负责“找得快”链表负责“排得动”把两个数据结构组合在一起问题就化解了。哈希表负责解决“key到节点的定位”链表负责解决“访问顺序的维护”。具体结构是这样的哈希表HashMap的key存题目里的keyvalue存链表节点NodeNode里面是key、value、prev指针、next指针。链表头部表示最近刚访问过的数据链表尾部表示最久没访问过的数据。get的时候先用哈希表O(1)找到节点然后把节点从当前位置摘下来放到链表头部。put的时候如果key已经存在同样更新值并移到头部如果key不存在新建节点放到头部并写入哈希表如果此时容量超了就把链表尾部节点删掉同时把它的key从哈希表里删掉。这套结构里哈希表让“找到某个key对应的节点”变成O(1)双向链表让“删除一个节点”“在头部插入一个节点”也变成O(1)。两个O(1)叠加整体就是O(1)。这就是标准答案的灵魂也是面试官最想听你讲清楚的地方。2.3 三个被问烂的“为什么”为什么用伪头部和伪尾部节点如果链表为空增删节点时要处理很多null判断用两个固定的哑节点把头尾边界“焊死”之后无论链表里有没有真实节点插入和删除的逻辑都长一个样不用判断prev或next是不是空。代码少写一半bug也少一半。为什么哈希表的value存节点而不是存值因为get完之后要移动节点。如果只存值你还得再遍历链表去找对应节点那哈希表就白建了。直接把节点对象存在value里查到的瞬间就拿到了节点引用移动、更新都能立刻操作。为什么必须是双向链表而不是单向链表这个问题最经典。删除一个节点时需要让它的前一个节点的next绕过它。单向链表里拿不到前一个节点只能从头找复杂度退化。双向链表每个节点都存着prev删除当前节点只需O(1)把前后两个节点接上。这些细节不是钻牛角尖它们直接决定了算法能不能满足题目的复杂度要求。我在实际工程中写缓存组件时也沿用了同样的思路因为这些底层逻辑是跨语言的。3. 手写LRU缓存把每个细节落实成代码3.1 数据结构定义和初始化我习惯用Java来写这道题因为在面试中Java的HashMap和LinkedList相关问题是高频顺手就把链表操作也练了。先定义节点类和LRU缓存类class LRUCache { // 双向链表节点 class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() {} public DLinkedNode(int key, int value) { this.key key; this.value value; } } private MapInteger, DLinkedNode cache new HashMap(); private int size; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity) { this.size 0; this.capacity capacity; // 伪头部和伪尾部节点 head new DLinkedNode(); tail new DLinkedNode(); head.next tail; tail.prev head; } }这里有个细节值得单独说初始化时一定让head.next指向tailtail.prev指向head。很多初学者把head和tail分别设置为null结果后面写addToHead、removeNode时到处判空逻辑很容易乱。用伪节点初始化的好处是链表永远不为“空”删除和插入的代码路径统一。3.2 get操作的完整思路和实现get的逻辑分两步查缓存、挪位置。public int get(int key) { DLinkedNode node cache.get(key); if (node null) { return -1; } // 如果 key 存在先通过哈希表定位再移到头部 moveToHead(node); return node.value; }moveToHead做两件事把节点从原位置摘除再插入到头部。摘除操作在双向链表里非常干净private void removeNode(DLinkedNode node) { node.prev.next node.next; node.next.prev node.prev; }插入头部时只需要操作head的next和原头部节点。这里要注意顺序不能先把head.next改了再取原头部private void addToHead(DLinkedNode node) { node.prev head; node.next head.next; head.next.prev node; head.next node; }很多书上会把它简写成三行但我建议新手把四行都写清楚因为改指针的顺序一旦混乱就会出现节点“自指”或者链表断裂的诡异bug。我的习惯是先改新节点的prev和next再改旧节点的引用最后再动head。3.3 put操作的完整思路和实现put比get多几种情况我把完整逻辑拆成四步如果key已存在更新value并把节点移到头部。如果key不存在创建新节点加到头部放入哈希表。size加1。如果size超过capacity删除尾部节点并从哈希表移除对应key。public void put(int key, int value) { DLinkedNode node cache.get(key); if (node ! null) { node.value value; moveToHead(node); return; } // key 不存在创建新节点 DLinkedNode newNode new DLinkedNode(key, value); cache.put(key, newNode); addToHead(newNode); size; if (size capacity) { // 删除尾部节点 DLinkedNode tailNode tail.prev; removeNode(tailNode); cache.remove(tailNode.key); size--; } }有一个常见点是删除尾部节点时应该通过tail.prev拿到真正的尾节点而不是直接操作tail。因为tail是伪节点不存任何真实数据。我见过有人把tail当作数据节点来删结果头尾指针全乱了。删除之后别忘了从哈希表里移除对应的key这一步漏掉整个缓存的数据就错乱了。3.4 完整可运行的Java版本把上面几个方法合到一起就是一个可以直接跑通的完整版本。我强烈建议你拿到代码后自己敲一遍不要复制粘贴。手敲的过程能帮你建立“谁指向谁”的空间感这是光看不练很难得到的。import java.util.HashMap; import java.util.Map; class LRUCache { class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() {} public DLinkedNode(int key, int value) { this.key key; this.value value; } } private MapInteger, DLinkedNode cache new HashMap(); private int size; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity) { this.size 0; this.capacity capacity; head new DLinkedNode(); tail new DLinkedNode(); head.next tail; tail.prev head; } public int get(int key) { DLinkedNode node cache.get(key); if (node null) { return -1; } moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node cache.get(key); if (node ! null) { node.value value; moveToHead(node); return; } DLinkedNode newNode new DLinkedNode(key, value); cache.put(key, newNode); addToHead(newNode); size; if (size capacity) { DLinkedNode tailNode tail.prev; removeNode(tailNode); cache.remove(tailNode.key); size--; } } private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } private void removeNode(DLinkedNode node) { node.prev.next node.next; node.next.prev node.prev; } private void addToHead(DLinkedNode node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } }如果面试时语言选Python思路一模一样只是链表需要自己用类或双端队列实现。我见过用Python的OrderedDict一行字典搞定的版本但作为面试题考官更想看到你亲手构建节点的过程。我自己刷题时两种语言都写过Java版能帮助理解指针Python版则更接近日常脚本的写法。4. 刷题之外工程里的LRU长什么样4.1 库函数解法LinkedHashMap怎么写Java的LinkedHashMap本身就是“哈希表双向链表”的实现它额外维护了插入顺序或访问顺序。只要开启accessOrder并重写removeEldestEntry就能用几行代码实现LRU缓存import java.util.LinkedHashMap; import java.util.Map; class LRUCache extends LinkedHashMapInteger, Integer { private int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true); this.capacity capacity; } public int get(int key) { return super.getOrDefault(key, -1); } public void put(int key, int value) { super.put(key, value); } Override protected boolean removeEldestEntry(Map.EntryInteger, Integer eldest) { return size() capacity; } }这段代码在LeetCode上能跑通看起来轻松但我要提醒一句如果你在面试中直接这么写除非面试官主动问你“有没有更底层的实现”否则最好主动说清楚底层原理。LinkedHashMap的第三个构造函数参数决定了链表维护的是插入顺序还是访问顺序accessOrder为true时才符合LRU语义。很多人背了这段代码却不知道accessOrder的含义一问就露馅。4.2 Redis、MySQL缓存池与LRU的工程变形Redis的过期和内存淘汰里就常用近似LRU算法。它没有为每个key维护精确的全局链表因为那样内存开销太大。Redis的做法是采样从设置了过期时间的key中随机抽取若干个淘汰其中最近最少使用的一个。Redis 4.0后还引入了回收池进一步提升了近似LRU的命中率。理解LeetCode上的精确LRU再看Redis的近似实现你就能明白工程里经常会在“效果”和“成本”之间做取舍。MySQL的Buffer Pool也用到了LRU变体它把链表分成new区和old区。为什么要分因为普通LRU有一个问题一次全表扫描会把大量数据页读入缓冲池这些数据用过一次后大概率不会再被访问却可能把真正的热点数据挤出去。这就是LRU的“缓存污染”问题。MySQL把新读入的数据先放到old区如果被再次访问才晋升到new区从而减少一次性扫描带来的污染。如果你把146题的标准代码和MySQL这种改进型LRU对比一下就会发现核心始终是那套“链表哈希表”的组合变的只是访问策略和节点晋升规则。这也是我建议所有后端工程师反复做这道题的原因。4.3 面试官最爱追问的三个进阶问题第一个追问如果多个线程同时访问你的LRU缓存怎么保证线程安全最简单的回答是在get和put上直接加锁再进一步可以聊ConcurrentHashMap配合锁分段。实际工程中也可以直接用同步方法或读写锁重点是要让对方知道你有并发意识而不是只会写单线程版本。第二个追问为什么Redis不用精确LRU可以从内存角度回答。精确LRU需要每个key维护前后指针和一个全局链表会额外消耗大量内存Redis本身存海量key必须放弃一部分精度换取更低的维护成本。这个问题的潜台词是考察你在资源受限下是否会灵活设计算法。第三个追问如果某段时间内来了大量只访问一次的数据LRU的命中率会怎样这就引出了缓存污染。你可以顺势聊LFU作为对比或者聊MySQL为什么要把LRU分成年老区和年轻区。能把这个话题带出来面试官基本就知道你对缓存体系有整体认知了。5. 高频报错和避坑实录一份速查表5.1 常见错误与排查思路我见过不少人在LeetCode上反复提交这道题错误五花八门但其实高度集中在几个点上。我把它们整理成一个速查表写代码时脑子里的那根弦可以按这张表来检查。错误表现根本原因解决思路提交后出现NullPointerException链表节点为null时仍访问prev或next确保伪头尾节点初始化正确删除节点前判断节点非空容量判断出错缓存溢出先判断容量再决定是否淘汰或漏增减sizeput流程先更新size再检查是否超过capacity淘汰后再减sizeget之后数值对但顺序不对只返回值但没有把节点移到头部get不仅要查哈希表还要调moveToHead更新已有key时链表里出现重复节点put里没有先判断key是否存在直接新建节点put第一步永远是cache.get存在则更新值并移动不存在才新建淘汰后哈希表里还残留旧key删除了链表尾节点但忘记从map中删除removeNode后一定执行cache.remove(tailNode.key)moveToHead后链表断裂遍历异常指针修改顺序错误导致某个节点的next指向自己按“先新后旧”的顺序操作指针写完后用边界数据自测光是“忘了在淘汰时删map的key”这一个错误我在帮同事review代码时就见过好几次。它的隐蔽之处在于前几次put可能不会暴露只有当缓存满了并且重复使用相同key时数据才会开始错乱。刷题时编译器不会提示这种逻辑错误需要靠自查和测试用例兜底。5.2 一类必须记住的边界条件LeetCode的判题系统会覆盖各种边界情况但你自己写测试时更容易漏掉这些capacity等于0的时候put任何key都应该触发淘汰get任何key都应该返回-1。有些实现没有考虑容量为0直接创建节点放入map结果map越来越大逻辑彻底失控。capacity等于1的时候每次put新key旧的key要立即被淘汰。这是最简单的缓存模型用它可以快速验证“新节点进头部、旧节点出尾部”的流程是否正确。连续put同一个key多次每次都算一次访问节点应该被移到头部而不是在链表中产生多个相同key的节点。如果链表中出现了重复key说明put的更新分支没写对。get一个刚被淘汰的key必须返回-1。这个测试能同时验证淘汰时map的删除逻辑和get的取值逻辑。我自己做题时会准备这样一组测试用例直接拼在main方法里跑public static void main(String[] args) { LRUCache lru new LRUCache(2); lru.put(1, 1); lru.put(2, 2); System.out.println(lru.get(1)); // 返回 1 lru.put(3, 3); // 淘汰 key 2 System.out.println(lru.get(2)); // 返回 -1 lru.put(4, 4); // 淘汰 key 1 System.out.println(lru.get(1)); // 返回 -1 System.out.println(lru.get(3)); // 返回 3 System.out.println(lru.get(4)); // 返回 4 }这几行测试覆盖了“访问后提升优先级”“容量触发淘汰”“淘汰后不可访问”三大核心行为能跑通基本就说明代码没大问题。以前我刷LeetCode周赛的时候也喜欢把这种自测用例当成调试工具比干瞪眼看代码猜bug高效得多。再分享一个经验调试链表类题目时不要只依赖print输出因为节点地址满天飞反而不容易看清。更有效的办法是在纸上把head、tail和几个关键节点的指针画出来手动模拟一次get和put。画三轮指针的关系就刻在脑子里了以后写这类代码几乎不会错。我个人刷这道题的体会是第一次独立写出来时我在capacity边界上反复栽了好几次归根结底是没把“map和链表是同一份数据的两套索引”这个认知建立起来。后来我把这道题当作分析其他缓存机制的工具每次看Redis或MySQL的淘汰策略都会回到这个模型上。如果你也想彻底掌握LRU我的建议是不要只看题解而是亲手敲一遍然后试着把get和put的过程讲给身边人听。能讲明白才是真会了。