最近帮一个准备跳槽的朋友做模拟面试连着三次让他手写 LRU 缓存淘汰算法三次都在细节上翻了车。这道题在 Python 岗位的笔试和一面里出镜率极高今年我看到的各家题库里已经出现了不少变体。LRU 全称 Least Recently Used翻译过来就是“最近最少使用”属于缓存淘汰策略里最经典的一种缓存空间有限放不下所有数据时就把最久没被访问的那些数据先请出去。很多同学能背出“哈希表加双向链表”这个标准答案但真到了白板编程或在线编辑器里从定义节点到处理边界条件能一次写对的人并不多。这篇文章就按我在面试现场和实际项目里用过无数遍的思路把这道题从头到尾拆开讲清楚适合正在准备大厂 Python 岗位面试的同学也适合想给自己的服务加一层本地缓存但不知道从哪下手的工程师。1. 先搞清楚 LRU 是什么面试官到底在考什么1.1 用生活场景理解缓存淘汰缓存淘汰算法解决的是一个非常朴素的问题存储空间有限放不下所有数据当新数据要进来的时候必须把某些旧数据赶出去那么应该赶谁走LRU 的策略简单说就是“谁最久没被用过就先淘汰谁”。这个规则可以类比成整理书架你面前有一个只能放五本书的小书架每天都要翻书复习。如果你已经两天没有碰过某本书而新买的参考书又必须上架那你大概率会把那本最久没翻的书收进箱子里。手机后台任务管理也是一样系统内存吃紧时优先杀掉那些很久没切换的应用而不是刚打开正在用的应用。缓存系统里有一个核心指标叫“命中率”。如果数据在缓存里能查到就是一次命中查不到就得去数据库或远程服务取成本高得多。淘汰策略的目标就是尽量保住那些未来最可能被访问的数据。LRU 的基本假设是如果一个数据刚被访问过那么接下来短时间内再被访问的概率也很高反过来如果一个数据很久没被访问那它在未来被访问的概率也在不断下降。这个假设在很多真实负载下是成立的所以 LRU 才会成为使用最广泛的淘汰策略。1.2 大厂为什么偏偏拿这道题考你面试官考手写 LRU不只是想看你知不知道这个算法而是通过一道二三十行的代码同时考察好几层能力。第一层是数据结构基础。LRU 的标准解法是“哈希表 双向链表”哈希表负责 O(1) 的查找双向链表负责 O(1) 的删除和移动。这两者的结合是非常经典的设计题很多人单身链表都操作不利索更别说带哨兵节点的双向链表了。第二层是算法复杂度意识。你不仅要写出功能正确的代码还要能解释清楚为什么 get 和 put 都是 O(1)。如果实现里出现遍历链表找节点、删除节点时从头扫描前驱这类操作复杂度就退化成了 O(n)这道题基本就废了。第三层是工程边界感。容量为 0 怎么办重复写入同一个 key 怎么办put 一个已经存在的 key 时要不要更新链表顺序这些看起来很小的细节恰恰是线上事故最常见的导火索。面试官出这道题其实就是想看你的代码有没有防御性能不能想到普通用户不会去测但生产环境一定会遇到的场景。第四层是方案取舍能力。如果你能主动说一句“其实 Python 里可以用 OrderedDict 实现但工程中有得也有失”面试官对你的印象会明显不一样。这代表你不是只背了题而是真的理解背后 trade-off。这道题看起来是在考代码实际上是在考一名工程师面对空间有限、时间敏感、访问模式不确定时的综合决策能力。想明白这一点你就知道这篇文章后面要讲的东西都很关键。2. 设计一个 O(1) 的 LRU哈希表加双向链表缺一不可2.1 为什么数组和单链表都不行先看一个很自然的想法给每个 key 记录一个最近访问时间戳每次淘汰时扫描全部 key找出时间戳最小的那个删掉。这个方案能实现但是淘汰操作是 O(n)一旦缓存条目数量达到几千几万每次写入都要做全量扫描性能完全扛不住。更麻烦的是时间戳本身会随高频访问快速膨胀还得处理精度问题。用单链表维护访问顺序也不够。单链表可以做到 O(1) 在头部插入新节点但删除一个中间的节点时你必须知道它的前驱节点是谁。单向链表没有指向前驱的指针只能从头开始遍历找到前驱又是 O(n)。如果你想淘汰的是尾节点更是得遍历整个链表。哈希表加双向链表之所以是标准答案是因为这两者做到了完美的互补。哈希表让你能在 O(1) 时间内定位到任意一个 key 对应的链表节点双向链表让你能在拿到节点后以 O(1) 代价把它从当前位置移除并放到链表头部。链表的头部永远表示“最近被访问过”尾部永远表示“最久没有被访问”淘汰时只需要斩掉尾节点。2.2 哨兵节点的价值很多人第一次写双向链表时会在头尾边界判断上栽跟头链表为空时怎么处理只有一个节点时怎么处理每次插入删除都要写一堆 if 分支容易漏也容易错。一种更省心的做法是引入哨兵节点也叫 dummy head 和 dummy tail。它们在初始化时就互相指向对方形成一条空链表。真实的节点永远夹在这两个哨兵中间头部的哨兵不对应任何真实数据尾部的哨兵也不对应任何真实数据。这样设计的好处是在链表不为空的情况下所有操作都不需要特殊判断。往头部插入节点时永远有一个真实的 head.next 存在删除尾节点时永远有一个真实的 tail.prev 存在。代码更短边界更少出错概率更低。2.3 节点里为什么必须存 key这是一个非常容易被忽略的设计点。链表节点里除了 value通常还会存一份 key。为什么因为当你要淘汰最久未使用的节点时不光要把这个节点从链表里摘除还要把它从哈希表里删掉。摘除节点时我们手里只有这个节点的对象如果对象里没有 key你就无法从哈希表中定位并删除对应的条目。这个细节平时写代码可能感觉不出来但面试官只要在代码里看到你没存 key几乎都会追问一句“那淘汰的时候你拿什么去删哈希表”如果你愣住了说明你对整个数据结构之间的联动关系还没有真正理解。2.4 操作流程拆解把整体流程想清楚再动手写事半功倍。当 get 一个 key 的时候先去哈希表查。查不到返回 -1查到了把这个节点从链表当前位置挪到头部然后返回它的 value。这里有一个细节get 也算一次访问所以必须调整链表顺序否则这个 key 的“最近使用”属性就不会被刷新。当 put 一个 key 的时候先查哈希表。如果 key 已经存在直接更新节点的 value然后把它挪到头部。注意这个步骤很多新手会写成“先删旧的再插新的”逻辑没错但白白多了一次节点创建和哈希删除没必要。如果 key 不存在就创建一个新节点插入链表头部写入哈希表然后让容量计数加一。如果容量计数超过了限制就把尾节点摘除同时在哈希表里删掉它对应的 key最后把容量计数减回来。整个流程里哈希表、双向链表、容量计数三个东西必须始终保持一致。很多 bug 都出在“链表删了但哈希没删”或者“哈希加了但链表没加”这一类不一致问题上。3. 手写代码完整实现与每个方法的逐行拆解3.1 节点定义与初始化直接上代码我写的这版是网上流传最广、面试中也最稳的写法。class DLinkedNode: def __init__(self, keyNone, valueNone): self.key key self.value value self.prev None self.next None class LRUCache: def __init__(self, capacity: int): if capacity 0: raise ValueError(capacity must be positive) self.capacity capacity self.size 0 self.cache {} self.head DLinkedNode() self.tail DLinkedNode() self.head.next self.tail self.tail.prev self.head构造函数里有两个值得说的点。第一我直接对 capacity 做了校验小于等于 0 时抛异常。很多面试题默认容量合法但实际工程里这种防御式写法会给你加分。第二head 和 tail 两个哨兵节点互相指着对方一开始链表就是空的之后所有真实节点插入后都会出现在这两个哨兵之间。3.2 两个最基础的链表操作def _remove_node(self, node): node.prev.next node.next node.next.prev node.prev def _add_to_head(self, node): node.prev self.head node.next self.head.next self.head.next.prev node self.head.next node_remove_node 的思路是让当前节点的前驱直接指向当前节点的后继让当前节点的后继直接指回前驱这样就绕过了这个节点本身。操作完成之后这个节点就处于“悬空”状态除了它自己还留着 prev 和 next 的引用链表里已经没有任何指针指向它了。垃圾回收会把它清理掉。_add_to_head 是四步操作顺序一定要对。先让新节点的 prev 指向 head让新节点的 next 指向当前真正的第一个节点然后把第一个节点的 prev 指向新节点最后把 head 的 next 指向新节点。很多人喜欢反过来写先动了 head.next后面就找不到原来的第一个节点了。这个顺序只要写错一次链表就断掉运行时会直接报错或者死循环。_set_关键的逻辑是把“移动节点到头部”这个复合操作进行复用。移动本质上就是两步先从当前位置摘除再插到头部。def _move_to_head(self, node): self._remove_node(node) self._add_to_head(node)写完你会发现get 和 put 的核心动作都是这个 move_to_head代码变得非常简洁。3.3 get 和 put 的完整逻辑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) else: new_node DLinkedNode(key, value) self.cache[key] new_node self._add_to_head(new_node) self.size 1 if self.size self.capacity: removed self.tail.prev self._remove_node(removed) del self.cache[removed.key] self.size - 1get 的逻辑很简单查得到就移动并返回值查不到就返回 -1这是题目给定的接口行为。put 分两种情况。key 存在时更新 value 之后要移动到头部这一步很多人漏掉。key 不存在时先创建节点、写哈希、插头部、size 加一然后判断是否超出容量。超出容量时尾哨兵的前一个节点就是最久没被使用的节点把它摘掉并在哈希表里删除对应 key。到这里一个完整的 LRUCache 类就成型了。总代码量不到六十行但数据结构和算法细节全在里面。3.4 用面试官视角测试这段代码代码写完不能直接说“好了”要当场验证这个习惯非常加分。我会在脑子里或者直接在编辑器里跑这几组用例。第一组容量为 1 的基本场景。put(1, 1)再 put(2, 2)此时 1 应该被淘汰get(1) 返回 -1get(2) 返回 2。第二组重复 put 同一个 key。put(1, 1)put(1, 2)get(1) 应该返回新值 2并且链表头部是 1。第三组经典容量 2 的场景。put(1, 1)、put(2, 2)、get(1) 返回 1 并且把 1 挪到头部此时最久未使用的是 2。然后 put(3, 3)2 被淘汰get(2) 返回 -1get(1) 和 get(3) 正常。这几组用例能覆盖大部分逻辑分支。我建议你在自己的电脑上敲一遍加几个 print 看链表里的节点顺序。这里推荐一个调试技巧写一个 debug 方法遍历整个链表并打印 key 序列比如“head - 1 - 2 - tail”这样每次操作后都能直观看到顺序变化定位问题非常快。4. 面试官爱追问的 6 个问题回答思路给你整理好了4.1 能简化吗Python 里 OrderedDict 版本面试官经常在你写完双向链表版本后追问一句“如果你在真实 Python 项目里会用什么更简单的写法吗”这个问题问的是你知不知道 Python 标准库里的 OrderedDict。OrderedDict 是 dict 的子类额外维护了键的插入顺序并且提供了 move_to_end 和 popitem 两个方法。基于它实现 LRU 只要十几行from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): 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[key] value self.cache.move_to_end(key) else: self.cache[key] value if len(self.cache) self.capacity: self.cache.popitem(lastFalse)这段代码把“最近使用”定义为“插入顺序的末端”每次访问一个 key 就把它的顺序移到末尾。淘汰时 popitem(lastFalse) 弹掉最开头的那个 key也就是最久没用的。这个写法在工程上多快好省不容易出链表断链的问题。但这里有一个值得主动说出来的 trade-offOrderedDict 在 Python 内部也是用双向链表实现的所以时间复杂度和手写版本没有本质差别。手写版本的优势在于你能完全控制内存布局和内部行为面试时更便于展示底层能力OrderedDict 的优势是代码更短、更不容易出错。实际项目中我会优先用 OrderedDict面试中建议先把双向链表版本写出来再主动补一句“其实 Python 里可以用 OrderedDict 简化”显得你既有底层功底又懂工程实践。4.2 能再进一步吗缓存污染问题缓存污染是一个很容易被忽略但真实存在的痛点。假设你的缓存容量是 1000某个接口突然被脚本批量刷数据一次性访问了 10000 个不重复的 key。按标准的 LRU这 10000 个 key 会顺序进入缓存把原本高频访问的热点数据全部挤出去。等刷屏结束那些真正有价值的 key 反而不在缓存里了命中率暴跌。针对这个问题工程上常见的优化方案是分段 LRU。比如把缓存分成两段刚进入的数据先放在“新手区”只有被访问超过一定次数或者存活超过一定时间才有资格进入“主缓存区”。淘汰时优先从新手区淘汰。这种设计在一定程度上抵御了突发流量对热点数据的冲击。面试时提出这一点等于告诉面试官你不只是背了一个模板而是真在缓存场景里踩过坑。4.3 复杂度证明怎么说如果面试官问“为什么你的 get 和 put 都是 O(1)”别只回答“哈希表 O(1)、链表 O(1)”要一条条拆开说。get 未命中时就是一次哈希查找O(1)。get 命中时哈希查找 O(1) 找到节点双向链表做一次摘除和一次头部插入全是固定几步指针操作也是 O(1)。put 新 key 时创建节点是 O(1)插入头部是 O(1)哈希写入是 O(1)如果触发淘汰拿到 tail.prev 这个节点是 O(1)摘除是 O(1)哈希删除是 O(1)。put 已存在的 key 时更新 value 是 O(1)移动节点到头部还是 O(1)。整个类里的每个操作都没有循环和递归所以整体时间复杂度稳定在 O(1)。空间复杂度方面哈希表加链表每一对 key-value 会产生一个节点总的空间是 O(capacity)。4.4 并发和安全怎么考虑实际工程中的缓存基本都是多线程或多进程访问的。面试官可能会问“你的 LRU 线程安全吗”手写版本里get 和 put 涉及多个指针操作在并发环境里不额外做同步就会有数据竞争。最简单的处理方式是用一把锁把 get 和 put 都包起来。锁粒度大并发性能会受一定影响但胜在实现简单。如果并发量很高可以考虑把哈希表拆成多个分片每个分片独立加锁让不同 key 的请求在不同锁上竞争。还有一种思路是缓存尽量保持不可变读取时用读写锁写入时加写锁把并发的读放大。面试时不需要你现场实现一个高并发的 LRU但能说出加锁、分段锁、读写锁这几个方向就能展现出工程意识。4.5 和 LFU、FIFO 的对比表格是最好的回答形式。算法淘汰依据适用场景核心代价LRU最近访问时间热点数据相对集中、访问带有时间局部性需要 O(1) 维护顺序内存占用略高LFU历史访问频率访问频率分布非常不均匀、少数 key 占绝大流量需要维护频率计数和最小堆复杂度高FIFO进入缓存的时间数据生命周期短、几乎没有多次访问实现最简单但可能把刚访问的热点赶出去很多同学答完 LRU 就停了其实主动对比这几个算法是很好的加分项。你可以说一句“LFU 对突发流量更友好但实现复杂度高得多FIFO 简单但不考虑访问频率淘汰可能误伤热点LRU 是一个实现与效果之间比较平衡的选择”。4.6 Redis 为什么不肯用精确 LRURedis 作为缓存界的代表在内存淘汰策略上并没有使用教科书里的精确 LRU而是用了一种“近似 LRU”的采样淘汰方案。原因很现实精确 LRU 需要维护一个全局链表每次访问都要做节点搬运对内存和 CPU 都是不小的开销。Redis 的做法是在内存达到上限需要淘汰时随机采样若干 key然后从采样集合里挑出最久没被访问的那个淘汰掉。抽样数量可以通过配置项调整默认是 5。这个方案的时间成本低内存占用小牺牲的只是淘汰的精确度。大多数访问模式下近似 LRU 的命中率已经很接近精确 LRU。如果面试官提到 Redis你就可以顺着这个话题展开一是展示你对业界经典系统的熟悉程度二是体现你理解“算法的工程落地需要考虑成本和收益”。5. 手写这道题最容易踩的 8 个坑5.1 链表断链和顺序错乱最常见的崩溃现场都出现在 _add_to_head 的四步操作顺序上。如果你先把 self.head.next 改了原来的第一个节点就找不回来了。正确顺序永远是先让新节点把两端的引用接好再动原链表里的头尾指针。还有一类坑是删除节点时只改了一半。比如忘了把 node.next.prev 指回 node.prev整个链表就像断了线的珠子遍历一遍就绕不回来。每次写完链表操作最好在纸上画一下指向关系或者跑一遍 debug 遍历打印。5.2 哈希表和链表状态不一致这个坑隐蔽且致命。大家最容易漏的是“淘汰时只在链表里摘除节点忘了在哈希表里删 key”。结果是链表长度正常了但哈希表里还残留着陈旧的条目后续 get 还能查到已经“被淘汰”的数据甚至可能出现内存泄漏。反过来也有一种错法key 存在时更新 value但没有把节点挪到头部。这会导致“最近使用”信息没有更新紧接着再 put 一个新 key 时淘汰掉的可能恰恰是刚刚更新过的数据。5.3 size 计数错乱size 是缓存里每一步操作都需要维护的状态。漏加、漏减或者重复加减都会导致淘汰时机不对。一个非常典型的错误在 put 已存在的 key 时误执行了 size 1缓存容量 2实际存了 3 个节点链表直接超容。更稳妥的做法是只在 else 分支创建新节点时加一只在淘汰节点时减一其他分支不要碰这个变量。5.4 对 capacity 边界不敏感如果面试官在题目描述里没有明确说 capacity 一定大于 0你最好在构造函数里加防御。我在实际代码里选择直接抛 ValueError并且说明理由一个容量为 0 的缓存没有任何意义让它后面抛异常反而更难排查。5.5 get 也算一次访问别忽略移动很多初学者把 get 理解成“读操作不需要改结构”这是一个大误区。LRU 的核心是“用访问时间刷新活跃度”get 本身就是一次访问行为。如果你在 get 命中的时候不移动节点一个热点 key 即使天天被读也会因为它很久没被 put 而排在链表尾部被淘汰掉。5.6 调试技巧打印链表和哈希表强烈建议在类里临时加一个 debug 方法def debug(self): keys [] cur self.head.next while cur ! self.tail: keys.append(cur.key) cur cur.next return keys每次 put 或 get 之后打印一次比如执行 put(3, 3) 后链表应该显示 [3, 1, 2]就能立刻发现顺序是否符合预期。面试时你可以说“我先用 debug 方法确认一下再提交”这不是示弱是专业的表现。5.7 常见问题速查表症状可能原因修复方向运行时报 NoneType 没有 next哨兵节点没初始化或链断了一半检查 head/tail 是否始终存在检查 _add_to_head 四步顺序get 返回已经淘汰的值链表摘除了节点但哈希表没删 key在淘汰分支补上 del self.cache[removed.key]缓存实际存储超过容量size 维护错误或淘汰判断写错位置检查 size 只在新建节点时加、淘汰时减put 已有 key 后顺序不变更新 value 后忘记 move_to_head在 if 分支里补上 _move_to_head链表死循环哨兵节点互相引用被破坏检查 _add_to_head 是否把 head.next 的 prev 改对了面试时脑子空白没有提前画图先画四个指针图再写代码5.8 写完别急着交三个自测用例我每次写完这道题无论多熟练都会跑一遍固定用例再收工。第一组是容量 1 连续 put 两个不同 key确认第一个 key 被淘汰。第二组是同一个 key 连续 put 两次不同 value确认 value 被更新且只占一个节点。第三组是 put 新 key、get 一个不存在的 key、再 put 另一个新 key确认淘汰的确实是最久没用的那一个。这三组用例覆盖了所有主要分支和边界条件跑完心里就有底了。6. 从笔试题到工程实践LRU 在真实系统里的样子6.1 Python 标准库里的现成实现很多人忘了 Python 标准库的 functools 模块里就带了一个 lru_cache 装饰器这是把 LRU 思想直接封装成工具的最好案例。from functools import lru_cache lru_cache(maxsize128) def fibonacci(n): if n 2: return n return fibonacci(n - 1) fibonacci(n - 2)加上这个装饰器之后同样的输入只需要真正计算一次后续调用直接从缓存取结果。递归算斐波那契数列在没有缓存时是指数复杂度加了 lru_cache 之后变成线性复杂度肉眼可见地变快。这个小例子值得在面试中主动聊一聊因为它证明你不是只会自己写类还知道标准库的设计思路。6.2 业务系统里的本地缓存实际业务代码里本地缓存很少只有一个 LRU 类而是 LRU 和其他策略的组合。比如缓存的数据通常还带过期时间超过 TTL 的数据即使还活着也不能返回。你可能需要维护一个基于时间优先级的过期队列再叠加 LRU 的访问优先级。又比如为了降低锁竞争可以把大缓存拆成多个分片每个分片一个 LRUkey 通过哈希分布到不同分片。分片之间相互独立并发度自然就上去了。还有一点工程上的经验是缓存不能只考虑存储结构还需要考虑数据一致性。比如某个 key 对应的数据库记录被更新了你要主动把缓存里对应的条目删掉或者写一个短过期时间来兜底。否则 LRU 算法本身再优秀上层的数据一致性出问题线上照样出事故。6.3 量化交易里为什么会用到 LRU热搜词里有“python 量化交易策略代码”这其实是 LRU 很典型的一个实际应用场景。量化回测时同一段行情数据会被多个指标重复读取同一份历史 K 线可能既被均线策略用到又被波动率策略用到。如果每次都去数据库或磁盘拉取IO 开销会拖慢整个回测速度。把这些行情数据按窗口切分用 LRU 缓存最近使用过的行情片段内存压力可控回测速度能提升一个量级。我自己接过的本地缓存需求里还有一类是把上一次的计算结果缓存起来比如某段行情的盘中指标。只要最近十几分钟的行情没变就直接复用缓存结果一旦有新的 tick 进来淘汰最旧的一段。这种需求用 LRU 实现非常自然。6.4 联想把 LRU 扩展成小型缓存框架如果你掌握了手写 LRU 的思路可以顺手扩展出一个更完整的工具类。除了 LRU再加一个定时过期机制用一个额外的优先队列按过期时间排序到点了就异步清理。再加一个可选的指标统计记录 get 次数、命中次数、淘汰次数这样你在线上就能通过监控看到缓存命中率的变化。有一个我在工程里反复踩过的坑缓存命中率不是越高越好不能只盯着命中率优化。如果命中率太高的代价是缓存大量冷数据或者为了维持命中率而把缓存容量调到内存吃紧那反而是负优化。正确做法是同时关注命中率和内存占用率两个指标找到平衡点。这些方向不一定都写在笔试题里但面试快结束时如果能聊到这里面试官基本会认定你是一个真正理解缓存系统的工程师而不是只会背答案的求职者。最后分享一点个人的习惯。面试时拿到这道题我不会急着写代码而是先把“哈希表负责 O(1) 查找、双向链表负责 O(1) 删除和移动、头部是最近使用、尾部是最久未使用”这几句话讲清楚然后画出节点图再动手写。代码写完后当场跑一组边界用例这样做比闷头写完直接提交要稳得多。手写 LRU 我已经练过无数遍现在在公司做本地缓存方案时依然会按这套思路来思考只是把双向链表换成有界队列把哈希表换成带并发控制的结构。能把一道面试题练到可以讲清楚每一个设计取舍它就不再只是一道题了。