LRU缓存淘汰算法：哈希表+双向链表实现O(1)与生产级优化

1. 从缓存淘汰说起LRU 到底解决的是什么问题聊 LRU 之前我先讲个特别接地气的场景。你家里有个鞋柜只能放十双鞋但你有一百双鞋。每次出门穿哪双脱下来就往柜子里塞。塞满了怎么办要么把最久没穿过的那双扔了要么把最近刚穿过的扔掉。正常人都会做第一个选择——把最久没碰过的清出去因为那双鞋大概率你近期也不需要了。LRU 算法Least Recently Used最近最少使用干的就是这么回事只不过它管的不是鞋是内存里的数据。在计算机系统里内存和缓存永远不够用。CPU 有寄存器、L1/L2/L3 缓存容量一级比一级小、速度一级比一级快。操作系统管理物理内存的时候不可能把所有进程的数据都同时塞进内存条。数据库查询热数据的时候也不可能把整张表都常驻内存。这就必然引出一个问题当缓存空间满了新的数据要进来得请谁出去这就是所谓的淘汰策略而 LRU 是这里面应用最广、也最经得起实战考验的一种。1.1 为什么是最近最少使用而不是别的淘汰策略其实有好几种比较常见的还有 FIFO先进先出和 LFU最不经常使用。FIFO 顾名思义谁先进来的谁先滚蛋简单粗暴但它有个致命缺陷它不考虑数据的使用频率。想象一个场景你在做一个网页服务首页的配置数据是访问最频繁的但它在系统启动时是最早加载的那批。如果按 FIFO 淘汰这个最热的配置数据反而会最先被踢出去然后下次访问又要重新加载然后又最早进来又被最早踢出去——循环往复简直灾难。LFU 是按访问次数来淘汰听起来更科学但它的问题在于历史包袱。一个数据可能曾经被访问过一万次但现在早就不用了LFU 还是会把它当宝贝供着因为它次数高。而且 LFU 需要给每个数据维护一个计数器开销也不小。LRU 的哲学就很有意思了它赌的是局部性原理。什么意思就是如果一个数据刚刚被访问过那么它在不久的将来被再次访问的概率非常高。反过来如果一个数据很久没被碰过了那它未来被访问的概率就很低。这个假设在很多真实场景下都成立——你看视频刚看过的片段可能还要回看你查数据库同一批热点商品数据会被反复查询。所以 LRU 淘汰最久没用过的实际上是在用最小代价保住最可能被用到的数据。注意LRU 的核心假设是访问的时间局部性它不保证绝对最优。如果你的访问模式是随机的、没有局部性LRU 的命中率可能还不如一些更简单的策略。所以在选型前先想清楚你的业务访问模式。1.2 LRU 在真实系统里的位置你平时可能没直接写过 LRU但你几乎每天都在用它。操作系统的页面置换Linux 内核里那一套 active/inactive 链表本质就是 LRU 的变体MySQL 的 InnoDB Buffer Pool 用的近似 LRU通过分代优化来避免全表扫描污染缓存Redis 的maxmemory-policy里就有allkeys-lru和volatile-lru两种模式各种 HTTP 客户端、CDN、浏览器缓存背后也都有 LRU 的影子。所以当面试官问你手写一个 LRU的时候他不是在考你背书他是在看你对数据结构 缓存思想的理解深度。这个题之所以经典是因为它逼着你在时间复杂度和空间复杂度之间做权衡而做权衡恰恰是工程的核心。2. 核心设计拆解为什么必须是哈希表 双向链表很多人第一次面对设计一个 O(1) 的 LRU时会懵。直觉上我需要两件事第一我要能快速找到某个 key 对应的数据在哪里查找快第二我要能快速知道谁是最久没用的并且能快速把它删掉、把新来的加进去更新快。单靠一个数组不行删除中间元素要移动后面所有元素O(n)。单靠一个单向链表也不行你找到某个节点之后想把它移到链表头但单向链表拿不到它的前驱节点还是要从头遍历O(n)。单靠一个哈希表更不行哈希表能让你 O(1) 找到数据但它没法告诉你谁最久没用。所以答案就是组合拳哈希表负责找得到双向链表负责排得序。2.1 哈希表在这里扮演什么角色哈希表在 Java 里是 HashMapPython 里是 dictC 里是 unordered_map存的是 key 到链表节点的映射。这里有个细节新手容易踩坑哈希表里存的 value 不是数据本身而是指向双向链表节点的引用指针。为什么要这么设计因为当你要访问某个 key 的时候你希望 O(1) 就能定位到它在链表里的那个节点然后直接把这个节点从当前位置摘下来移到链表头部标记为最近使用。如果你存的是数据值而不是节点引用你就得拿着 key 再去链表里遍历找节点那又退化成 O(n) 了。实操心得很多教程图省事哈希表直接存 value然后在淘汰时遍历链表找最旧的那个——这在小数据量下看着没问题一旦数据量上来性能直接崩盘。LRU 的精髓就在这个节点引用别省这一步。2.2 双向链表为什么不是单向链表双向链表在这里的职责是维护使用顺序。我们约定靠近头部的节点是最近使用的靠近尾部的节点是最久未使用的。访问一个数据把对应节点移到头部。淘汰数据把尾部节点删掉。插入新数据放到头部。这里面有个关键动作叫把任意节点移到头部。如果链表是单向的你要删除一个节点必须知道它的前驱节点而单向链表只能从头往后找这就是 O(n) 的根源。双向链表每个节点都有prev和next两个指针不管这个节点在哪个位置你都能直接拿到它的前驱和后继摘除和插入都是常数时间。为了代码写起来不恶心工业实现里通常会引入虚拟头节点dummy head和虚拟尾节点dummy tail。这两个节点不存真实数据只是哨兵。好处是你永远不用判断是不是空链表是不是在头部插入是不是在尾部删除这些边界情况所有操作都能用统一的逻辑处理代码会干净很多bug 也少很多。2.3 各操作的时间复杂度账我们把账算清楚操作做法时间复杂度查找 key哈希表定位O(1)访问数据哈希表定位 链表节点移到头部O(1)插入新数据存入哈希表 插入链表头部O(1)淘汰数据删除链表尾部节点 删哈希表项O(1)空间复杂度哈希表 O(n) 链表 O(n)O(n)这就是 LRU 的精髓所在用额外的 O(n) 空间换取所有核心操作 O(1) 的时间。在缓存这个场景里空间本来就是要用来存数据的所以这份额外开销哈希表存指针、链表节点存指针完全可以接受。2.4 为什么不用现成的有序结构有人会问Java 里不是有LinkedHashMap吗它可以设置accessOrdertrue天生就是 LRU。没错LinkedHashMap底层就是哈希表 双向链表和我们手写的结构一模一样。那手写还有什么意义第一你得理解它否则遇到需要定制版本比如加过期时间、加权重、加分段的时候你就抓瞎。第二LinkedHashMap的 LRU 是全局锁的高并发下性能很差真到生产环境你往往需要自己实现一套带分片加锁或者无锁的结构。第三面试和笔试它是刚需躲不掉。所以我一直建议先手写一遍理解原理再在合适的场景用现成实现需要性能时自己优化。3. 手写实现从零到可运行的完整代码光说不练假把式。我用 Python 写一版最清晰的再给一版 C 的最后给一版 Java 用LinkedHashMap的极简版方便不同语言的读者直接抄作业。3.1 双向链表节点的定义节点是基础。我们把它设计得简单点class Node: def __init__(self, key0, value0): self.key key # 存 key 是为了淘汰时能反查哈希表 self.value value self.prev None self.next None这里有个容易被忽略的细节节点里为什么要存 key因为淘汰尾部节点的时候我们不仅要把这个节点从链表删掉还要把哈希表里对应的映射删掉否则哈希表就会泄漏。要删哈希表你就得有 key而尾部节点只有 value 没有 key你就找不到哈希表里那项。所以节点必须存 key。这是新手最常踩的坑之一代码跑起来发现数据对不上八成就是这里出了问题。3.2 完整 LRU 实现Python 版class LRUCache: def __init__(self, capacity: int): self.capacity capacity self.cache {} # key - Node # 虚拟头尾节点简化边界处理 self.head Node() self.tail Node() self.head.next self.tail self.tail.prev self.head def _remove(self, node): 把节点从链表中摘除 node.prev.next node.next node.next.prev node.prev def _add_to_head(self, node): 把节点插入到头部最近使用的位置 node.next self.head.next node.prev self.head self.head.next.prev node self.head.next node def _move_to_head(self, node): self._remove(node) self._add_to_head(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) else: node Node(key, value) self.cache[key] node self._add_to_head(node) if len(self.cache) self.capacity: # 淘汰尾部节点最久未使用 lru self.tail.prev self._remove(lru) del self.cache[lru.key]这段代码我建议你对着敲一遍尤其是_remove和_add_to_head这两个操作里指针的顺序。指针操作是 LRU 实现里最容易出 bug 的地方顺序错了就会形成环或者断链。操作禁忌写指针操作的时候一定要遵循先接后断的原则——先把新指针接好再断开旧指针。上面_add_to_head里先设置node.next和node.prev再修改self.head.next.prev和self.head.next这个顺序不能乱否则会丢失节点引用。3.3 关键步骤的现场推演我拿一组具体数据带你把流程走一遍容量设为 2。初始状态链表空head - tail。put(1, 1)新建节点1挂到头部。链表变成head - 1 - tail哈希表{1: node1}。put(2, 2)新建节点2挂到头部。链表变成head - 2 - 1 - tail哈希表{1: node1, 2: node2}。get(1)命中把节点1移到头部。链表变成head - 1 - 2 - tail。返回 1。注意现在节点2变成了尾部也就是最旧的。put(3, 3)新建节点3此时 size 会变成 3超过容量 2。先挂节点3到头部链表变成head - 3 - 1 - 2 - tail然后淘汰尾部节点2删链表和哈希表。最终head - 3 - 1 - tail哈希表{1: node1, 3: node3}。get(2)不在哈希表里返回 -1。正确因为2已经被淘汰了。你把这几步在纸上画一画整个 LRU 的动态就活了。很多人看代码觉得懂了一画图发现理解是错的这就是为什么要动手。3.4 C 版本的核心骨架C 里用std::list和std::unordered_map组合最省事因为std::list天然支持 O(1) 的任意位置删除和转移。class LRUCache { private: int cap; std::liststd::pairint, int lst; // 头部最新尾部最旧 std::unordered_mapint, std::liststd::pairint, int::iterator mp; public: LRUCache(int capacity) : cap(capacity) {} int get(int key) { auto it mp.find(key); if (it mp.end()) return -1; // 把命中的节点 splice 到头部 lst.splice(lst.begin(), lst, it-second); return it-second-second; } void put(int key, int value) { auto it mp.find(key); if (it ! mp.end()) { it-second-second value; lst.splice(lst.begin(), lst, it-second); return; } if ((int)lst.size() cap) { int oldKey lst.back().first; lst.pop_back(); mp.erase(oldKey); } lst.emplace_front(key, value); mp[key] lst.begin(); } };这里splice是std::list的杀手锏它能把一个节点从链表的一个位置剪切到另一个位置而且不涉及内存分配和拷贝纯指针操作效率极高。很多人不知道这个函数用erase push_front虽然也对但多了一次节点构造和析构性能上有差距。实操心得C 的std::list迭代器在splice之后依然有效只要节点没被销毁所以哈希表里存的迭代器不用更新。这个特性是很多面试官想考察的点答对了加分。3.5 Java 一行搞定的方式如果你只是想快速用Java 的LinkedHashMap是标准答案重写removeEldestEntry即可class LRUCache extends LinkedHashMapInteger, Integer { private int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true); // accessOrder true 开启 LRU 排序 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.EntryInteger, Integer eldest) { return size() capacity; } }注意构造函数第三个参数accessOrder必须传true默认是false插入顺序。这一点坑过无数人跑出来的行为是 FIFO 而不是 LRU还找不到原因。4. 进阶优化真实生产环境里的 LRU 长什么样标准 LRU 在教科书里很美好但到了生产环境它有几个硬伤。这一章我讲讲怎么把它改造成能扛住真实业务的版本这些内容在普通教程里基本看不到。4.1 并发环境下的加锁问题单线程 LRU 没问题但 Redis 那种高并发场景多个线程同时读写链表不加锁必崩。最粗暴的方案是给整个 LRU 加一把大锁但这样所有读操作都串行化吞吐量上不去。工业界的做法通常是分段锁sharding把一个大的 LRU 拆成 N 个小 LRU每个小 LRU 一把锁访问时用 key 的哈希值决定去哪个分片。import threading class ShardedLRUCache: def __init__(self, capacity, shard_count16): self.shards [ (LRUCache(capacity // shard_count), threading.Lock()) for _ in range(shard_count) ] self.shard_count shard_count def get(self, key): idx hash(key) % self.shard_count cache, lock self.shards[idx] with lock: return cache.get(key) def put(self, key, value): idx hash(key) % self.shard_count cache, lock self.shards[idx] with lock: cache.put(key, value)这样做的好处是只要 key 分布均匀并发冲突概率大大降低。代价是每个分片独立淘汰整体上不是严格的 LRU但在这个量级下误差可以忽略性能收益是值得的。注意分片数不是越多越好。分片太多锁竞争是小了但内存碎片、缓存局部性、管理开销都会上升。实践中一般取 2 的幂次16 或 32 是比较稳的起点。4.2 近似 LRURedis 为什么不用严格 LRURedis 官方文档里说得很清楚它用的是近似 LRUApproximate LRU。为什么因为维护一个严格的全局 LRU 链表每次访问都要修改指针在高频读写场景下这个链表操作本身就是巨大的开销而且严重限制并发。Redis 的做法是每个对象存一个lru_clock时间戳精度是秒级或毫秒级淘汰的时候随机采样若干个 key从中挑出最久未使用的那个淘汰。这样不需要维护链表淘汰时也不影响读写主流程。采样数量默认是 5可以通过maxmemory-samples配置。采样 5 个听起来很粗糙但 Redis 官方做过压测采样 10 个的时候近似 LRU 的效果已经和严格 LRU 非常接近了。这就是工程上的经典取舍——用一点点精确性换来了巨大的性能提升和并发能力。4.3 LRU-K 与 2Q解决缓存污染标准 LRU 有个著名的问题叫缓存污染cache pollution。举个例子你做数据库缓存突然来了一次全表扫描大量数据一次性涌入瞬间把原本热点的数据全挤出去了。等全表扫描结束热点数据全没了缓存命中率断崖式下跌。解决方案之一是LRU-K。它的思路是记录每个数据最近的第 K 次访问时间只有当访问次数达到 K 次时才认为它是热数据才允许进入主缓存。这样偶尔访问一次的数据比如全表扫描的数据根本进不来污染不了。2QTwo Queues是另一个思路维护两个队列一个 FIFO 队列用于过滤冷数据和一个 LRU 队列存热数据。数据先进 FIFO被第二次访问才移到 LRU。原理和 LRU-K 类似实现更简单。算法核心思想适用场景代价标准 LRU淘汰最久未使用访问局部性强易被偶发大量访问污染LRU-K访问达 K 次才入主缓存有明显热点、抗污染需维护访问计数K 值难调2QFIFO 过滤 LRU 留存抗扫描污染结构复杂内存开销大近似 LRU采样淘汰高并发、海量 key精度略降实操心得K 值怎么选没有万能公式。太小比如 2过滤能力弱太大比如 5会导致新热点迟迟进不来。我一般从 2 开始试看命中率曲线找到拐点。这东西必须靠业务数据调别迷信理论值。4.4 给缓存加过期时间和权重真实业务里光有 LRU 不够经常还要叠加 TTL生存时间和权重。TTL 好理解每个节点加个过期时间戳get的时候先检查是否过期过期就当作未命中。但要注意TTL 的清理策略也有讲究惰性删除访问时才检查省 CPU 但浪费内存定期删除后台线程扫描占 CPU 但内存干净。Redis 用的是两者结合。权重是另一个维度。假设你的缓存里既有小对象几 KB又有大对象几 MB单纯按个数淘汰一个大对象可能占着很多空间却只算一个名额这不合理。所以有些系统会引入基于大小的淘汰GDSF 等让大对象在淘汰时权重大更容易被清出去。这些改造在校招面试里基本不会问但一旦你工作两三年负责一个真实的缓存层这些就是你必须考虑的东西。我见过太多项目一开始用最简单的 LRU跑着跑着内存爆了、命中率崩了回过头来才发现是没考虑这些。5. 常见问题排查与踩坑实录这一章是我自己这些年踩过的坑还有帮别人看代码时遇到的典型问题。LRU 本身不难但细节特别多一不留神就翻车。5.1 高频 Bug 速查表现象可能原因排查方向淘汰后数据还能查到淘汰时忘了删哈希表 / 节点没存 key检查put里的 cleanup 逻辑命中率异常低accessOrder 没开退化成 FIFO检查构造参数链表出现环死循环指针操作顺序错误检查_remove和_add顺序get之后淘汰错了对象没有把命中节点移到头部检查get是否调用_move_to_head容量为 0 时报错没处理边界情况特判 capacity 0更新已存在的 key 没生效只更新了哈希表没更新节点检查put的更新分支5.2 一个我真实踩过的坑节点没存 key刚工作那会儿我写了个 LRU 用在接口缓存上测试环境跑得好好的一上预发就出问题缓存里已经有 100 条了还在往里加看起来容量限制完全没生效。查了半天才发现我淘汰尾部节点的时候只删了链表节点没删哈希表里的映射。而判断是否超容量是看哈希表大小所以哈希表一直在涨链表缩了但计数没减两边对不上。这个坑的教训就是哈希表和链表是两份必须同步的数据结构任何一方的增删都必须同步到另一方。后来我养成一个习惯把删链表 删哈希表封装成一个原子方法永远成对调用不再分开写。这个小重构之后再没犯过类似的错。5.3 命中率上不去的排查思路如果你发现 LRU 命中率远低于预期别急着换算法先按这个顺序排查第一确认访问模式有没有局部性。如果业务本身就是随机访问海量 key那 LRU 天生就不适合换什么算法都白搭得考虑用别的方案或者加大容量。第二看有没有缓存污染。抓一段时间的访问日志看看是不是有周期性的批量扫描把热点冲掉了。如果是上 LRU-K 或 2Q。第三检查容量设置是否合理。容量太小怎么淘汰都不够用。一般有个经验值热点数据的总大小乘以 1.5 到 2 倍是比较舒服的容量。第四确认 key 的粒度。有时候一个大 key 里塞了几百个小字段访问其中一个字段也要整个换入换出命中率自然低。这时候应该考虑把 key 拆细。5.4 面试答题的加分点如果你是在准备面试除了能写出 O(1) 的代码我建议你主动聊这几点面试官会觉得你真的理解而不是背题主动说明为什么要用双向链表而不是单向链表点出前驱指针的必要性。提一句虚拟头尾节点简化边界处理。说出 LRU 基于时间局部性原理并说明它的局限。如果能顺带提到 Redis 用近似 LRU、MySQL 用分代 LRU那就是明显加分。被问如果并发怎么办答分段锁并说明取舍。这些点我在面试别人的时候特别看重能把标准答案背出来的人很多能讲清楚为什么这么设计什么场景不适用的人很少。最后再分享一个我自己调 LRU 的小技巧加个命中率监控埋点定期打日志。很多问题不是代码错了是业务访问模式变了而你还不知道。有了命中率曲线你就能第一时间发现异常早发现早处理比事后救火强太多。