LRU缓存这道题在LeetCode高频手撕题里属于顶流中的顶流T0级别没有任何争议。面试考它考的不是你会不会用现成的LinkedHashMap而是你能不能从零手写一个“哈希表双向链表”的LRU缓存机制在O(1)时间内完成get和put。这篇博文就专门针对这个题把思路拆到骨头缝里给你一份可以直接背的Python实现再把正常人容易踩的坑全部摆出来。不管是准备大厂面试、暑期实习还是日常刷题查漏补缺这题都绕不过去。另外先提一句网上很多帖子拼写是Leecode其实正确的应该是LeetCode不过大家都看得懂也无所谓了。1. 为什么LRU缓存是T0级手撕题1.1 面试官到底在考察什么手撕题目分三六九等很多题属于“刷过就会没刷就懵”的类型但LRU缓存不是。它考的是三件很难同时做到位的事数据结构组合能力、边界条件处理、复杂度分析。第一数据结构组合能力。你需要在哈希表和一个双向链表之间建立映射关系。哈希表负责O(1)的查找双向链表负责O(1)的插入和删除。如果不理解为什么会用这两种结构真让你手写代码的时候一定会卡在“如何把两者串起来”这一步。第二边界条件处理。LRU看起来逻辑很简单——容量满了删除最久没用的那个。但实际写代码时你会遇到缓存容量为1、key不存在、插入已存在的key、删除后链表指针是否正确等一堆边界情况。很多人在LeetCode上一遍过是因为用语言自带的库比如Java的LinkedHashMapPython的collections.OrderedDict。一旦让你手写瞬间暴露真实水平。第三复杂度分析。面试官一定会追问你的get和put为什么是O(1)如果链表是单向的删除一个节点为什么退化成O(n)这些追问没有深刻理解底层原理是答不上来的。1.2 LRU到底是什么LRU是Least Recently Used的缩写翻译成中文。严格来说是“最近最久未使用”但大多数人口语里就说“最近最少使用”意思是一个东西越久没被访问。就越应该被淘汰。用生活化的例子来说就像你手机里的后台应用列表。打开一个新应用时它排在最前面。当你不断打开新应用最久没用的那个就会从后台被踢掉。对于一个缓存系统你要做到两点。get一个key的时候如果存在把它标记为“最近刚用过”。put一个key的时候如果容量满了淘汰掉“最久没用的那个”。这规则并不复杂复杂的是怎么在代码里设计数据结构支撑它。1.3 这题的难度定位LeetCode上的原题编号是146标记为中等难度。但实际面试中这题经常被当作难题来问因为面试官会根据你的实现方式不断加深追问。比如你写出的get函数放在一整个类里面试官会问这个类是否线程安全如果两个线程同时get和put会怎样如果放在Redis缓存场景里你的这个设计能不能扛住?别急着回答先把基础版本写出来后面我们会展开讲这些。2. 思路拆解为什么是哈希表加双向链表2.1 只用链表行不行如果只用链表get一个节点时为了判断key是否存在你至少要遍历一次链表这就是O(n)。在缓存场景里这个效率无法接受因为缓存存在的意义就是快。如果只用哈希表呢哈希表确实能O(1)找到key对应的value但你无法知道哪个key是最久没用的。哈希表本身是无序的你还需要一种结构来记录访问先后顺序而且这个结构必须支持O(1)地删除和插入。所以结论是哈希表负责两件事快速找到key对应的链表节点快速判断key是否存在。双向链表负责两件事维护访问顺序支持O(1)删除节点。两者缺一不可。2.2 为什么必须是双向链表很多初学者会问单链表也能做到O(1)的头部插入和头部删除但你要删除的往往不是头部节点而是中间任意一个节点甚至可能是尾部节点。如果你想删除某个节点在单链表里你需要知道它的前驱节点才能把它摘下来否则链表就断了。但单链表要找到前驱节点只能从头遍历又变成了O(n)。双向链表就不存在这个问题每个节点既有prev指针也有next指针当前节点可以O(1)拿到它的前驱和后继实现“自我删除”。这个“自我删除”的操作是整个LRU实现里最精髓的一部分。把这段逻辑想清楚了下面所有代码读起来都会非常顺。2.3 哨兵节点的妙用手写双向链表的另一个关键点是哨兵节点也就是dummy head和dummy tail。我可以直接告诉你我的经验真实面试里用哨兵节点是目前最优的写法。为什么因为如果没有哨兵节点你在删除节点时必须判断删除的是不是链表头部是不是链表尾部在新增节点时也要判断链表是否为空。每一种判断都是一个容易写错的地方而哨兵节点让这些边界情况全部消失了。所谓哨兵节点就是两个虚构的节点head和tail它们本身不存储任何真实数据只是作为标记保证链表永远不会为空。真实的节点永远在head和tail之间这样一来所有对链表的操作都不需要再特殊处理“空链表”的情况大大降低代码出错率。2.4 思路总览现在把整个流程先走一遍心里有个完整的画面。定义一个Cache类内容是一个capacity容量、一个哈希表cache、一个双向链表。get(key)先从哈希表查如果不存在返回-1。如果存在找到对应节点把它从当前位置移到链表头部然后返回value。put(key, value)如果key已存在更新节点的value并把节点移到链表头部。如果key不存在新建一个节点插入链表头部并放进哈希表。接着判断当前节点数是否超过容量如果超过删除链表尾部的真实节点同时删除哈希表中对应的key。整个过程的核心原则是每次访问或新增一个节点它都必须被挪到链表头部。链表从头部到尾部节点新鲜程度从新到旧。最久没用的永远在链表尾。3. 可直接背的Python实现3.1 完整代码下面直接放一份我简化到极致但又保留了所有细节的Python实现把.py后缀标注清楚方便直接复制。class Node: def __init__(self, key0, value0): self.key key self.value value self.prev None self.next None class LRUCache: def __init__(self, capacity: int): self.capacity capacity self.cache {} self.head Node() self.tail Node() self.head.next self.tail self.tail.prev self.head def _remove_node(self, node): node.prev.next node.next node.next.prev node.prev def _add_to_head(self, node): node.next self.head.next node.next.prev node node.prev self.head self.head.next node def _move_to_head(self, node): self._remove_node(node) self._add_to_head(node) def _pop_tail(self): node self.tail.prev self._remove_node(node) return node def get(self, key: int) - int: if key not in self.cache: return -1 node self.cache[key] self._move_to_head(node) return node.value def put(self, key: int, value: int) - None: if key in self.cache: node self.cache[key] node.value value self._move_to_head(node) return if len(self.cache) self.capacity: node self._pop_tail() del self.cache[node.key] new_node Node(key, value) self.cache[key] new_node self._add_to_head(new_node)这是我在多次面试后最终沉淀下来的版本核心逻辑非常干净。别小看这份代码面试时你光默写是不够的还得能解释每一行为什么这么写。下面拆开讲。3.2 初始化阶段__init__里做了四件事保存容量、初始化空哈希表、创建两个哨兵节点、让两个哨兵节点互相指向对方。self.head Node() self.tail Node() self.head.next self.tail self.tail.prev self.head此时链表没有任何真实节点相当于一个空链表。注意哨兵节点本身不存任何有效数据在Node的默认参数里key和value都是0但这0会被覆盖成真实数据留给新建节点时用。这里有个常见的面试追问为什么不用self.head None然后每次操作都判断链表是否为空答案很简单哨兵节点让链表永远处于“非空”状态这样_remove_node和_add_to_head里不需要做任何空指针判断代码更简洁、更不容易出错。3.3 链表核心操作代码里有三个私有方法_remove_node、_add_to_head、_move_to_head。这是整个类的心脏。_remove_node就是让当前节点的前后两个节点绕过它直接连起来。这个操作在任何位置都能用因为双向链表给了我们前驱和后继的引用。def _remove_node(self, node): node.prev.next node.next node.next.prev node.prev注意这两行不能交换顺序。你想想如果先执行node.next.prev node.prev此时node.next还是好的没问题。但如果先修改了node.prev.next然后第2行用node.next.prev两者其实互不影响因为node.next还没变。不过更稳妥的写作习惯是第1行先处理“前驱的后继”第2行处理“后继的前驱”。如果你非要倒过来逻辑上其实也不会出错但容易在读代码时引起混乱。面试时你按这个顺序写最标准。_add_to_head要把新节点插到head哨兵节点之后。def _add_to_head(self, node): node.next self.head.next node.next.prev node node.prev self.head self.head.next node这四行的顺序很讲究。最容易出的错是先让self.head.next node然后才去设置node的next和prev结果node.next指向了自己链表就闭环了。正确的顺序是先让新节点和原来第一个真实节点建立联系再让新节点和head建立联系。_move_to_head就更简单了先删再加两步。之所以能这么优雅完全得益于双向链表和哨兵节点。def _move_to_head(self, node): self._remove_node(node) self._add_to_head(node)这两个操作的时间复杂度都是O(1)这也是整道题能保持O(1)的关键。3.4 get方法的实现get的逻辑非常短只有三行有效代码。def get(self, key: int) - int: if key not in self.cache: return -1 node self.cache[key] self._move_to_head(node) return node.value第一行查哈希表判断key是否存在不存在直接返回-1这是LRU题目硬性要求。存在的话通过哈希表拿到对应的链表节点然后把它移动到链表头部。移动的意义是这个key刚刚被访问了它不再是“最久未使用的”应该拥有“不被淘汰”的新鲜身份。这里有一个绝大多数人忽略的细节get操作也会改变链表的顺序。这也是LRU和FIFO最大的区别FIFO淘汰的是最先插入的而LRU淘汰的是最久没有被访问的。get一次相当于给了这个key一条命它又变“新”了。3.5 put方法的实现put分为两种情况key存在和不存在再叠加一个容量满的场景。def put(self, key: int, value: int) - None: if key in self.cache: node self.cache[key] node.value value self._move_to_head(node) return if len(self.cache) self.capacity: node self._pop_tail() del self.cache[node.key] new_node Node(key, value) self.cache[key] new_node self._add_to_head(new_node)如果key已经存在不新建节点直接复用旧节点更新value然后把它移动到链表头部。为什么不新建因为如果不复用旧节点还在链表里新节点又插进去哈希表指向新节点后旧节点就变成了一堆无法被访问到的孤立节点占用内存不说逻辑也会混乱。如果key不存在先把新节点创建出来。但在插入之前要先判断容量。如果当前哈希表大小已经大于等于容量上限就调用_pop_tail()把链表尾部节点弹出。弹出后必须立刻从哈希表里删掉它的key这一步很容易忘很多人会漏掉del self.cache[node.key]这一行。删掉之后缓存就空出一个位置再把新节点插入链表头部写入哈希表。这里有个非常关键的边界场景容量为1时。put了一个key之后再put另一个新key触发了容量满的淘汰逻辑。淘汰的是哪一个是链表尾部那个。因为新key还没插入链表尾部就是旧key所以旧key被正确淘汰新key被插入逻辑没问题。但如果顺序反了先把新key插进去再淘汰淘汰的就是新key了肯定不对。所以“先淘汰再插入”的顺序必须刻在脑子里。3.6 代码背诵的三个抓手如果你现在想去背代码建议不要死记硬背而是按下面三个抓手来拆着背。抓手一双向链表的四个核心操作删除节点、头部添加、移动节点、弹出尾节点。抓手二哈希表和链表节点一一对应哈希表的value存的是“节点”而不是“值”这个“节点”里才有真正的key和value。抓手三put的三种情况更新已存在、插入新节点且容量没满、插入新节点且容量已满。背的时候可以在纸上画一个容量为2的LRU图手动模拟几次put和get流程画几遍之后你会发现自己根本不需要背代码逻辑清楚了下笔就是代码。4. 高频细节坑点与面试追问实录4.1 get时要不要判断容量大于0有一个容易出现歧义的细节如果LRU的capacity为0怎么办构造函数里传入0那么任何put操作都会触发淘汰逻辑最终哈希表永远为空任何get都返回-1。真实面试里倒很少出这种刁钻条件但你在LeetCode上提交时测试用例不会包含capacity为0的情况。为了稳妥可以在__init__里加一句if capacity 0: raise ValueError(Capacity must be positive)或者直接在put里处理掉。我个人倾向于抛异常让调用方提前发现配置问题。4.2 value为0或者None时有没有区别在我们这个实现里Node的value可以是任何值包括0、None、负数。get返回-1只表示key不存在不表示value不能等于-1。这个设计要特别注意不要写成if node is None也不要因为value等于-1而误判。哈希表里只要存在该key返回的就是真实value。4.3 为什么哈希表的value要存节点而不是值这是最容易被问的一道送命题但其实想想就知道如果哈希表只存value那么链表里的节点没办法通过哈希表索引到因为get的时候你需要找到链表节点然后把它移动到头部而不是只返回一个值。所以哈希表的value必须存“链表节点对象”这样才能同时拿到key、value以及前后指针。4.4 为什么不用Python的OrderedDictLeetCode上确实有考核这题的兄弟题比如“LRU Cache”可以被OrderedDict一行实现。但面试官让你手写考的是你会不会手写双向链表而不是你会不会调库。有一次我面试如实说了“Python的OrderedDict底层就是哈希表加双向链表”面试官马上追问“那你解释一下OrderedDict底层是如何实现O(1)删除的”还是得回到手写层面。所以我的建议是调库版本自己私下懂就行面试时还是老老实实手写Node类。4.5 线程安全怎么答如果面试官问“你的LRU是不是线程安全的”答案是“不是”。因为多线程同时读写同一个LRU实例时链表可能会被破坏哈希表也可能出现不一致。最简单的解决办法是加一把全局锁用threading.Lock把get和put都包起来。但这样每次访问都需要竞争锁性能会下降。更细粒度的解决办法是分段锁把哈希表分成多个段每段一把锁只锁当前段涉及的链表操作。但这个复杂度在面试题里通常不会被要求实现能把全局锁讲清楚已经足够应付绝大多数面试。4.6 背诵时的常见错位顺序我见过很多人在默写时犯同一个顺序错误——_add_to_head里先改了self.head.next再改node的指针导致链表死循环。你可以用下面这个小口诀来记先连新节点的两个空位再拆head的旧连接。具体来说就是先设node.next和node.prev再更新node.next.prev和head.next。这里我再单独列一下标准步骤的写法。def _add_to_head(self, node): node.next self.head.next node.prev self.head node.next.prev node self.head.next node注意这里和之前的版本顺序稍有区别但不影响正确性。关键在于一定要先保证node成功接管了“链表的第一个真实节点”这条连接再去更新head的next指向node。头尾两个判断都不需要因为有了哨兵节点。5. 如何把LRU缓存用成“肌肉记忆”5.1 同题型扩展训练LRU这道题的价值远不止于让你背会一个模板。它是未来一大坨题目的地基。比如LFULeast Frequently Used、Redis的缓存淘汰策略、ThreadLocal源码里对ThreadLocalMap的清理策略都涉及链表节点移动和哈希表映射。你如果LRU能手写得很熟后面学LFU会轻松很多因为LFU的实现是在LRU基础上再加一个频率维度的结构。我自己的刷题习惯是先把LRU默写三遍确认不看代码也能通过然后立刻做「146. LRU 缓存」的原题。接着再用OrderedDict写一个简单版对比体会手写和调库的差异。最后去找两道同样是“哈希表 双向链表”结构的题比如“全 O(1) 的数据结构”做完之后你会发现自己对这类题的敏感度完全不一样了。5.2 面试时怎么边写边讲面试和LeetCode做题有一个很大的区别LeetCode只要跑过用例就行面试官却会盯着你写代码的过程听你解释思路。建议你按这个顺序讲先说设计目标get和put都要O(1)。再说为什么O(1)哈希表负责O(1)查找双向链表负责O(1)删除和插入。展示哨兵节点避免边界判断。写代码时每写完一个方法就简单说一句它在做什么。比如写_add_to_head时可以顺口说“这里把node插到head后面顺序是先把node的next指向原来的第一个真实节点再更新它的prev和head的next”。用这种“代码等同于讲解”的方式面试官会觉得你是真懂而不是背的。5.3 怎么防止当场紧张写错很多面试者会有一种情况代码背熟了但一上黑板就紧张写着写着乱了。解决这个问题没有捷径只有一个笨办法默写时不看答案每次卡住就记录卡在哪个方法然后重点突破。我发现90%的人卡住的位置就是_add_to_head的四行顺序剩下10%是忘记del self.cache[node.key]。针对这两个薄弱点你可以给自己出几个特殊用例容量为1put两个不同key。容量为2get一个老key后put一个新key验证老key是否又变“新”了。put一个已存在的key再容量满时put另一个新key验证旧key顺序是否正确。把这些用例画在草稿纸上模拟一遍指针变化基本就不会错了。5.4 亲手画一遍LRU状态流转我建议你准备一张纸画一个容量为2的LRU完整走一遍下面这个序列。每一步都画出链表并在图中标出哈希表内容这一步能做到手撕就稳了。初始head - tailcache为空。put(1, a)新建节点1插入头部cache变为{1: node1}。put(2, b)新建节点2插入头部cache变为{1: node1, 2: node2}。get(1)节点1移到头部链表顺序变为1、2。put(3, c)容量满先弹出链表尾部节点2再插入节点3。链表变为1、3cache删掉key2加入key3。这个手动模拟过程走三遍比任何讲解都有用。6. 各路语言实现差异与手写通用思路6.1 Java版本Java面试遇到这题的概率很高因为Java自带LinkedHashMap面试官往往要求你禁用它来手写。Java手写版本需要定义一个static class Node包含int key、int value和前后指针然后构造双向链表。操作逻辑和Python完全一致只是在指针操作上用.取出对象引用另外删除节点后还需要手动处理哈希表的移除。这里不贴完整Java代码了因为讲核心思路的话上面Python版足以你可以把Python代码逐行翻译成Java注意Java里Node是引用类型赋值时拷贝的是引用比Python还要直观一些。6.2 Go版本Go面试也越来越多手写时需要格外小心一点Go没有内置的链表容器所以Node得自己定义而且指针操作和Python相比更原始容易出现空指针引用。建议Go版本里所有涉及node.prev或node.next的地方都要想一想是否为nil虽然哨兵节点已经避免了大多数nil问题但删除节点时还是要确认节点确实在链表中。还有一种“奇技淫巧”是在Go中用container/list加map[int]*list.Element实现但手写题的主要目的是考察数据结构能力用库就没有手写意义。敢于手写Node类本身就是在向面试官传达你对底层结构的理解程度。6.3 C版本C需要手动管理内存Node用new创建删除节点时delete容易出现内存泄漏。如果你的代码里只用智能指针面试官可能会说这不行因为引用的计数会增加额外开销。但面试场景里大多数讨论停留在算法层面内存管理只要提一句“用delete释放被淘汰节点避免泄露”就差不多了。有一点值得注意C的unordered_map里value存的是list的iterator在list插入或删除元素后iterator仍然有效这是list和vector最大的区别。很多C候选人会用vector存iterator结果一旦插入就全失效了这是典型的错误。再用list写一次会顺很多。7. 实战中的那些坑一次性说干净7.1 删除尾节点后哈希表不同步这是我见过最多人犯的错误没有之一。代码里弹出链表尾节点后只删除了链表中的节点却忘了从哈希表里删掉它的key。这种情况在LeetCode测试用例中很难暴露因为你的get可能永远不会访问被删的key但面试官一眼就能看出来。因为他会追问“你的哈希表里还存着这个key吗”顿时原形毕露。所以每次写_pop_tail后面必须紧跟着del self.cache[node.key]这个习惯可以刻进肌肉记忆。7.2 链表顺序和哈希表顺序不一致哈希表本身是无序的不要试图依赖哈希表的迭代顺序去推断LRU顺序。我见过有人用Python 3.7之后字典的有序性来实现LRU用move_to_end来模拟移动操作。这种做法虽然能跑通而且只需要几十行代码但它不是你手动写出来的“哈希表双向链表”的组合面试时如果被追问“双向链表的具体实现细节”你就露馅了。所以面试时千万别用这种快捷方式。7.3 容量小于0的输入虽然LeetCode不会给你这样的测试用例但作为工程人员你应该在构造函数里做防御性处理。capacity 0要么抛异常要么直接把所有put当成什么都不做。我更推荐抛异常因为一个无法存储任何数据的缓存类本身就是一个错误配置沉默地忽略只会让问题更隐蔽。7.4 value类型的细节有的版本会要求key和value都是int类型有的允许泛型。如果只按int处理在Java泛型里可能要用Integer或者包装类。Python版本用类型标注就不会有这个问题。但面试时如果面试官说“value是一个对象怎么办”你只需要说明Node里存的是对象的引用数据结构本身不关心具体类类型即可。7.5 把复杂问题简单化的能力这道题终究是一个数据结构设计题考察的重点不是算法里的数学技巧而是你能不能把“哈希表查找快”和“链表顺序调整快”这两个看似不相关的优点组合在一起。面试官看的是你的思考方式而不是你背的代码。所以即使你现在能全部默写出来也建议你像上面那样手动模拟一次状态流转把指针的每一次变化都搞明白。你越理解底层越不用靠背。我是一个刷了很多年题、也面了很多次试的老兵LRU这题真是被问过太多遍了。每次面到它我都会有种“老朋友又来了”的感觉。最后分享一个自己的小习惯我在面试前会把LRU默写一遍不看代码纯靠记忆加理解大概五分钟内能写完写完还会在注释里标一下每个方法的时间复杂度。这个动作为我节省了不少临场思考的时间也让我有信心在写代码的同时还有余力做口头讲解。希望这篇拆解也能帮你把这道T0级手撕题彻底踩平让它成为你的送分题而不是拦路虎。后面的高频题还有很多LRU只是热身先把这一关过了再说。