2026/9/13 6:32:36
FEATURED · 精选文章 
搞懂LRU其实就那么回事。LRULeast Recently Used最近最少使用是缓存设计里最经典的一个淘汰策略也是很多人面试时被现场要求手写代码的第一道“下马威”题。你可能在Redis、MySQL、操作系统的页面置换算法里都见过它的身影但真要让你十分钟内用代码撸一个出来还是有不少细节会被忽略。这篇就来把LRU从原理到实现彻底讲透。内容包括它到底解决什么问题、为什么选哈希表加双向链表这个组合、get和put每一步在做什么、Java代码怎么写得干净利落以及那些面试官最爱追问的细节。无论你是正在准备校招、社招还是单纯想巩固一下数据结构基础这篇都能帮上忙。1. 内容整体设计与思路拆解1.1 LRU到底在解决什么问题先聊场景。任何缓存系统都有容量上限不可能无限存数据。不管是CPU的cache、浏览器的历史记录、Redis的键值对还是数据库的连接池一旦存满了再想塞新数据就必须把某个旧数据踢出去。问题的关键是踢谁最朴素的做法是随机淘汰但用户体验和命中率都没保障。于是就有了各种淘汰策略FIFO先进先出谁先来谁先走。不管你有没有被经常访问排到队尾了就淘汰。LFU最不经常使用统计访问频率把频率最低的淘汰。LRU最近最少使用把最长时间没被访问的淘汰。FIFO的问题是明显的——它不关心数据的使用情况。比如一个早年加载的配置项可能每隔几秒就被读一次但因为排在最前面反而最先被挤掉。LFU也有缺陷如果某个数据在短时间内被疯狂访问然后长期不再使用它会因为频率计数高而占据缓存空间造成“热点僵尸”。LRU的假设是如果一个数据刚被访问过那么短期内大概率还会被访问如果一个数据很久没被访问那以后大概率也不需要了。这个假设在绝大多数应用场景下成立而且实现成本比LFU低得多所以LRU成了最普及的淘汰策略。1.2 数据结构选型为什么是哈希表加双向链表要手写LRU核心就是选对数据结构。先分析需求查询某个key是否在缓存中以及拿到它的value要快。访问了某个key之后要把这个key标记为“最近使用”也就是要调整它在淘汰序列中的位置。缓存满了的时候要快速找到“最久没被访问”的那个key并删掉。这三个需求摆在一起单靠一种数据结构是搞不定的。用数组行不行查询要靠遍历O(n)删除还要搬移元素也是O(n)很容易就超时。用一个普通的单链表行不行插入头部倒是O(1)但查询某个key还是要遍历O(n)删除某个节点还得从头找到它的前驱依然是O(n)。栈行不行访问一个已有节点时你要把它从栈中间抽出来再压回栈顶这操作本身就是O(n)。真正合适的组合是哈希表负责快速定位双向链表负责维护访问顺序。哈希表的key对应链表节点这样get的时候先用哈希表O(1)找到节点指针然后通过指针在链表中移动链表的头尾分别代表“最近使用”和“最久未使用”删除和插入都是O(1)。哈希表解决了“定位慢”的问题双向链表解决了“删除节点需要找前驱”的问题两个一拼完美互补。空间复杂度是O(capacity)因为哈希表存了capacity个映射链表也最多有capacity个节点。时间复杂度方面get和put全是O(1)这是LRU最核心的指标。2. 核心细节解析与实操要点2.1 读操作get的完整流程很多人以为LRU的get就是查到了就返回没那么简单。每次get命中之后这个节点要被移动到链表头部表示它刚刚被使用过。完整的get流程用key去哈希表里查。查不到直接返回-1。查到了拿到对应的链表节点把value保存下来。把这个节点从当前位置摘除移动到链表头部。返回value。这里有个很容易被忽略的细节为什么读操作也算“使用”因为LRU的判断标准是“最近最少使用”这里的“使用”包含读和写。比如你有两个热点数据A和B如果A被频繁读取但B已经不读了淘汰的时候应该淘汰B。如果get不会刷新位置那高频读的A总有一天也会因为“很旧”被误杀。所以读操作同样要移动节点到头部。2.2 写操作put的完整流程put的流程比get复杂一些因为要考虑两种情况key已存在和key不存在。key已存在时用key找到哈希表里的节点。更新这个节点的value。把这个节点移动到链表头部。key不存在时创建一个新节点。把新节点插到链表头部。把key和节点指针写入哈希表。判断当前链表节点数是否超过容量。如果超了把链表尾部节点也就是最久未使用的节点摘除并从哈希表中删除对应的key。这个顺序一定要记牢。有人喜欢先判断容量再插节点逻辑上也能转过来但更容易在边界条件上出错。先插入再判断是否超容量最后统一处理代码会干净很多。2.3 手撕时最容易被忽略的三个细节第一个细节虚拟头尾节点。如果不用虚拟节点链表为空、插入第一个节点、删除唯一节点的时候都要单独处理头指针尾指针的边界情况很容易漏判。加一个虚拟头节点和虚拟尾节点让真实的节点永远有前驱和后继所有的插入删除操作都变成统一的指针操作代码量直接少三分之一。第二个细节删除链表节点时要同步删除哈希表映射。新手写LRU最容易犯的错就是只动了链表忘了删哈希表。下次再访问这个key哈希表里还留着旧指针指向一个已经不在链表里的节点程序直接崩溃或者行为错乱。记住一条铁律链表节点和哈希表映射必须同生共死。第三个细节capacity为0或1的边界。capacity为0意味着不允许缓存任何数据所有put都应该直接放弃所有get都返回-1。capacity为1意味着只有一个位置每次put新key都要先淘汰旧key。这些边界在代码里用if判断cover住不然测试用例跑出来就会挂。3. 实操过程与核心环节实现3.1 Java手写LRU完整代码直接上代码我用的是最常见的“哈希表双向链表”写法。下面这段代码可以直接跑没有任何依赖第三方库。import java.util.HashMap; import java.util.Map; public class LRUCache { // 双向链表节点 static 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 final MapInteger, DLinkedNode cache new HashMap(); private final int capacity; // 虚拟头节点和虚拟尾节点 private final DLinkedNode head; private final DLinkedNode tail; // 当前链表中的节点数量 private int size; public LRUCache(int capacity) { this.capacity capacity; this.size 0; 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) { // 新节点 DLinkedNode newNode new DLinkedNode(key, value); cache.put(key, newNode); addToHead(newNode); size; // 超出容量则淘汰尾部节点 if (size capacity) { DLinkedNode tailNode removeTail(); cache.remove(tailNode.key); size--; } } else { // 更新值并移到头部 node.value value; moveToHead(node); } } // 把节点添加到头部 private void addToHead(DLinkedNode node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } // 删除一个节点前提是节点已在链表中 private void removeNode(DLinkedNode node) { node.prev.next node.next; node.next.prev node.prev; } // 把节点移动到头部 private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } // 删除尾部节点并返回它 private DLinkedNode removeTail() { DLinkedNode res tail.prev; removeNode(res); return res; } }代码不长但每一段都有讲究。addToHead负责把节点插到虚拟头节点后面removeNode用前驱和后继互相指向来跳过当前节点moveToHead就是先摘除再插入removeTail取的是tail.prev——也就是最后一个真实节点。这四个私有方法配合起来get和put的主逻辑才会这么简洁。3.2 用一个容量为3的例子走一遍完整流程光看代码可能还不够直观我拿一个具体例子手动模拟一遍你就彻底懂了。假设capacity3初始链表只有一个虚拟头节点和一个虚拟尾节点中间是空的。第一步put(1, 1)哈希表中没有key1新建节点(1,1)。插入到链表头部链表顺序是[1]。size1没超过3不淘汰。第二步put(2, 2)新建节点(2,2)插入头部。链表顺序是[2] - [1]。size2不淘汰。第三步put(3, 3)新建节点(3,3)插入头部。链表顺序是[3] - [2] - [1]。size3刚好等于容量不淘汰。此时如果从链表尾部往前看淘汰的优先级顺序是1最先被淘汰然后是2最后是3。第四步get(2)哈希表命中节点(2,2)的value是2。把节点(2,2)从当前位置摘除移动到头部。链表顺序变成[2] - [3] - [1]。注意此时1已经掉到了链表的最后它成了“最久未使用”的那一个。第五步put(4, 4)哈希表中没有key4新建节点(4,4)。插入到头部链表顺序是[4] - [2] - [3] - [1]。此时size4已经超过了capacity3需要淘汰。删除链表尾部节点也就是(1,1)同时从哈希表中移除key1。链表顺序变成[4] - [2] - [3]。哈希表里剩下2、3、4三个key。如果这时候再执行get(1)哈希表里已经没有key1了直接返回-1。走到这里整个LRU的运行机制已经完全清晰了。3.3 面试时手撕代码的书写技巧面试现场手写和自己在IDE里敲代码完全是两种体验。没有编译器的提示没有语法高亮一切靠脑子硬写有几个小技巧很实用第一先把类和成员变量写出来。DLinkedNode节点类、HashMap、capacity、head、tail这些字段先摆上构建器和get、put方法留空也行。先把骨架搭好心里就有底了后面逐个填充逻辑。第二先写辅助方法。addToHead、removeNode、moveToHead、removeTail这四个私有方法是get和put的地基。先完成这四个方法再去写get和put你会发现主逻辑特别顺手。这个写代码的顺序和阅读代码的顺序不完全一样但面试时用这个顺序思路会清晰很多。第三注意变量命名。现场写代码时节点类可以叫Node而不是DLinkedNode方法名尽量短一点比如addHead、removeNode、moveToHead、popTail。命名越简单手写的时候越不容易因为拼写错误卡住。第四写完肉眼跑一个例子。面试官一般不会立刻让你提交运行但你要自己在心里走一遍。拿capacity2put一个、get一个、再put触发淘汰这样一个小例子从头到尾过一遍能发现很多手误。4. 常见问题与排查技巧实录4.1 关于LRU的六个高频追问第一个追问为什么get和put都是O(1)在哪一步会有O(n)的风险哈希表让get能在常数时间找到节点双向链表让节点的删除和插入都只需要改动前后指针和链表总长度无关淘汰时直接取tail.prev也是O(1)。整个实现里没有一个操作需要遍历链表所以全部都是O(1)。第二个追问Java的LinkedHashMap能实现LRU吗能而且很多业务代码里就是这么干的。LinkedHashMap内部就是哈希表加双向链表结构和我们手写的如出一辙。构造传入accessOrdertrue之后get和put访问节点会自动把节点移到链表末尾重写removeEldestEntry方法就能在元素数超过容量时自动淘汰最头部的那个节点。手写LRU的训练意义在于让你真正理解底层机制面试时如果时间紧张也可以直接用LinkedHashMap但要能讲清楚它的原理。第三个追问为什么不用数组加时间戳数组加时间戳的思路是每个元素记录一个lastAccessTime淘汰时遍历数组找时间戳最旧的那个。理论上能实现LRU语义但淘汰的时间复杂度是O(n)并且数组是连续内存插入删除都得搬移根本不适合频繁变动顺序的场景。第四个追问为什么双向链表不用单链表单链表也能通过头插法维护顺序但删除中间节点时必须从头遍历找到它的前驱这就让moveToHead变成O(n)了。双向链表让每个节点都持有前驱指针删除自己只需要改前后两个节点的指向所以能保持O(1)。第五个追问并发场景下LRU怎么保证线程安全最简单的办法是在get和put方法上加synchronized或者用Collections.synchronizedMap包一层。但这样吞吐量很低。更精细的做法是用读写锁或者参考ConcurrentLinkedHashMap的并发分段锁思路。实际业务里如果用的是Redis的LRU那服务端本身就考虑好了并发问题不需要应用层操心。第六个追问LRU有什么缺点有什么改进版本LRU最大的缺点是不抗“局部性突变”。比如某天一个冷门商品突然被扫了一遍它就会被频繁塞进头部万一真的热点数据刚好被挤掉了就得不偿失。改进版本有LRU-K规定一个数据被访问K次之后才进入正式缓存还有Two Queue用一个FIFO队列先过滤掉一次性流量再进入LRU。Redis官方实现在Lru算法上做了近似处理并不维护严格的双向链表而是随机采样部分key然后比较空闲时间。4.2 手撕过程中最典型的错误汇总写LRU的时候容易翻车的地方其实高度集中我把新手踩得最多的坑汇总成一张表直接看图自查。错误点具体描述正确做法指针顺序写反在addToHead中先改了head.next再改原头部节点的prev导致原头部节点的prev指向了自己先处理新节点和原头部节点最后再改head的指向删链表忘了删哈希表淘汰节点时只修改了链表没执行cache.remove(key)删链表和删哈希表要成对出现get时return前忘了moveToHead命中了但没刷新节点位置LRU退化成类似FIFO的行为命中后必须先移动到头部再返回value容量判断写错用了if (size capacity)判断但此时还没插入新节点把“插入后超了”和“插入前就满”搞混插入后判断 if (size capacity)节点类忘了存key淘汰尾部节点时需要知道这个节点的key才能从哈希表删除没存key就只能干瞪眼节点类必须同时存key和value使用了真实头节点头节点本身是真实数据删除头节点时要额外处理边界条件多用虚拟头尾节点让head和tail始终是空站台4.3 自己验证代码是否正确的小窍门写完代码之后怎么快速判断对不对我自己常用一个记忆口诀来验证访问就上移满了就删尾。具体做法是手动跑三个用例。用例一get不存在的key必须返回-1。用例二容量为1时的put。put(1,1)再put(2,2)此时第一个元素必须被淘汰get(1)必须是-1get(2)必须是2。用例三模拟完整的经典顺序put(1,1)、put(2,2)、get(1)、put(3,3)、get(2)、put(4,4)、get(1)、get(3)、get(4)。在容量为2的情况下这个过程每一步的链表状态都可以推出来最后结果分别是1、-1、3、4。如果跑出来的结果和这个对不上多半就是哪个细节出了问题。5. LRU在真实系统中是如何落地的5.1 操作系统中的页面置换操作系统的分页虚拟内存管理里物理内存装不下所有页就必须在缺页时把某些页换出。LRU是页面置换算法里的理想算法因为它能达到最优的驻留集合。但真正的操作系统实现里维护一个严格的双向链表成本太高所以实际使用的是Clock算法这类近似LRU方案。Clock算法通过循环遍历页表项用一个引用位标记是否被访问过优先换出引用位为0的页。它本质上是LRU的简化版本用牺牲一点淘汰精度来换取硬件实现成本的可控。5.2 Redis的近似LRURedis的maxmemory回收策略里allkeys-lru和volatile-lru都是基于LRU的。但Redis官方并没有为每个key维护一个双向链表——全局有序结构在热点key多的时候锁竞争太严重。Redis的做法是给每个key记录一个最近访问时间戳LRU时钟淘汰时不是全局找最旧的那个而是从所有key中随机采样一批默认5个淘汰其中空闲时间最长的那个。这个策略叫近似LRU。Redis还做了额外优化从Redis 4.0开始支持LFU策略是因为采样LRU在访问模式是“扫描式”或“周期性脉冲式”的时候淘汰精度不够好。5.3 MySQL InnoDB Buffer Pool的变体LRUMySQL的Buffer Pool用的是一个经过改造的LRU叫midpoint insertion strategy。它把整个链表分成两部分young区域和old区域默认比例为5:3。新读入的页不是直接插到链表头部而是插到young区尾部和old区头部之间。这样做是为了防扫描污染——如果某个查询做了全表扫描大量一次性读入的页会直接淹没真正的热点页。插入midpoint之后只有再次被访问的页才会进入young区域全表扫描的页因为只访问一次会在old区快速被淘汰。这和LRU-K的思想是异曲同工。5.4 业务开发中最常见的LRU应用在实际业务代码里LRU最常见的应用就是做一个本地缓存。比如电商系统里缓存用户最近浏览的商品列表、推荐系统里缓存用户最近点击的item ID甚至编译器里都在用它做符号管理。手写一个LRU然后封装成线程安全版本并不难。但如果是在分布式系统里还是要优先考虑Redis这类独立缓存组件因为本地缓存的一致性维护成本很高节点多了之后每个节点各存一份副本数据不一致的问题马上就来了。6. 我手撕LRU的一些体会最后说点我的个人体会。LRU这个题背模板是背不牢的因为它考察的其实是你对两种基础数据结构——哈希表和链表的理解程度。如果你真正理解了“为什么get要移动到头”“为什么尾部是最旧数据”代码就是顺着思路自然流淌出来的产物而不是死记硬背的八股。我有个习惯不管面试还是自己练手都会先在草稿纸上把Cache的状态变化用箭头画一遍。put进去一个新节点画一条新的头指针淘汰一个节点把尾指针往前挪一格。画完几张图之后整个算法在心里就有了画面感写代码的时候就会非常快。LRU还有不少延伸变种比如LRU-K、Two Queue、Multi Queue每个都是在解决LRU在某些特定流量模式下的短板。但它们的核心思想都一样给每个数据一个“新鲜度”访问越频繁越靠近头部越久没碰越往尾部掉。把这个根儿上的东西弄明白了后面学什么都快。
搞懂LRU：原理、实现与面试全解析
搞懂LRU其实就那么回事。LRULeast Recently Used最近最少使用是缓存设计里最经典的一个淘汰策略也是很多人面试时被现场要求手写代码的第一道“下马威”题。你可能在Redis、MySQL、操作系统的页面置换算法里都见过它的身影但真要让你十分钟内用代码撸一个出来还是有不少细节会被忽略。这篇就来把LRU从原理到实现彻底讲透。内容包括它到底解决什么问题、为什么选哈希表加双向链表这个组合、get和put每一步在做什么、Java代码怎么写得干净利落以及那些面试官最爱追问的细节。无论你是正在准备校招、社招还是单纯想巩固一下数据结构基础这篇都能帮上忙。1. 内容整体设计与思路拆解1.1 LRU到底在解决什么问题先聊场景。任何缓存系统都有容量上限不可能无限存数据。不管是CPU的cache、浏览器的历史记录、Redis的键值对还是数据库的连接池一旦存满了再想塞新数据就必须把某个旧数据踢出去。问题的关键是踢谁最朴素的做法是随机淘汰但用户体验和命中率都没保障。于是就有了各种淘汰策略FIFO先进先出谁先来谁先走。不管你有没有被经常访问排到队尾了就淘汰。LFU最不经常使用统计访问频率把频率最低的淘汰。LRU最近最少使用把最长时间没被访问的淘汰。FIFO的问题是明显的——它不关心数据的使用情况。比如一个早年加载的配置项可能每隔几秒就被读一次但因为排在最前面反而最先被挤掉。LFU也有缺陷如果某个数据在短时间内被疯狂访问然后长期不再使用它会因为频率计数高而占据缓存空间造成“热点僵尸”。LRU的假设是如果一个数据刚被访问过那么短期内大概率还会被访问如果一个数据很久没被访问那以后大概率也不需要了。这个假设在绝大多数应用场景下成立而且实现成本比LFU低得多所以LRU成了最普及的淘汰策略。1.2 数据结构选型为什么是哈希表加双向链表要手写LRU核心就是选对数据结构。先分析需求查询某个key是否在缓存中以及拿到它的value要快。访问了某个key之后要把这个key标记为“最近使用”也就是要调整它在淘汰序列中的位置。缓存满了的时候要快速找到“最久没被访问”的那个key并删掉。这三个需求摆在一起单靠一种数据结构是搞不定的。用数组行不行查询要靠遍历O(n)删除还要搬移元素也是O(n)很容易就超时。用一个普通的单链表行不行插入头部倒是O(1)但查询某个key还是要遍历O(n)删除某个节点还得从头找到它的前驱依然是O(n)。栈行不行访问一个已有节点时你要把它从栈中间抽出来再压回栈顶这操作本身就是O(n)。真正合适的组合是哈希表负责快速定位双向链表负责维护访问顺序。哈希表的key对应链表节点这样get的时候先用哈希表O(1)找到节点指针然后通过指针在链表中移动链表的头尾分别代表“最近使用”和“最久未使用”删除和插入都是O(1)。哈希表解决了“定位慢”的问题双向链表解决了“删除节点需要找前驱”的问题两个一拼完美互补。空间复杂度是O(capacity)因为哈希表存了capacity个映射链表也最多有capacity个节点。时间复杂度方面get和put全是O(1)这是LRU最核心的指标。2. 核心细节解析与实操要点2.1 读操作get的完整流程很多人以为LRU的get就是查到了就返回没那么简单。每次get命中之后这个节点要被移动到链表头部表示它刚刚被使用过。完整的get流程用key去哈希表里查。查不到直接返回-1。查到了拿到对应的链表节点把value保存下来。把这个节点从当前位置摘除移动到链表头部。返回value。这里有个很容易被忽略的细节为什么读操作也算“使用”因为LRU的判断标准是“最近最少使用”这里的“使用”包含读和写。比如你有两个热点数据A和B如果A被频繁读取但B已经不读了淘汰的时候应该淘汰B。如果get不会刷新位置那高频读的A总有一天也会因为“很旧”被误杀。所以读操作同样要移动节点到头部。2.2 写操作put的完整流程put的流程比get复杂一些因为要考虑两种情况key已存在和key不存在。key已存在时用key找到哈希表里的节点。更新这个节点的value。把这个节点移动到链表头部。key不存在时创建一个新节点。把新节点插到链表头部。把key和节点指针写入哈希表。判断当前链表节点数是否超过容量。如果超了把链表尾部节点也就是最久未使用的节点摘除并从哈希表中删除对应的key。这个顺序一定要记牢。有人喜欢先判断容量再插节点逻辑上也能转过来但更容易在边界条件上出错。先插入再判断是否超容量最后统一处理代码会干净很多。2.3 手撕时最容易被忽略的三个细节第一个细节虚拟头尾节点。如果不用虚拟节点链表为空、插入第一个节点、删除唯一节点的时候都要单独处理头指针尾指针的边界情况很容易漏判。加一个虚拟头节点和虚拟尾节点让真实的节点永远有前驱和后继所有的插入删除操作都变成统一的指针操作代码量直接少三分之一。第二个细节删除链表节点时要同步删除哈希表映射。新手写LRU最容易犯的错就是只动了链表忘了删哈希表。下次再访问这个key哈希表里还留着旧指针指向一个已经不在链表里的节点程序直接崩溃或者行为错乱。记住一条铁律链表节点和哈希表映射必须同生共死。第三个细节capacity为0或1的边界。capacity为0意味着不允许缓存任何数据所有put都应该直接放弃所有get都返回-1。capacity为1意味着只有一个位置每次put新key都要先淘汰旧key。这些边界在代码里用if判断cover住不然测试用例跑出来就会挂。3. 实操过程与核心环节实现3.1 Java手写LRU完整代码直接上代码我用的是最常见的“哈希表双向链表”写法。下面这段代码可以直接跑没有任何依赖第三方库。import java.util.HashMap; import java.util.Map; public class LRUCache { // 双向链表节点 static 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 final MapInteger, DLinkedNode cache new HashMap(); private final int capacity; // 虚拟头节点和虚拟尾节点 private final DLinkedNode head; private final DLinkedNode tail; // 当前链表中的节点数量 private int size; public LRUCache(int capacity) { this.capacity capacity; this.size 0; 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) { // 新节点 DLinkedNode newNode new DLinkedNode(key, value); cache.put(key, newNode); addToHead(newNode); size; // 超出容量则淘汰尾部节点 if (size capacity) { DLinkedNode tailNode removeTail(); cache.remove(tailNode.key); size--; } } else { // 更新值并移到头部 node.value value; moveToHead(node); } } // 把节点添加到头部 private void addToHead(DLinkedNode node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } // 删除一个节点前提是节点已在链表中 private void removeNode(DLinkedNode node) { node.prev.next node.next; node.next.prev node.prev; } // 把节点移动到头部 private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } // 删除尾部节点并返回它 private DLinkedNode removeTail() { DLinkedNode res tail.prev; removeNode(res); return res; } }代码不长但每一段都有讲究。addToHead负责把节点插到虚拟头节点后面removeNode用前驱和后继互相指向来跳过当前节点moveToHead就是先摘除再插入removeTail取的是tail.prev——也就是最后一个真实节点。这四个私有方法配合起来get和put的主逻辑才会这么简洁。3.2 用一个容量为3的例子走一遍完整流程光看代码可能还不够直观我拿一个具体例子手动模拟一遍你就彻底懂了。假设capacity3初始链表只有一个虚拟头节点和一个虚拟尾节点中间是空的。第一步put(1, 1)哈希表中没有key1新建节点(1,1)。插入到链表头部链表顺序是[1]。size1没超过3不淘汰。第二步put(2, 2)新建节点(2,2)插入头部。链表顺序是[2] - [1]。size2不淘汰。第三步put(3, 3)新建节点(3,3)插入头部。链表顺序是[3] - [2] - [1]。size3刚好等于容量不淘汰。此时如果从链表尾部往前看淘汰的优先级顺序是1最先被淘汰然后是2最后是3。第四步get(2)哈希表命中节点(2,2)的value是2。把节点(2,2)从当前位置摘除移动到头部。链表顺序变成[2] - [3] - [1]。注意此时1已经掉到了链表的最后它成了“最久未使用”的那一个。第五步put(4, 4)哈希表中没有key4新建节点(4,4)。插入到头部链表顺序是[4] - [2] - [3] - [1]。此时size4已经超过了capacity3需要淘汰。删除链表尾部节点也就是(1,1)同时从哈希表中移除key1。链表顺序变成[4] - [2] - [3]。哈希表里剩下2、3、4三个key。如果这时候再执行get(1)哈希表里已经没有key1了直接返回-1。走到这里整个LRU的运行机制已经完全清晰了。3.3 面试时手撕代码的书写技巧面试现场手写和自己在IDE里敲代码完全是两种体验。没有编译器的提示没有语法高亮一切靠脑子硬写有几个小技巧很实用第一先把类和成员变量写出来。DLinkedNode节点类、HashMap、capacity、head、tail这些字段先摆上构建器和get、put方法留空也行。先把骨架搭好心里就有底了后面逐个填充逻辑。第二先写辅助方法。addToHead、removeNode、moveToHead、removeTail这四个私有方法是get和put的地基。先完成这四个方法再去写get和put你会发现主逻辑特别顺手。这个写代码的顺序和阅读代码的顺序不完全一样但面试时用这个顺序思路会清晰很多。第三注意变量命名。现场写代码时节点类可以叫Node而不是DLinkedNode方法名尽量短一点比如addHead、removeNode、moveToHead、popTail。命名越简单手写的时候越不容易因为拼写错误卡住。第四写完肉眼跑一个例子。面试官一般不会立刻让你提交运行但你要自己在心里走一遍。拿capacity2put一个、get一个、再put触发淘汰这样一个小例子从头到尾过一遍能发现很多手误。4. 常见问题与排查技巧实录4.1 关于LRU的六个高频追问第一个追问为什么get和put都是O(1)在哪一步会有O(n)的风险哈希表让get能在常数时间找到节点双向链表让节点的删除和插入都只需要改动前后指针和链表总长度无关淘汰时直接取tail.prev也是O(1)。整个实现里没有一个操作需要遍历链表所以全部都是O(1)。第二个追问Java的LinkedHashMap能实现LRU吗能而且很多业务代码里就是这么干的。LinkedHashMap内部就是哈希表加双向链表结构和我们手写的如出一辙。构造传入accessOrdertrue之后get和put访问节点会自动把节点移到链表末尾重写removeEldestEntry方法就能在元素数超过容量时自动淘汰最头部的那个节点。手写LRU的训练意义在于让你真正理解底层机制面试时如果时间紧张也可以直接用LinkedHashMap但要能讲清楚它的原理。第三个追问为什么不用数组加时间戳数组加时间戳的思路是每个元素记录一个lastAccessTime淘汰时遍历数组找时间戳最旧的那个。理论上能实现LRU语义但淘汰的时间复杂度是O(n)并且数组是连续内存插入删除都得搬移根本不适合频繁变动顺序的场景。第四个追问为什么双向链表不用单链表单链表也能通过头插法维护顺序但删除中间节点时必须从头遍历找到它的前驱这就让moveToHead变成O(n)了。双向链表让每个节点都持有前驱指针删除自己只需要改前后两个节点的指向所以能保持O(1)。第五个追问并发场景下LRU怎么保证线程安全最简单的办法是在get和put方法上加synchronized或者用Collections.synchronizedMap包一层。但这样吞吐量很低。更精细的做法是用读写锁或者参考ConcurrentLinkedHashMap的并发分段锁思路。实际业务里如果用的是Redis的LRU那服务端本身就考虑好了并发问题不需要应用层操心。第六个追问LRU有什么缺点有什么改进版本LRU最大的缺点是不抗“局部性突变”。比如某天一个冷门商品突然被扫了一遍它就会被频繁塞进头部万一真的热点数据刚好被挤掉了就得不偿失。改进版本有LRU-K规定一个数据被访问K次之后才进入正式缓存还有Two Queue用一个FIFO队列先过滤掉一次性流量再进入LRU。Redis官方实现在Lru算法上做了近似处理并不维护严格的双向链表而是随机采样部分key然后比较空闲时间。4.2 手撕过程中最典型的错误汇总写LRU的时候容易翻车的地方其实高度集中我把新手踩得最多的坑汇总成一张表直接看图自查。错误点具体描述正确做法指针顺序写反在addToHead中先改了head.next再改原头部节点的prev导致原头部节点的prev指向了自己先处理新节点和原头部节点最后再改head的指向删链表忘了删哈希表淘汰节点时只修改了链表没执行cache.remove(key)删链表和删哈希表要成对出现get时return前忘了moveToHead命中了但没刷新节点位置LRU退化成类似FIFO的行为命中后必须先移动到头部再返回value容量判断写错用了if (size capacity)判断但此时还没插入新节点把“插入后超了”和“插入前就满”搞混插入后判断 if (size capacity)节点类忘了存key淘汰尾部节点时需要知道这个节点的key才能从哈希表删除没存key就只能干瞪眼节点类必须同时存key和value使用了真实头节点头节点本身是真实数据删除头节点时要额外处理边界条件多用虚拟头尾节点让head和tail始终是空站台4.3 自己验证代码是否正确的小窍门写完代码之后怎么快速判断对不对我自己常用一个记忆口诀来验证访问就上移满了就删尾。具体做法是手动跑三个用例。用例一get不存在的key必须返回-1。用例二容量为1时的put。put(1,1)再put(2,2)此时第一个元素必须被淘汰get(1)必须是-1get(2)必须是2。用例三模拟完整的经典顺序put(1,1)、put(2,2)、get(1)、put(3,3)、get(2)、put(4,4)、get(1)、get(3)、get(4)。在容量为2的情况下这个过程每一步的链表状态都可以推出来最后结果分别是1、-1、3、4。如果跑出来的结果和这个对不上多半就是哪个细节出了问题。5. LRU在真实系统中是如何落地的5.1 操作系统中的页面置换操作系统的分页虚拟内存管理里物理内存装不下所有页就必须在缺页时把某些页换出。LRU是页面置换算法里的理想算法因为它能达到最优的驻留集合。但真正的操作系统实现里维护一个严格的双向链表成本太高所以实际使用的是Clock算法这类近似LRU方案。Clock算法通过循环遍历页表项用一个引用位标记是否被访问过优先换出引用位为0的页。它本质上是LRU的简化版本用牺牲一点淘汰精度来换取硬件实现成本的可控。5.2 Redis的近似LRURedis的maxmemory回收策略里allkeys-lru和volatile-lru都是基于LRU的。但Redis官方并没有为每个key维护一个双向链表——全局有序结构在热点key多的时候锁竞争太严重。Redis的做法是给每个key记录一个最近访问时间戳LRU时钟淘汰时不是全局找最旧的那个而是从所有key中随机采样一批默认5个淘汰其中空闲时间最长的那个。这个策略叫近似LRU。Redis还做了额外优化从Redis 4.0开始支持LFU策略是因为采样LRU在访问模式是“扫描式”或“周期性脉冲式”的时候淘汰精度不够好。5.3 MySQL InnoDB Buffer Pool的变体LRUMySQL的Buffer Pool用的是一个经过改造的LRU叫midpoint insertion strategy。它把整个链表分成两部分young区域和old区域默认比例为5:3。新读入的页不是直接插到链表头部而是插到young区尾部和old区头部之间。这样做是为了防扫描污染——如果某个查询做了全表扫描大量一次性读入的页会直接淹没真正的热点页。插入midpoint之后只有再次被访问的页才会进入young区域全表扫描的页因为只访问一次会在old区快速被淘汰。这和LRU-K的思想是异曲同工。5.4 业务开发中最常见的LRU应用在实际业务代码里LRU最常见的应用就是做一个本地缓存。比如电商系统里缓存用户最近浏览的商品列表、推荐系统里缓存用户最近点击的item ID甚至编译器里都在用它做符号管理。手写一个LRU然后封装成线程安全版本并不难。但如果是在分布式系统里还是要优先考虑Redis这类独立缓存组件因为本地缓存的一致性维护成本很高节点多了之后每个节点各存一份副本数据不一致的问题马上就来了。6. 我手撕LRU的一些体会最后说点我的个人体会。LRU这个题背模板是背不牢的因为它考察的其实是你对两种基础数据结构——哈希表和链表的理解程度。如果你真正理解了“为什么get要移动到头”“为什么尾部是最旧数据”代码就是顺着思路自然流淌出来的产物而不是死记硬背的八股。我有个习惯不管面试还是自己练手都会先在草稿纸上把Cache的状态变化用箭头画一遍。put进去一个新节点画一条新的头指针淘汰一个节点把尾指针往前挪一格。画完几张图之后整个算法在心里就有了画面感写代码的时候就会非常快。LRU还有不少延伸变种比如LRU-K、Two Queue、Multi Queue每个都是在解决LRU在某些特定流量模式下的短板。但它们的核心思想都一样给每个数据一个“新鲜度”访问越频繁越靠近头部越久没碰越往尾部掉。把这个根儿上的东西弄明白了后面学什么都快。 
