准备过后端或客户端面试的人对 LRU 和 LFU 这两个缩写应该不会陌生。它俩都属于缓存算法核心要回答的是同一个问题缓存空间满了之后下一个被淘汰的数据该是谁如果你去面试后端岗位大概率会被要求现场手写一个 LRU稍微进阶一点会手撕 LFU。很多人以为这是死记硬背的八股文其实不是考察的是你对数据结构组合、访问特征和工程权衡的理解。这篇文章我把 LRU 和 LFU 从原理、实现、场景到面试追问一次讲透争取你看完能直接上战场。1. 先搞明白 LRU/LFU 到底在解决什么1.1 缓存最绕不开的问题容量满了怎么办缓存的基本假设很简单把数据放在更快的存储介质里下次访问就不用再穿透到慢速存储。访问一次内存可能只要几十纳秒访问一次磁盘可能是几毫秒而访问一次数据库还要算上网络开销和查询成本差距是数量级的。所以几乎所有系统都会在 CPU、操作系统、数据库、Redis、服务端业务层做缓存。但缓存有个天然约束容量不可能无限大。你不可能把数据库几十亿条记录全部塞进内存也不可能让一个 Map 无限增长。当缓存满的时候新数据要进来就必须有一个老数据要出去这个“把谁踢出去”的规则就是缓存淘汰策略也叫驱逐策略。听起来很简单对吧关键在于不同的淘汰策略会直接影响缓存命中率。如果你把一个未来马上要用到的数据淘汰了那下一次访问只能回到慢速存储缓存的价值就打了折扣。LRULeast Recently Used最近最少使用和 LFULeast Frequently Used最不经常使用就是两类最经典的决策规则。面试官问 LRU/LFU本质上就是想看你有没有能力回答“当资源受限时如何用有限的资源追求最大效益”这类问题。1.2 为什么面试官一定追着 LRU/LFU 问我面试过不少候选人LRU 这题几乎可以说是后端岗的“送分题”但能拿满分的人真的不多。大部分人能背出“双向链表 哈希表”但你要是接着问一句“为什么一定是双向链表换成数组行不行”一下就卡壳了。这题之所以高频是因为它能把几个关键知识点串起来哈希表解决 O(1) 查找双向链表解决 O(1) 插入删除两者组合起来才是一个真正 O(1) 的淘汰结构。而且它还牵扯到缓存命中、时间局部性、甚至并发场景下的线程安全这些都是实际业务里天天要面对的问题。所以面试官不是闲得无聊才问你这道题。他想看到的是你的分析路径而不是你默写代码的熟练度。你如果能先说清楚“我要维护什么”“为什么用这个结构”“最坏情况发生在哪里”其实已经比只会闷头写答案的人高一个档次。接下来我们就从 LRU 开始拆。2. LRU最近最少使用不只是“背双向链表哈希表”2.1 LRU 依赖的直觉时间局部性LRU 的淘汰依据很简单如果一个数据最近被访问过那么将来它被再次访问的概率也比较高如果一个数据很长时间都没被访问它大概率已经没人关心了。所以 LRU 要保证的是最近访问过的数据留在缓存里最久没有被访问的数据先被请出去。你可以想一下手机通话记录最近联系的人通常就是你马上还要联系的人最早那几条记录你基本不会再点开。这个假设在绝大多数业务场景下都成立这也是 LRU 被称为“最实用淘汰算法”的原因。这里要重点理解“时间局部性”这个概念。程序在运行时的访问模式往往表现出一段时间内集中访问某些数据比如你刷短视频连续几分钟都在看同一个类型的推荐列表这种访问就不是均匀的而是有时间窗口的。LRU 正好捕捉了这个特征它把所有数据按访问时间排成一条“新鲜度”序列越靠前说明刚才还在用越靠后说明很久没人碰了。容量满时把最后一个淘汰掉就行了。2.2 为什么标准实现默认是“双向链表哈希表”LRU 要求支持 get 和 put 两个操作复杂度都要做到 O(1)。如果只用数组即使你在数组里记录了访问顺序一旦某个中间数据被命中你需要把它移到最前面后面的数据全都要往前挪这是 O(n) 的开销数据量大时直接崩。如果只用普通的单链表删除一个节点必须找到它的前驱找到前驱又得从头遍历又是 O(n)。所以单链表和数组都扛不住高频访问。双向链表 哈希表是教科书级的答案。哈希表负责保存 key 到链表节点的映射这样 get 的时候能直接定位到节点双向链表负责维护访问顺序并且能在 O(1) 时间内完成删除和插入。为什么删除节点能 O(1)因为双向链表里每个节点都存着前驱和后继的指针你可以直接让前驱的 next 指向后继让后继的 prev 指向前驱不需要遍历去找前驱。这正是面试官想听的“为什么”。在实际手写的时候我强烈建议你使用哨兵节点dummy head 和 dummy tail而不是把 head 和 tail 当作 null 去判断。哨兵节点最大的好处是让链表永远不是“空的”插入和删除操作不需要对头尾做大量 if 判断代码更少边界情况也更好处理。很多人第一次写 LRU 时老在空链表、只有一个节点、删除尾节点这几个地方翻车用哨兵节点基本能规避大半问题。2.3 关键操作拆解get 和 put 各做了什么我们先确定数据结构一个 HashMap 用来存 key 到节点的映射一个双向链表用来维护访问顺序。我约定头节点代表最近访问尾节点代表最久未访问。get 操作如果 key 不在 map 里直接返回 -1如果在先把对应节点从当前位置摘下来再用头插法把它放到最前面然后返回节点的值。这一步就是在更新访问时间让它变成“最新鲜”的数据。put 操作要分情况。如果 key 已经存在那说明这是更新操作直接把节点的 value 改掉同时也要把这个节点移到链表头部。如果 key 不存在就新建一个节点放到头部并写入 map。这时候如果缓存容量超了就把链表尾部节点删掉同时从 map 里删掉对应的 key。值得注意的坑是很多人只顾着删链表节点忘了删除 map 里的 key结果内存泄漏或者数据错乱还有人更新已存在 key 以后忘了移动节点导致访问顺序没有更新后面淘汰就会出错。这些细节在面试跑用例时都会暴露。2.4 实际手撕时最容易犯的三个错第一个错是移动节点的顺序。摘除节点时必须先让前驱的 next 指向后继再让后继的 prev 指向前驱顺序反了可能导致原节点和前后都断开了。第二个错是更新存在节点时忘了处理“如果 capacity 为 0”。有的面试题会给 capacity 0这时候任何 put 都不应该继续执行否则链表和 map 里还是会塞进数据。第三个错是删除尾部节点时直接 tail.prev 写成 head如果链表里只有一个真实节点这一步就会直接把哨兵头给删了。只要你老老实实用哨兵节点并且多测几个边界用例这些问题都能提前发现。3. LFU最不经常使用关键在“频率桶”怎么组织3.1 为什么要换“频率”这个维度LRU 看的是“多长时间没访问”LFU 看的是“访问得少不多”。LFU 全称 Least Frequently Used核心思想是在缓存容量有限的情况下访问频率最低的数据最应该被淘汰。举个例子有一个 key 曾经常年保持极高的访问量只是过去十分钟没被访问另一个 key 刚刚被访问了一次但它可能只是一次性请求。这时候 LRU 可能会保留那个一次性的 key把老热点给淘汰掉。如果用 LFU那个高频老 key 不会被轻易淘汰因为它积累了大量访问次数。LFU 背后的业务直觉也很常见。比如某个商品详情页的“爆款”接口一天被用户点了几万次这种数据应该长期留在缓存里而一个普通请求可能只是偶然路过用完这一次后续再也不来了。此时把机会留给访问频率更高的数据往往比“最近用过”更符合实际需求。不过 LFU 也有自己的毛病我们放到后面讲场景时再展开。3.2 LFU 标准的实现结构主哈希表 频率映射表LFU 比 LRU 多了一个维度频率。所以不能只用一个双向链表了事。常用结构是两层第一层仍然是 HashMapkey 映射到节点信息节点里保存 value、freq、以及它在频率链表里的位置第二层是频率映射表把每个频率值对应到一批节点比如 freq 1 的 key 有一个集合freq 2 的 key 有另一个集合。当某个 key 被访问时它的 freq 加 1然后要从旧频率集合里摘除放进新频率集合的最前面。这个“每个频率一个集合”的结构有点像在 HashMap 外面再包一层 HashMap。为了让同一个频率下也能做到公平淘汰这个集合通常还需要维护一个“最近使用”的顺序。最经典的做法是给每个 freq 配一个双向链表链表头部代表该频率下最近访问的 key尾部代表最久没被访问的 key。这样一来LFU 实际上就是在 LRU 的基础上把“一个全局顺序链表”换成了“多个按频率划分的局部顺序链表”。3.3 minFreq 的更新是 LFU 的灵魂LFU 里有一个非常关键的变量minFreq即当前缓存中所有 key 的最小访问频率。淘汰的时候我们只需要到 minFreq 对应的那个频率集合里把最久没被访问的 key 踢出去即可不需要遍历全表。所以 minFreq 的维护决定了整个算法的正确性。访问已存在的 key 时如果它的旧频率正好等于 minFreq而且旧频率对应的集合里已经没有其他 key 了那 minFreq 就要加 1因为当前缓存里已经没有这个频率的 key 了。插入一个全新 key 时它的频率是 1如果缓存满了淘汰发生在 minFreq 所在的集合里然后新 key 插到 freq 1所以 minFreq 直接变成 1。这里的细节很容易踩坑。很多人会忘记“旧频率集合为空时再更新 minFreq”结果淘汰的时候去一个空集合里找 key 或者根本找不到最小频率程序直接报错。还有人在 put 已存在的 key 时只更新 value忘记把节点转移到新频率集合这会导致频率统计失真和 LRU 里“更新后忘记移动节点”是同一个根因。面试官特别喜欢在这些小地方做文章因为测试用例会精确命中最短或最边界的状态。3.4 同频率淘汰时用什么顺序LFU 还有一个隐性问题如果多个 key 的频率完全相同该淘汰谁这不能靠随机必须有第二个规则。最常见的做法是“同频内按最近未使用顺序淘汰”同一个 freq 集合内部用双向链表维护顺序淘汰时从链表末尾选也就是所有同频 key 里最久没被访问的那个。这个策略本质上是在 LFU 里嵌套了一个小 LRU兼顾频率和实时性。如果只按插入时间顺序那么一些历史遗留的低频 key 可能会长期霸占坑位新热点很难替换上来缓存会变得很迟钝。另外有些面试题会要求 LFU 的淘汰规则是“访问次数相同时淘汰访问时间最早的”。它刚好能对应到双向链表尾部。你可以在面试时主动说出这个 tie-breaking 思路会显得你不是在背代码而是真的理解算法设计里的取舍。4. 场景选择LRU 和 LFU 各有硬伤4.1 LRU 的扫描污染 vs LFU 的缓存惯性LRU 最出名的问题是“扫描污染”。想象一个批处理任务一次性从头到尾扫描了大量数据这些数据每一份都只读一次以后再也不需要了。但因为它们刚被访问过LRU 会把它们都放到链表最前面结果把真正的热数据全部挤出缓存。这个场景在数据库、文件系统、大数据扫描任务里非常常见。MySQL 的 InnoDB Buffer Pool 之所以要改成带分区的 LRU目的就是解决这种扫描导致的缓存污染。LFU 的问题则完全是另一副面孔它很难适应频率变化。一个 key 曾经火过积累了超高的访问次数现在虽然没人访问了但在 LFU 看来它依然是最有资格留在缓存里的数据另一个 key 刚变成热点访问次数还很低它反而会成为被淘汰的对象。这就像老员工靠资历占着关键岗位新人才怎么都挤不上来术语叫“缓存惯性”。所以 LFU 对突然爆发的热点反应特别慢对周期性和长期稳定的热点却非常友好。4.2 命中率、内存和实现成本对比我把关键差异整理成一个表方便你对比。拿真实系统选型时这张表也能派上用场。对比维度LRULFU决策依据最近访问时间访问频率同频时再叠加最近访问核心结构双向链表 哈希表主哈希表 多个频率链表/集合get 复杂度O(1)O(1)put 复杂度O(1)O(1)额外内存每个 key 一个链表节点每个 key 一个节点还要维护频率索引对突发流量反应快但容易被扫描污染反应慢容易保留旧热点对固定热点够用但需要反复保持热度更稳频率不容易被清掉工程实现难度较低较高只看复杂度两者都是 O(1)这其实会给人“实现差不多”的错觉。LFU 的 O(1) 是建立在维护多个频率桶的前提下的而且每个 key 每访问一次就要经历一次“脱离旧集合、加入新集合”的操作代码里有大量指针维护和边界判断。如果直接在 Java 里用 PriorityQueue 按 freq 排序更新频率时堆的调整是 O(log n)并不能真正常数级。所以你在面试里听到大厂手写 LFU几乎都是要求你用频率链表或者 LinkedHashSet 来做。4.3 真实世界的缓存算法几乎都不是“纯 LRU/LFU”工程上直接原封不动使用教科版 LRU/LFU 的产品其实很少大厂都会在细节上做改造。Redis 使用的是“近似 LRU”它并不维护全量的访问顺序而是每次随机采样若干 key淘汰其中空闲时间最长的。这样能大幅减少内存开销同时效果上接近 LRU。Redis 也支持 LFU 淘汰策略但当 key 的访问频率非常高时计数器增长会采用对数算法并且有衰减机制避免“老数据霸榜”。再看 MySQL 的 InnoDB Buffer Pool用的是一种改进 LRU把链表分成 young 区和 old 区新读入的数据先放在 old 区只有再次被访问才会升级到 young 区。这样一次大扫描的数据就算很多也只能污染 old 区很难把真正热的数据顶掉。Caffeine 缓存组件则使用了 W-TinyLFU它是一种结合频率和近因的近似 LFU用 Count-Min Sketch 这种概率数据结构做频次统计用很少的内存解决“LFU 不适合新热点”的问题。这些改进并不是为了炫技而是 LRU 和 LFU 的原始版本在真实负载下太容易暴露缺陷。5. 面试实战手撕、追问与常见翻车点5.1 动笔前先把设计方案讲给面试官听我见过太多候选人拿到题目以后一句话不说就开始疯狂打字。其实面试官更希望你先给出完整设计哪怕只花一分钟。你可以开口说我会用一个 HashMap 保存 key 到节点的映射再用双向链表维护访问顺序保证 get 和 put 都是 O(1)最近访问的节点放头部最久未访问的节点放尾部淘汰时删除尾节点。这句话本身就已经把 LRU 的框架讲清楚了说明你知道自己在写什么而不是在默写答案。尤其是 LFU 题目设计方案更重要。你可以说我会用两个 HashMap第一个存 key 到 node第二个存 frequency 到该频率的 key 集合再维护一个 minFreq 变量淘汰时从 minFreq 对应集合的最久未访问处删。这个表达比直接扔代码舒服得多。面试官如果认同了你的设计后面代码写歪时他也会知道你只是某一步写错了而不是整个思路不行。5.2 一个可以直接复制的 Python 版 LRU 实现下面是一个标准实现哨兵节点都包含在内。代码不长但它把所有关键操作都体现出来了查、改、增、删全部 O(1)。你可以照着这个写也可以参考它的命名思路。class DLinkedNode: 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 DLinkedNode() self.tail DLinkedNode() 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.prev self.head node.next self.head.next self.head.next.prev node self.head.next node def _move_to_head(self, node): self._remove_node(node) self._add_to_head(node) def _remove_tail(self): tail_node self.tail.prev self._remove_node(tail_node) return tail_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 self.capacity 0: return node DLinkedNode(key, value) self.cache[key] node self._add_to_head(node) if len(self.cache) self.capacity: tail_node self._remove_tail() del self.cache[tail_node.key]这个版本去掉了“如果 key 不存在且容量为 0 时抛异常”之类的处理因为不同面试题有不同的边界要求你在面试时先问清楚容量为 0 该怎么表现也是一种好习惯。我建议你把_remove_node、_add_to_head、_move_to_head单独抽出来写因为它们之间逻辑独立后面调试也方便。5.3 LFU 的核心代码片段两层映射怎么维护LFU 完整代码比较长我给出最关键的核心片段。主映射仍然负责 O(1) 定位频率映射负责维护“哪个 key 在哪个频率”minFreq 负责指导淘汰方向。from collections import defaultdict, OrderedDict class LFUCache: def __init__(self, capacity: int): self.capacity capacity self.min_freq 0 self.key_to_node {} self.freq_to_keys defaultdict(OrderedDict) def get(self, key: int): if key not in self.key_to_node: return -1 node self.key_to_node[key] self._increase_freq(node) return node.value def _increase_freq(self, node): old_freq node.freq self.freq_to_keys[old_freq].pop(node.key) if old_freq self.min_freq and not self.freq_to_keys[old_freq]: self.min_freq 1 node.freq 1 self.freq_to_keys[node.freq][node.key] None def put(self, key: int, value: int): if self.capacity 0: return if key in self.key_to_node: node self.key_to_node[key] node.value value self._increase_freq(node) return if len(self.key_to_node) self.capacity: victim_key, _ self.freq_to_keys[self.min_freq].popitem(lastFalse) del self.key_to_node[victim_key] node Node(key, value, 1) self.key_to_node[key] node self.freq_to_keys[1][key] None self.min_freq 1这里用了OrderedDict来保证同频内部还维护一个先进先出的顺序popitem(lastFalse)弹的是最旧的一个恰好就是在同频率下“最久没被访问”的 key。如果你用纯双向链表道理也是一样的每个频率桶是一个内部有顺序的链表。面试时即使不允许你用标准库把这个思路讲出来也算合格。5.4 面试追问从 LRU 升级到 LFU成本到底高在哪里不少面试官会顺着 LRU 问一句如果我希望记录访问次数淘汰访问次数少的 key结构要怎么改这是一个典型的从 LRU 到 LFU 的过渡问题。你得能说清楚LRU 只有一个全局顺序你把节点移到头部就够了LFU 必须根据频率把节点分到不同的桶里每次访问都要跨桶搬移。跨桶搬移意味着哈希表多了一层索引同时也多了一个“旧频率集合是否为空”的判断否则 minFreq 会过期。更深入一点你还可以提到频率计数器的存储和老化。LFU 在真实系统中不会用 64 位整数存无限制的次数因为高频 key 的计数值可能无限增长既浪费内存又让“低频新数据”永无出头之日。所以很多实现会使用对数增长访问次数越少计数器增加幅度越大访问次数大了之后增加速度明显变慢还会定期对所有计数器做衰减让历史热度逐渐下降。Redis 的 LFU 实现正是结合了计数器饱和和衰减的机制。面试中能讲出这些说明你已经从“算法题”跳到“工程实践”层面了这是很大的加分项。5.5 面试现场最容易被测试用例抓到的五个翻车点删除节点后忘记从 map 删 key。链表删干净了map 里还残留引用后续 get 还能拿到旧节点数据直接错乱。更新已存在 key 时只改 value 没把节点移到头部或新的频率桶。访问顺序或频率统计失真淘汰时就会误杀。处理“容量为 0”时没有返回。capacity 为 0 时任何 put 都不应该产生缓存节点否则 len(map) 会大于 0后面全是问题。LFU 中更新 minFreq 的条件写错。必须同时满足“旧频率等于 minFreq”和“旧频率集合为空”才增加 minFreq少一个条件都不行。同频集合内淘汰顺序不明确。有些冲突你会想当然用哈希表随机顺序在面试中最好明确说同频按最久未使用淘汰并和你的数据结构保持一致。这些坑我几乎都在真实面试代码里见过不是我在纸上谈兵。练习的时候大家可以刻意用几个用例自测容量 1 的反复 putget 不存在的 key容量满以后连续 put同一个 key 反复 get 后再插入新 keyLFU 里把所有同频 key 同时访问一遍再淘汰。把这些用例跑熟了面试基本不会栽在隐藏用例上。5.6 面试结束前我一定会讲的一句话我自己的体会是LRU/LFU 这题最后一步往往不是“代码写完了”而是“把复杂度讲给面试官听”。写完代码以后我会主动说一句get 和 put 的最坏时间复杂度都是 O(1)空间复杂度是 O(n)如果要支持并发还需要加锁或者像 Redis 一样用近似算法避免全局锁竞争。这句话虽然简单但能让面试官确认你脑子里有完整的性能画像而不是只盯着链表的指针转来转去。很多人把 LRU/LFU 当成死记硬背的模板题但你会发现真正能拉开差距的永远是你对“为什么”的回答。为什么双向链表而不是数组为什么 LFU 要维护多个频率桶为什么真实系统要改造成近似策略。把这些原因讲透了这道面试题就从“背题”变成了“展示设计能力”的加分项。下次再被问到缓存算法不用慌先把容量、访问顺序、频率这三个关键词抓在手里你的思路就不会乱。