一文讲透LRU与LFU缓存淘汰算法：原理、实现与面试考点

准备过后端或客户端面试的人，对 LRU 和 LFU 这两个缩写应该不会陌生。它俩都属于缓存算法，核心要回答的是同一个问题：缓存空间满了之后，下一个被淘汰的数据该是谁？如果你去面试后端岗位，大概率会被要求现场手写一个 LRU，稍微进阶一点会手撕 LFU。很多人以为这是死记硬背的八股文，其实不是，考察的是你对数据结构组合、访问特征和工程权衡的理解。这篇文章我把 LRU 和 LFU 从原理、实现、场景到面试追问一次讲透，争取你看完能直接上战场。

1. 先搞明白 LRU/LFU 到底在解决什么

1.1 缓存最绕不开的问题：容量满了怎么办

缓存的基本假设很简单：把数据放在更快的存储介质里，下次访问就不用再穿透到慢速存储。访问一次内存可能只要几十纳秒，访问一次磁盘可能是几毫秒，而访问一次数据库还要算上网络开销和查询成本，差距是数量级的。所以几乎所有系统都会在 CPU、操作系统、数据库、Redis、服务端业务层做缓存。但缓存有个天然约束：容量不可能无限大。你不可能把数据库几十亿条记录全部塞进内存，也不可能让一个 Map 无限增长。当缓存满的时候，新数据要进来，就必须有一个老数据要出去，这个“把谁踢出去”的规则就是缓存淘汰策略，也叫驱逐策略。

听起来很简单对吧？关键在于，不同的淘汰策略会直接影响缓存命中率。如果你把一个未来马上要用到的数据淘汰了，那下一次访问只能回到慢速存储，缓存的价值就打了折扣。LRU（Least Recently Used，最近最少使用）和 LFU（Least 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 多了一个维度：频率。所以不能只用一个双向链表了事。常用结构是两层：第一层仍然是 HashMap，key 映射到节点信息，节点里保存 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 命中率、内存和实现成本对比

我把关键差异整理成一个表，方便你对比。拿真实系统选型时，这张表也能派上用场。

只看复杂度，两者都是 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, key=0, value=0): 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(last=False) 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(last=False)弹的是最旧的一个，恰好就是在同频率下“最久没被访问”的 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 的反复 put；get 不存在的 key；容量满以后连续 put；同一个 key 反复 get 后再插入新 key；LFU 里把所有同频 key 同时访问一遍再淘汰。把这些用例跑熟了，面试基本不会栽在隐藏用例上。

5.6 面试结束前我一定会讲的一句话

我自己的体会是，LRU/LFU 这题，最后一步往往不是“代码写完了”，而是“把复杂度讲给面试官听”。写完代码以后，我会主动说一句：get 和 put 的最坏时间复杂度都是 O(1)，空间复杂度是 O(n)；如果要支持并发，还需要加锁，或者像 Redis 一样用近似算法避免全局锁竞争。这句话虽然简单，但能让面试官确认你脑子里有完整的性能画像，而不是只盯着链表的指针转来转去。

很多人把 LRU/LFU 当成死记硬背的模板题，但你会发现，真正能拉开差距的永远是你对“为什么”的回答。为什么双向链表而不是数组；为什么 LFU 要维护多个频率桶；为什么真实系统要改造成近似策略。把这些原因讲透了，这道面试题就从“背题”变成了“展示设计能力”的加分项。下次再被问到缓存算法，不用慌，先把容量、访问顺序、频率这三个关键词抓在手里，你的思路就不会乱。