LRU缓存这道题算是LeetCode高频题里少有的几个“T0级别”存在。我前后面试过不少公司不管大厂小厂手撕算法题环节十次里有四五次能看到LRU的影子LinkedHashMap那种黑盒写法能不能过完全取决于面试官心情但手写双链表加哈希表的经典实现几乎就是标准答案。今天这篇就是把这道“可直接背”的题掰开揉碎给你一套能默写的模板顺带讲清楚每一步为什么这么写以及面试官坐在对面盯着你写时哪些地方最容易翻车。1. 题目到底在考什么先看清LRU的庐山真面目1.1 原题描述与真实场景力扣146题的描述其实很短设计一个LRUCache类构造函数传入容量capacity实现get(key)和put(key, value)两个方法。get时如果key存在就返回值不存在返回-1put时如果key已存在就更新值不存在就插入插入后超过容量就把“最久没被使用”的key淘汰掉。很多人一看就以为这题简单无非是个“缓存”。但你要真把它放到业务里想LRU无处不在Android的图片加载内存缓存、Redis的内存淘汰策略、浏览器的后退页面缓存底层都是这个逻辑。面试官考这题表面考数据结构设计实际考的是你有没有“在有限资源下做淘汰决策”的工程意识。举个生活化的例子你家书桌只有三个空位每次看完的书要放回桌上新买来的书也要放桌上。放不下怎么办把最长时间没翻过的那本拿走。这其实就是LRU最朴素的直觉——最近用过的留最久没用的扔。算法题里的“使用”指的是get和put两种操作都算一次访问。1.2 三个层次的能力考察光把题目做对还不够面试官在这种“手撕题”里通常会叠加三层考察第一层是功能正确性get、put的语义对不对缓存满没满、被淘汰的是不是真正最久未使用的。这一层大多数背过模板的人都能过。第二层是复杂度达标get和put都要求O(1)时间复杂度。如果只用了数组或者链表查找需要O(n)直接不合格。这一层会刷掉一批上来就想用Queue或者List硬写的人。第三层是设计解释能力面试官会追问为什么用哈希表、为什么用双向链表、单链表行不行、JDK里的LinkedHashMap是怎么做到的。这一层考察的是你有没有理解数据结构的本质而不是死记硬背。所以“可直接背”不是让你背代码就完事而是背完要能对答如流。接下来的内容就是按这个标准给你整理的一套完整话术加模板。2. 核心设计思路为什么双链表加哈希表是标准答案2.1 单看一个数据结构都搞不定我先给新人排个雷这道题最忌讳的就是只用一个数据结构硬扛。用数组访问和插入都要O(n)而且中间插删还涉及元素移动完全不符合要求。用单向链表删除某个节点时你根本拿不到它的前驱节点只能从头遍历。虽然我们知道要删除的节点是“链表倒数第几个”但没有前驱指针就是删不掉。用LinkedHashMap本身是能解决问题的Java里直接继承再重写removeEldestEntry就能过题。但面试场景下你写成这样面试官大概率会让你“别用现成的手写一个”。因为LinkedHashMap内部就是哈希表加双向链表你自己把它拆开写一遍才是他真正想看的。2.2 哈希表负责“找得快”链表负责“记得住顺序”两个数据结构组合起来职责非常清晰哈希表Mapkey, Node负责O(1)找到某个key对应的节点对象。双向链表负责维护“最近使用”的顺序。链表头部永远放最近用过的节点尾部永远放最久没用的节点。这里有个关键点哈希表的value不能只存value必须存节点对象Node。因为get的时候命中缓存除了返回值还要把这个节点移动到链表头部。如果map里只存了value值你根本不知道这个value对应链表里的哪个节点也就没办法O(1)调整顺序。我见过不少新手写的版本Map存key和value链表也存key和value然后每次操作链表都在里面线性查找节点。这本质上等于退化成了一个带着哈希表的O(n)算法复杂度根本不达标。Map的value必须是Node引用这是整个设计的命门。2.3 双向链表节点为什么还要再存一个key链表的节点里除了存value还需要额外存key。这一点是很多教程含糊带过的地方但面试官特别爱问。原因是当缓存满了我们要淘汰链表尾节点。尾节点里只有key和value但我们要去哈希表里把对应的映射删掉就得知道这个key。如果节点里不存key淘汰时你还要在外面记录一份“key和Node的对应关系”或者另想办法把key找回来越搞越复杂。记住这句话“链表节点是双向的node和map也是双向的”。node里有keymap里以key为键找到node。这样无论是get、put还是淘汰都能O(1)完成闭环。2.4 哨兵节点的妙处不怕空链表也不用判空再来看链表头的虚拟头节点head和虚拟尾节点tail。这俩是“哨兵节点”不存真实数据只作为边界标记。head.next指向真正的第一个节点tail.prev指向真正的最后一个节点。这样设计最大的好处是处理链表插删时不需要对空链表做特殊判断。如果不用哨兵插入第一个节点和插入普通节点逻辑不一样删除最后一个节点和删除中间节点逻辑也不一样一旦写错就是空指针或者丢数据。有了哨兵头插和尾删永远都是同样的四行指针操作代码能短一截出错概率也低一截。实际写代码时初始化就让head.next指向tail、tail.prev指向head一个空链表就表示好了。后面所有操作都在这两个哨兵之间进行边界和安全都很好处理。下表把各角色的分工再捋一遍角色作用实现要点哈希表O(1)定位节点MapInteger, Nodevalue存节点引用双向链表维护访问顺序头最近使用尾最久未使用Node节点存储key和value必须存key淘汰时要用哨兵head标记链表头部head.next为真实头节点哨兵tail标记链表尾部tail.prev为真实尾节点3. 可直接背诵的Java模板先抄下来再一步步拆3.1 完整参考代码下面这份代码是我自己在面试前反复打磨过的版本每个方法职责单一没有多余分支。你可以先整个抄一遍抄完不要急着关页面后面我会逐段讲清楚它为什么是这么写的。import java.util.HashMap; import java.util.Map; class LRUCache { private static class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; DLinkedNode() {} 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; public LRUCache(int capacity) { 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) { DLinkedNode newNode new DLinkedNode(key, value); cache.put(key, newNode); addToHead(newNode); if (cache.size() capacity) { DLinkedNode tailNode removeTail(); cache.remove(tailNode.key); } } else { node.value value; moveToHead(node); } } 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; } private DLinkedNode removeTail() { DLinkedNode tailNode tail.prev; removeNode(tailNode); return tailNode; } }3.2 构造方法里藏着什么玄机构造函数接收一个capacity然后初始化两个哨兵节点。很多模板在这里会写head new DLinkedNode(-1, -1)给哨兵节点一个无意义的初始值这也没问题。但更干净的做法是用无参构造的DLinkedNode让哨兵节点完全没有key和value纯粹作为占位符存在。这里要特别注意一点capacity是final的因为一个缓存实例的容量在生命周期内不应该变化这样语义更清晰。cache同样用final修饰表示map引用不会变只是里面的内容不断增删。初始化哨兵连线这一步很多人会漏head.next tail; tail.prev head;。少了这一步后面addToHead里执行head.next.prev node时head.next还是null直接空指针。所以每次写完构造方法先在纸上画一下head和tail两个节点的一来一回连线确认这个“空的”双向链表真的闭合了。3.3 get方法的两种分支get的进出逻辑非常直白先从map里取取不到返回-1取到了就把节点挪到链表头部再返回节点里的value。这里有个隐含的语义细节get也算一次“使用”。很多人知道put算使用但get会把某个key从“老古董”变成“新鲜货”这一点恰恰是LRU的灵魂。你想象一下看视频App的首页推荐你点开了某个内容它后面一段时间就会经常出现在你面前——因为你“用”过它了。在LRU的实现里get就是那个“点开”的动作。移动节点到头部标准做法是两步先removeNode把它从原位置摘除再addToHead插入头部。这个组合操作我专门抽了一个moveToHead方法这样get和后面的put可以复用。面试时如果面试官问你get为什么要把节点移到头部你就答“为了让链表尾部始终沉淀最久未使用的key下次淘汰时直接摘tail.prev就行。”3.4 put方法的分支处理新增与更新两条路put的逻辑比get多一层判断。先用map查一下key在不在key不存在新建节点先把key和node放进map再把节点插到链表头部。然后检查map的size如果大于capacity就移除链表的真实尾节点同时把对应的key从map里删掉。key已存在更新节点里的value值然后把这个节点移到链表头部。这里注意不要重复put进map因为map里已经有这个key了只需要更新node.value。有一种看着也对但我不推荐的写法key已存在时先removeNode再addToHead等于把既有节点重新头插一遍。这种写法虽然结果正确但多绕了一步不如直接更新value再moveToHead语义清晰。面试的时候代码越直白越显得你理解到位不需要那些花哨的等价变换。还有一个容易忽略的细节新增节点后是先插链表再检查超容量还是先检查再加我建议先put进map、插到链表头部然后统一检查容量。这样新节点已经在链表里了如果超容量直接removeTail移除的就是“最久未使用”的节点逻辑上很顺畅。如果你先检查容量还没插入新节点就删除后面的代码分支会变多维护起来烦得很。3.5 四个私有工具方法背熟这四段就是背熟全题整道题最核心的“手筋”其实都集中在四个私有方法里我把它们单独拆出来讲removeNode(node)摘除一个节点。两行代码node.prev.next指向node.nextnode.next.prev指向node.prev。这里不需要处理node自己的prev和next因为被摘除的节点已经没用了后续如果还要用比如moveToHead会让addToHead重新给它赋值prev和next。addToHead(node)头插一个节点。四行代码的顺序是固定的先设置node.prev为headnode.next设为head.next再把head.next.prev指向node最后head.next指向node。这个顺序不能乱尤其是第三行必须在第四行之前执行。如果先执行head.next node那么第三步head.next.prev node就变成了node.prev node链表直接断开成环后面就崩了。moveToHead(node)先removeNode再addToHead。这个组合方法的存在意义就是复用代码量不长但能让get和put两个入口方法清爽很多。removeTail()拿到tail.prev这个真实尾节点removeNode摘除然后返回这个节点。返回的目的是让put方法里能用cache.remove(tailNode.key)把map里对应的映射也删掉。这一步正好印证了前面说的为什么节点里必须存key。这四个方法你完全可以当作口诀来记“remove两行add四行顺序别乱完美的循环”。4. 把“可直接背”落到实操记忆口诀与节奏练习4.1 六句口诀覆盖全部代码有读者问我代码确实不长但为什么一到面试现场就写劈叉。我总结下来主要是没有把代码“动词化”。光看代码是碎片信息不容易记一旦提炼成口诀跟着口诀走代码是自然带出来的。我平时带人刷这道题会让对方先背下面六句话哈希负责找链表负责序。头是新客尾是旧人。get命中先挪头没中返回负一不回头。put分两路新客点燃头挨个往里塞旧客改个值顺手挪个头。满员就拽尾拽完拿key删哈希。断链两行头插四行顺序先node后head。这六句话不是顺口溜每句都对应代码里的具体动作。比如第5句“满员就拽尾拽完拿key删哈希”对应的就是removeTail之后用tailNode.key去cache.remove。第6句则是addToHead里先操作node自己的prev和next再操作head那边保证链表不会断。4.2 三轮默写训练法第一步抄。把上面的完整代码抄三遍抄的过程中在旁边标注每一段的“口诀关键词”。比如写到addToHead就写“先node后head”。这一步是为了建立肌肉记忆。第二步关掉代码只留口诀。看着六句话把代码一行一行默写出来。默不出来就回看但每默写一次都要强迫自己回忆那段代码对应的口诀。坚持两遍之后你会发现你不是在“背代码”而是在“翻译口诀”。第三步限时闭卷。给自己掐一个7分钟的计时器在白板上或纸上完整写一遍。写的时候模拟面试环境——左手比划着画链表变化嘴里小声讲“这里是把新节点插到head后面”。这一步能提前适应面试时的紧张感。我自己带过的不少人三轮坚持下来基本能在5分钟左右写完完整实现。你要知道LeetCode上搜“LRU”能搜出一堆写法但能够在白板环境下不靠编译器还不报错的真没那么多。这套训练方法比单纯刷题有用得多。4.3 复杂度与记忆常见性能对照操作时间复杂度说明getO(1)map查找一次链表移动是常数次指针操作putO(1)map插入/更新一次链表头插/尾删为常数次空间O(capacity)最多存capacity个节点map和链表等量面试官问复杂度的时候你直接说O(1)还不够最好补一句“因为map的查找是O(1)双向链表的插入删除只要改前后指针不涉及遍历所以整体O(1)。”加上这句话复杂度层面就滴水不漏了。5. 手写现场最容易炸的五个坑5.1 头插四行顺序颠倒链表自环这是我在辅导里见到的最高频错误。addToHead的正确顺序要保证head.next.prev这行在head.next赋值之前执行。如果你先把head.next指向node再执行head.next.prev node实际上等于执行node.prev nodenode的前驱指向自己链表彻底乱了。避坑技巧头插永远先“补新节点的线”再“动head的线”。前两行是node.prev和node.next后两行才是head.next.prev和head.next。只要这个顺序不断自环就不会发生。5.2 removeNode时多写了多余的“清空”操作有些人在removeNode里会顺手写node.prev null; node.next null;觉得这样更干净。这在你不再使用这个节点时没问题但moveToHead会先把节点remove掉再addToHead——如果你清空了prev和nextaddToHead时就要重新补两行赋值虽然也能写对但平白多了出错的窗口。我的建议是removeNode只负责把节点从链表里摘掉不要清理它的prev和next引用让addToHead直接在旧引用基础上覆盖即可。当然这里针对的是模板代码如果你在别的地方复用这个节点且需要彻底断开那是另说。面试场景下少操作一步就是少一个出错的机会。5.3 put已存在的key时忘了moveToHead返回去更新value很多人会写node.value value就结束了完全没把节点挪到头部。这样会导致什么问题一个被put的key本应该算作“最近使用”结果它在链表里的位置纹丝不动可能明明刚被更新过却排在尾部等着被淘汰。语义错了题目就白做了。这里的口诀是“旧客改个值顺手挪个头”更新value后必须调用moveToHead一步都不能少。5.4 淘汰时忘了从map移除对应key还有种隐蔽的错法链表尾节点被removeTail摘掉了但map里还留着那个key对应的节点引用。之后get这个key仍然能查到node但node已经不在链表里后面moveToHead再操作它就会引发空指针或逻辑混乱。map和链表就像“双写账本”任何一边动了另一边必须同步。所以在put超容量的分支里removeTail拿到tailNode之后必须紧接着cache.remove(tailNode.key)。这两行是绑定的建议直接写在一起当成一个动作记忆。5.5 哨兵节点初始化遗漏构造方法里要是忘了head.next tail; tail.prev head;addToHead在第一次插入时就会因为head.next为null而空指针。这个错在IDE里一跑就现原形但白板面试时可没编译器提醒。我有个习惯写完构造方法先画图。head和tail之间画一条双向箭头确认“空链表闭合”心里默念“头尾相连”再继续往下写。这能帮你在写代码前先确认结构拓扑是对的。6. 面试进阶从LRU到LFU和工程实践6.1 面试官的经典追问LinkedHashMap是怎么做到的很多面试官在你写完手写实现后会追一句“你知道LinkedHashMap本身的LRU实现吗”这个问题其实是在考察你除了背模板有没有真正的知识广度。LinkedHashMap在HashMap基础上维护了一个双向链表并且有一个accessOrder字段。accessOrder为false时按插入顺序排列为true时按访问顺序排列。构造时传true然后在重写removeEldestEntry方法判断size是否超过capacity就能得到一套现成的LRU缓存。扩展一下如果面试官让你用LinkedHashMap再写一遍你至少要能说出下面这段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) { 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; } }这个版本能过题但我不建议作为面试首选。它把实现细节藏进了框架里面试官一眼就知道你用的是“黑盒”紧接着就会让你手写底层。你能写出来说明理解原理写不出来那这一题得分就打折扣了。6.2 LFU缓存最不经常使用的思路LFU是LRU的“兄弟题”力扣460题。它的淘汰规则从“最近最少使用”变成“使用频率最低”。两者的差异在于LRU只看时间维度LFU还要统计频率。LFU的常规实现是维护一个频率map每个频率对应一个双向链表或者用优先队列按频率和访问时间来排序。面试时被追问LFU不需要你写出完整实现但至少要能说出和LRU的结构差异LRU只需要一个链表LFU需要维护“频率桶”。如果你能在讲LRU时主动带一句“如果面试官问LFU核心不再是唯一链表而是为每个频率单独建链表”会显得你对数据结构的理解有层次感。6.3 工程里的近似LRU和业务变体实际工程里严格意义上的LRU往往因为性能、并发、内存占用等原因会被改造。Redis的淘汰策略号称近似LRU实际实现是采样淘汰在候选key池里随机取一批淘汰其中最久没用的。这样避免了为每个key维护精确时间戳的双向链表带来的内存开销性能更好误差在可接受范围内。很多面试官喜欢拿这个问“为什么Redis不用严格的LRU”你就可以答“内存和性能开销太大近似已经足够”。Android的LruCache则是在LinkedHashMap的accessOrder机制上包了一层线程安全控制通过synchronized关键字保证put、get的原子性。Android开发的同学对LruCache应该都不陌生面试时如果被问到可以把理解往“内部实现就是哈希表链表对外提供线程安全接口”这个方向引。除此之外还有一些业务变种比如“带有过期时间的LRU”“多级LRU”本质上都是在双链表和哈希表这个骨架上加额外的定时清理或分级缓存逻辑。只要你把核心骨架吃透这些变种无非是在get和put里多塞一段判断的事。7. Python版本的参考实现不想写Java也能用7.1 用OrderedDict的简洁实现Python刷题的读者也可以直接记下面这份简洁版。它借助collections.OrderedDict实现move_to_end和popitem都是O(1)操作思路与双链表完全同构。class LRUCache: def __init__(self, capacity: int): from collections import OrderedDict self.capacity capacity self.cache OrderedDict() def get(self, key: int) - int: if key not in self.cache: return -1 self.cache.move_to_end(key) return self.cache[key] def put(self, key: int, value: int) - None: if key in self.cache: self.cache.move_to_end(key) self.cache[key] value if len(self.cache) self.capacity: self.cache.popitem(lastFalse)这份代码的核心逻辑全在“move_to_end”和“popitem(lastFalse)”两句上前者把最新用过的挪到末尾后者弹出开头的“最老”元素。面试时如果你明确说“我用OrderedDict模拟双链表”对方一般也能接受。7.2 面试建议Python也最好能手写链表虽然OrderedDict写法简洁但有些面试官要求必须手写Node和链表结构。Python写双向链表不复杂关键是别用列表模拟链表否则删除中间节点时你会很痛苦。手写版的思路和Java一致定义DLinkedNode类维护head、tail哨兵写removeNode、addToHead、removeTail三个工具方法。语言不同指针换成了引用但逻辑完全一样。如果你时间充裕我建议Python也把双链表版默写一遍这样无论面试官用什么语言要求你都能接得住。最后分享一点个人的实操体会这道题我前前后后教过不少人也看他们在面试里出过各种状况。我自己印象最深的一次翻车是早年把addToHead的四行顺序写反了本地跑的时候直接死循环排查了半天才发现是head.next赋值写早了。那次之后我就给自己定了一条规矩“先node后head”头插永远先改node的prev和next再去动head.next。这条规矩后来再也没让我在链表操作上出过错。所以你练这道题的时候建议也给自己提炼这样一句“保命口诀”关键时刻比记整段代码可靠得多。面试时还有个小技巧写完代码不要立刻说“写完了”一定要自己按着get和put各推演一遍。拿一个容量为2的缓存跑一遍数据流程出声讲“先插1头部变成1再插2头部变成2get(1)把1挪到头部put(3)超容量把尾部2淘汰”。这一步演示比你说一万句“我的代码逻辑正确”都有说服力面试官能看到你的工程习惯和边界意识。