“请手写一个LRU缓存。”这道题我这些年见过太多次了面试官问、笔试考、论坛里讨论几乎每个学数据结构的人迟早都会碰到它。LRULeast Recently Used最近最少使用已经不只是面试题里的常客它是计算机系统里真实存在的底层机制——操作系统页面置换、数据库缓存命中、Redis的内存淘汰、浏览器的回退页面背后都有它的影子。这篇是这个系列的第二篇我就把这个高频数据结构核心知识点彻底拆开算法原理、执行步骤、代码实现、边界场景、踩坑记录一次性讲透。一句话概括LRU的思想当空间不够时优先淘汰最近最久没被访问过的数据。换句话说如果一个数据在最近一段时间内被频繁访问那么它在未来一段时间内被访问的概率也更高——这是时间局部性原理的直观应用。真正落地到代码上需要回答两个问题怎么做到O(1)的访问速度怎么做到O(1)的淘汰删除这篇博文就来逐一解开适合正在准备面试的开发者也适合刚学完链表和哈希表、想看它们怎么组合实战的学生。1. 从朴素到高效为什么最后是哈希表加双向链表1.1 LRU到底在解决什么问题先从手机后台说起想象一下你正在用手机刷应用。微信聊完切到抖音抖音看完又切回微信再点开支付宝付个款。手机系统后台保留着这些应用的状态但内存是有限的不可能把所有用过的应用都留在后台。这时候系统会怎么做它会把最长时间没被重新打开的那个应用关掉保留最近用过的那些。这个策略就是LRU。把这个场景抽象成数据结构模型有一块容量固定的存储空间不断有key进来每个key对应一份数据。当容量满了再有新数据要进来就必须把某份旧数据踢出去——踢谁踢最久没被访问的那个。同时每次get、每次更新都应该把该数据的最近使用时间刷新。这就是LRU的全部逻辑读、写、淘汰三个操作。如果只让你用理论实现很多人第一反应是用数组加时间戳每个数据记录一个lastAccessTime每次访问O(1)更新淘汰时遍历找最小的时间戳O(n)。这个方法能跑但淘汰是O(n)数据量一大就扛不住。更致命的问题是如果数据命中的概率很高每一次get都要维护时间戳后续淘汰还要全表扫描性能很难看。所以LRU的核心难点不是思想而是读要快、写要快、淘汰还要快。三个都快才是这题真正的考点。1.2 为什么选双向链表单向链表缺了什么先拆解需求。要O(1)地找到一个key自然会想到哈希表——这是哈希表最擅长的场景。哈希表里存key和对应的节点引用get时能立刻定位。但淘汰的时候哈希表帮不上忙。哈希表是无序的它不知道谁是最久没被访问的。所以必须有一个有序结构来记录访问的时间顺序。这个有序结构里头部是最新访问的尾部是最久未访问的淘汰时直接删尾部——这就是链表。链表选单向还是双向这是关键抉择。单向链表能O(1)地插入头部但删除任意一个节点时得知道它的前驱节点是谁。问题来了通过哈希表拿到的是节点本身单向链表的节点只有next指针没有prev指针你没法O(1)找到它的前驱只能从头遍历。这一遍历删除就变成O(n)了。双向链表完美解决这个问题——每个节点不仅有next还有prev。删除任意节点时直接执行node.prev.next node.next和node.next.prev node.prev不需要遍历O(1)完成。这就是为什么所有LRU的标准实现都是哈希表加双向链表哈希表负责O(1)查找双向链表负责O(1)删除和O(1)移动。用一张对比表看清各方案的复杂度实现方案查找插入删除按节点淘汰数组 时间戳遍历O(1)O(1)O(1)O(n)单向链表 哈希表O(1)O(1)O(n)需找前驱O(1)删尾部但无法删任意节点双向链表 哈希表O(1)O(1)O(1)O(1)这个复杂度推导过程本身就是面试官想听到的思维路径。很多人背结论说LRU用哈希加链表但说不出为什么不能用单向链表原因就在这里——不是背出来的是算出来的。2. 图解LRU核心数据结构与节点移动全过程2.1 Node节点设计每个元素需要记住什么动手写代码前先把数据结构的形态在脑子里画清楚。每条数据的载体是一个双向链表节点Node它需要保存四个信息key哈希表的键也是淘汰时从哈希表移除的依据value真正的数据值prev指向前一个节点next指向后一个节点整个LRU结构里有两个关键部件一个HashMapInteger, Node负责从key直接定位节点一条双向链表负责维护访问顺序。这里有个工程上面的细节链表的头尾不能是null。最省心的做法是设置两个哨兵节点——伪头节点head和伪尾节点tail。它们不存任何真实数据只是作为边界存在。真正的数据节点都在head和tail之间。结构长这样head - nodeA - nodeB - nodeC - tailhead的下一个节点是最新访问的tail的上一个节点是最久未访问的。为什么要用哨兵节点想象一下如果没有它们当链表为空时插入第一个节点要判断head null删除最后一个节点时也要处理tail null代码里到处是空指针判断。有了哨兵节点链表的插入和删除逻辑永远是一致的不需要分支判断代码简洁且不易出错。2.2 get操作全过程命中、移动、返回执行get(k)时三个步骤用哈希表查k如果不存在直接返回-1如果存在拿到对应的Node节点把这个节点移动到链表头部然后返回它的value为什么get也要移动节点因为访问本身刷新了数据的最近使用时间。刚才还在尾部最久未访问现在被读了它就变成了最近被使用的数据必须提到最前面。举例说明。初始状态map: {A:nodeA, B:nodeB, C:nodeC} list: head - A - B - C - tail执行get(B)后B被访问移动到头部list: head - B - A - C - tail步骤拆开看就是两步先把B从链表中摘下来让A直接接上C再把B插到head的后面。摘和插都是O(1)的指针操作。2.3 put操作三个分支新增、覆盖、淘汰执行put(k, v)时情况分三种情况一k已存在。直接更新该节点的value并把它移动到链表头部。注意这里不需要新建节点也不需要走淘汰逻辑。情况二k不存在且链表未满。新建一个node(k, v)把它插入链表头部同时在map里注册k到node的映射。情况三k不存在但链表已满。先删除链表尾部的节点——它是最久未访问的数据。拿到尾部节点的key从map里把它移除释放空间再执行情况二的操作。这里插一句容易踩坑的地方淘汰的节点必须从map中移除。很多人写代码时只操作了链表忘记同步map结果map里残留着被淘汰节点的引用导致这个key还能被get到逻辑就乱了。链表和哈希表是一体两面的任何一侧的修改都必须同步到另一侧。用图说明淘汰capacity 3 list: head - A - B - C - tail 执行put(D) 第1步插入D到头部list变成 head - D - A - B - C - tail 第2步发现size4 capacity3删除尾部C list变成 head - D - A - B - tail map中同步移除C完美体现了LRU的淘汰规则最久没被访问的C先出局哪怕它曾经被访问过无数次只要最近一段时间没碰它就会被淘汰。3. 手写实现完整Java代码与逐段拆解3.1 直接能跑的完整代码把上面的分析落到代码上。用Java实现一版结构清晰、注释完整可以直接复制运行测试。import java.util.HashMap; import java.util.Map; public 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 head new Node(0, 0); // 伪头节点 private final Node tail new Node(0, 0); // 伪尾节点 private int size; public LRUCache(int capacity) { this.capacity capacity; head.next tail; tail.prev head; } 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; } // 不存在新建节点 Node newNode new Node(key, value); map.put(key, newNode); addToHead(newNode); size; if (size capacity) { // 淘汰尾部最久未使用的节点 Node removed removeTail(); map.remove(removed.key); size--; } } // 将节点插入到链表头部伪头节点之后 private void addToHead(Node node) { node.next head.next; node.prev head; head.next.prev node; head.next node; } // 将节点从链表中摘除 private void removeNode(Node node) { node.prev.next node.next; node.next.prev node.prev; } // 将节点移动到头部 先摘除再插入 private void moveToHead(Node node) { removeNode(node); addToHead(node); } // 删除并返回尾部节点伪尾节点之前那个 private Node removeTail() { Node node tail.prev; removeNode(node); return node; } }这段代码就是LRU的经典实现LeetCode第146题的官方解法也是各种书籍、教程里出现频率最高的版本。运行一下LRUCache cache new LRUCache(2); cache.put(1, 1); cache.put(2, 2); System.out.println(cache.get(1)); // 返回 1 cache.put(3, 3); // 淘汰 key2 System.out.println(cache.get(2)); // 返回 -1 System.out.println(cache.get(3)); // 返回 33.2 最容易写错的addToHead四行指针的顺序问题如果你自己手写过这段代码大概率在addToHead这个函数上卡过壳。就四行代码但顺序错了整个链表就乱了。node.next head.next; // 新节点的next指向原第一个真实节点 node.prev head; // 新节点的prev指向伪头节点 head.next.prev node; // 原第一个真实节点的prev指向新节点 head.next node; // 伪头节点的next指向新节点关键点是必须先让新节点和原第一个真实节点建立联系再去修改head.next。如果反过来先执行head.next node那么原第一个真实节点就失联了——head的next已经变成node你再也拿不到原第一个节点后面两行就没法进行了。可以这样记先处理新节点自己的两个指针next和prev都得指对再处理它相邻两个节点指向它的指针先让后一个节点指过来再让前一个节点指过去。这个顺序是链表插入的通用法则不只是LRU里要用任何双向链表插入操作都遵循同样的规律。3.3 removeNode和moveToHead为什么不需要判空removeNode执行的是标准的双向链表摘除node.prev.next node.next; node.next.prev node.prev;两行代码没有判空。为什么不判空因为哨兵节点的存在链表里任何一个真实数据节点的prev和next都一定不为null——链表的边界是伪头和伪尾它们永远不会被当作真实节点删除也不会被移出链表。moveToHead就是removeNode加addToHead的组合先从老位置摘下来再插到头部。这两步必须连续执行中间不能有其他操作插入。所以我把它们封装成一个方法从调用方来看语义很清晰——这个节点刚刚被访问了把它挪到最新的位置。4. 面试官不会直接告诉你的三个隐藏考点4.1 考点一为什么get和put都是O(1)这道题之所以经典是因为它把三种数据结构的优势组合了起来哈希表O(1)查找、双向链表O(1)插入删除、哨兵节点避免空指针分支。三者缺一不可。面试时回答这个问题的标准表述get哈希表查key O(1)移动节点到头部由两个O(1)指针操作组成整体O(1)put哈希表查key O(1)新增或更新节点O(1)容量满时删除尾部节点O(1)同步map操作O(1)整体O(1)空间复杂度O(capacity)哈希表存capacity个映射链表存capacity个节点注意别说什么均摊O(1)——这个场景里所有操作都是严格的O(1)不需要分摊。4.2 考点二map里存Node还是Node里存map有同学会问为什么哈希表是MapInteger, Node而不是把Node作为key直接存你可以试想一下如果定义MapNode, Integer或者干脆把Node当key会有什么问题。Node是一个自定义类如果你没有重写equals和hashCode方法那么哈希表比较节点时比较的是内存地址。每次新建一个Node它的内存地址都不一样即使key值相同查找时也匹配不上哈希表形同虚设。所以这里的设计原则是哈希表的key一定要是业务意义上的keyvalue才是存储的载体节点。还有一个隐藏细节淘汰时为什么能通过removed.key从map中移除因为Node节点里保存了key字段。如果Node里不存key只存value淘汰的时候你拿到了Node却不知道它在map里对应的key是什么就没法同步清理map——那整个缓存就垮了。所以Node里的key字段不是冗余它是链表和map之间的桥梁。4.3 考点三手写实现没考虑并发但你要知道答案上面这份代码不是线程安全的。两个线程同时调用put可能导致链表被破坏、size计数不准确、map和链表数据不一致。面试时经常会追问如果并发访问怎么办最直接的答案是给get和put加上synchronized关键字。这属于粗粒度锁实现简单但并发性能很差所有操作串行化。实际生产环境如果追求性能会用读写锁——读操作不互斥写操作互斥因为get只读不改且get有修改链表的操作这个要看你对读的定义了或者直接使用JDK的ConcurrentHashMap配合额外的同步控制。另一个思路是使用LinkedHashMap的线程安全包装这个下一节详细说。更进一步的方案在Java生态里可以直接用Caffeine、Guava Cache这些本地缓存库它们内部实现了LRU/LFU等多种淘汰策略还支持过期时间、刷新机制比手写强得多。但面试时把这些方案说出来就够了不需要真去实现一个并发LRU。5. LinkedHashMap三行代码实现以及生产环境的真实选择5.1 三行代码背后发生了什么JDK里的LinkedHashMap本身就是一个哈希表双向链表的组合它默认按插入顺序维护链表。但它提供了一个构造参数accessOrder当设为true时链表顺序会变成按访问顺序维护——每次get到一个key这个key对应的节点就会被移动到链表尾部。利用这个特性LRU缓存可以这么写class LRUCache extends LinkedHashMapInteger, Integer { private final int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true); this.capacity capacity; } Override protected boolean removeEldestEntry(Map.EntryInteger, Integer eldest) { return size() capacity; } }三行核心逻辑但背后有不少细节。super(capacity, 0.75f, true)三个参数分别是初始容量、负载因子、accessOrder。置true之后每次get或put操作都会触发内部的afterNodeAccess回调把刚访问的节点挪到链表尾部。removeEldestEntry是插入完成后的钩子方法返回true时就删除链表头部的节点——注意在LinkedHashMap的实现里链表头部是最久未访问的尾部是最近访问的正好和手写版本相反。这个方法能不能用能生产环境里如果不想引入第三方库LinkedHashMap版LRU是完全可行的。但它的淘汰粒度只支持容量超过上限就删一个如果你需要按时间过期、按key维度设置不同的淘汰策略它就不够灵活了。5.2 为什么面试题不让你直接写LinkedHashMap面试官让你手写LRU不是不知道有LinkedHashMap恰恰相反他是在考察你对底层机制的理解。直接甩一个removeEldestEntry重写上去说明你只知道能用而不知道为什么这样能用。手写版本考察的是对哈希表和链表两个数据结构的理解深度对指针操作边界条件的掌控能力对复杂度的推导能力这三项才是数据结构和算法面试真正想筛选的能力。LinkedHashMap版本背熟了三分钟就能默写但它不会让你理解为什么哈希加双向链表是O(1)的。我的建议是两版都要会先能手写底层版再用LinkedHashMap做对照验证这样既理解原理又有生产落地方案。5.3 生产环境里选LRU还是LFU没人告诉你的事手写一个LRU容易但在真实系统里选用淘汰策略要考虑的问题远不止缓存容量。LRU有一个经典缺陷——缓存污染。如果一个冷门数据在短时间内被批量访问了一次LRU会把它当成热门数据留在缓存里挤掉真正的热点数据。针对这个场景LFULeast Frequently Used最不经常使用策略更合适它按访问频率淘汰。但LFU也有问题历史高频数据可能永远不被淘汰即使最近已经不热门了。现代缓存库往往用LRU的变体或者LRU和LFU的组合策略来避开这个坑。在Java世界里生产级本地缓存的推荐方案是Caffeine。它内部实现了W-TinyLFU算法结合了LRU和LFU的优势性能非常出色。如果你只是需要一个简单的LRU用LinkedHashMap足够了但如果你的缓存命中率对业务影响很大直接上Caffeine不要浪费时间去优化自己写的LRU——优化空间有限坑倒是一堆。6. 实测验证边界用例与一次真实的踩坑记录6.1 测试用例清单验证LRU的正确性写完代码不能直接扔到一边得用测试用例验证逻辑。我建议至少要覆盖这几类场景测试场景操作序列期望结果基本淘汰put(1,1), put(2,2), get(1), put(3,3), get(2)淘汰key2get(1)返回1get(2)返回-1访问刷新顺序put(1,1), put(2,2), get(1), put(3,3), get(2), get(1)key2被淘汰key1仍存在覆盖已存在keyput(1,1), put(1,2), get(1)返回新值2size不变容量为1put(1,1), put(2,2), get(1), get(2)get(1)返回-1get(2)返回2容量为0或负数new LRUCache(0)不抛异常put任何值立即淘汰这里特别说一下容量为1的边界。容量1时每次put新key链表里只有一个元素新节点插入头部后size变成2超过容量于是删除尾部节点——而尾部节点恰恰就是刚插入的那个新节点。所以put(2,2)之后缓存里没有任何数据。这不是bug这是容量只有1的正确行为。但如果你的代码在put时先淘汰再插入顺序反了就会出现新插入的key反而被删掉了的诡异现象。6.2 一次真实踩坑忘掉map.remove引发的数据错乱最后分享一个我实际调试中踩过的坑。有一次封装LRU测试时我在put里写淘汰逻辑链表操作全部正确size也减了但忘了执行map.remove(removed.key)。结果是什么被淘汰的key在map里还残留着引用get这个key时第一步map查到了节点返回了value第二步这个节点早就从链表里摘下来了但moveToHead时它依然是合法节点所以get竟然能返回成功表面上看起来缓存没有淘汰干净实则是map和链表不同步了。排查过程很有意思我先打印链表长度发现链表确实是2个节点再打印map的size发现map里是3个映射——这一刻问题立刻暴露了。这个场景很多人容易忽略因为单看put的每行代码都对只要遗漏了map的同步删除整体行为就是错的。这件事加深了我的一个习惯凡是涉及map和链表双结构联动的代码写完第一版先做数据一致性自查——链表里每个节点map里必须能找到map里每个映射链表里必须存在对应节点。这两条同时成立代码才算写完。这题我前前后后手写过几十遍每次重写都会有新的收获第一次能默写第二次理解了addToHead的指针顺序第三次想明白了为什么需要哨兵节点第四次才开始关注并发和淘汰策略的边界。数据结构这种东西看十遍不如手写一遍。你可以试着不用IDE自动提示徒手把这段代码写出来再跑一遍边界用例感受绝对不一样。