LRU缓存这道题，算是LeetCode高频题里少有的几个“T0级别”存在。我前后面试过不少公司，不管大厂小厂，手撕算法题环节十次里有四五次能看到LRU的影子，LinkedHashMap那种黑盒写法能不能过完全取决于面试官心情，但手写双链表加哈希表的经典实现几乎就是标准答案。今天这篇就是把这道“可直接背”的题掰开揉碎，给你一套能默写的模板，顺带讲清楚每一步为什么这么写，以及面试官坐在对面盯着你写时，哪些地方最容易翻车。
1. 题目到底在考什么：先看清LRU的庐山真面目
1.1 原题描述与真实场景
力扣146题的描述其实很短：设计一个LRUCache类，构造函数传入容量capacity，实现get(key)和put(key, value)两个方法。get时如果key存在就返回值，不存在返回-1；put时如果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 哈希表负责“找得快”，链表负责“记得住顺序”
两个数据结构组合起来，职责非常清晰：
- 哈希表Map<key, 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里有key，map里以key为键找到node。这样无论是get、put还是淘汰，都能O(1)完成闭环。
2.4 哨兵节点的妙处：不怕空链表也不用判空
再来看链表头的虚拟头节点head和虚拟尾节点tail。这俩是“哨兵节点”，不存真实数据，只作为边界标记。head.next指向真正的第一个节点，tail.prev指向真正的最后一个节点。
这样设计最大的好处是：处理链表插删时不需要对空链表做特殊判断。如果不用哨兵，插入第一个节点和插入普通节点逻辑不一样，删除最后一个节点和删除中间节点逻辑也不一样，一旦写错就是空指针或者丢数据。有了哨兵，头插和尾删永远都是同样的四行指针操作，代码能短一截，出错概率也低一截。
实际写代码时，初始化就让head.next指向tail、tail.prev指向head，一个空链表就表示好了。后面所有操作都在这两个哨兵之间进行，边界和安全都很好处理。
下表把各角色的分工再捋一遍：
| 角色 | 作用 | 实现要点 |
|---|---|---|
| 哈希表 | O(1)定位节点 | Map<Integer, Node>，value存节点引用 |
| 双向链表 | 维护访问顺序 | 头=最近使用，尾=最久未使用 |
| 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 Map<Integer, 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.next，node.next.prev指向node.prev。这里不需要处理node自己的prev和next，因为被摘除的节点已经没用了，后续如果还要用（比如moveToHead），会让addToHead重新给它赋值prev和next。
addToHead(node)：头插一个节点。四行代码的顺序是固定的：先设置node.prev为head，node.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 复杂度与记忆常见性能对照
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| get | O(1) | map查找一次，链表移动是常数次指针操作 |
| put | O(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 = node，node的前驱指向自己，链表彻底乱了。
避坑技巧：头插永远先“补新节点的线”，再“动head的线”。前两行是node.prev和node.next，后两行才是head.next.prev和head.next。只要这个顺序不断，自环就不会发生。
5.2 removeNode时多写了多余的“清空”操作
有些人在removeNode里会顺手写node.prev = null; node.next = null;，觉得这样更干净。这在你不再使用这个节点时没问题，但moveToHead会先把节点remove掉再addToHead——如果你清空了prev和next，addToHead时就要重新补两行赋值，虽然也能写对，但平白多了出错的窗口。
我的建议是：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 LinkedHashMap<Integer, 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.Entry<Integer, 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(last=False)这份代码的核心逻辑全在“move_to_end”和“popitem(last=False)”两句上：前者把最新用过的挪到末尾，后者弹出开头的“最老”元素。面试时如果你明确说“我用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，头部变成2；get(1)把1挪到头部；put(3)超容量，把尾部2淘汰”。这一步演示比你说一万句“我的代码逻辑正确”都有说服力，面试官能看到你的工程习惯和边界意识。
