手撕过LRU的人很多真正把它吃透的人不多。缓存淘汰是计算机系统里绕不开的问题而LRULeast Recently Used最近最少使用正是其中最经典的答案。不管你是准备面试还是在设计本地缓存、接入Redis内存淘汰总会撞上这个老朋友。这篇博客从原理讲起拆解三种实现思路逐行分析哈希表双向链表的标准解法再聊聊生产环境里那些面试题外的LRU变种希望能帮你把这块彻底搞清楚。1. LRU究竟在解决什么问题1.1 缓存淘汰的根源是空间有限计算机世界里缓存无处不在CPU的L1/L2 Cache、操作系统物理内存里的页面、运行时的本地缓存、分布式系统的热点数据本质上都在解决同一个矛盾——数据访问速度要和存储容量做交换。拿你手机里的App举例。列表页加载完的数据下次滑回来如果还要重新请求体验会非常糟糕。于是你引入了一个内存缓存把最近看过的内容存一份下次直接读缓存。但内存不是无限的假设你只能缓存100条记录用户不断浏览新内容旧内容终归要腾地方。问题是腾谁的地方官方一点的说法叫“淘汰策略”大白话就是——缓存满了谁先滚蛋。最理想的情况是淘汰“未来最长时间内不会再被访问”的数据。但未来不可预测我们只能通过历史行为去近似。于是业界总结出几种经典的近似方案FIFO先进先出谁先来谁先走。实现最简单但完全不考虑访问频率和时间一个被高频访问的老数据也可能被无情清掉效果较差。LFU最不经常使用谁用得少谁先走。问题在于“历史包袱”——一个早期高频访问、后来再没碰过的数据计数仍然很高一直赖着不走导致冷数据滞留。LRU最近最少使用谁最久没被访问谁先走。它只关注“距离上一次访问的时间间隔”既保留了热度语义又不会让冷数据长期占坑是实践中最常用的折中方案。LRU为什么这么流行因为它用“最近是否被访问”来近似“未来是否会被访问”这个假设在绝大多数业务场景下都成立你今天看过的新闻明天很可能还会看三年前的冷饭没人会主动回想。1.2 LRU的核心判定逻辑LRU的核心规则就两句话每次访问不管是读还是写都把这条数据标记为“最新鲜”。缓存容量满时把“最久没被访问”的数据淘汰掉。这里要特别注意一个误区LRU不是看“被访问了多少次”而是看“距离上次访问过了多久”。一个数据哪怕只被访问过一次只要它是最近一次访问它就能留在缓存里另一个数据就算被访问了一万次如果最后一次访问发生在很久以前它照样是淘汰候选。理解了这个逻辑就理解了为什么每次get操作也必须更新数据的“新鲜度”。很多初学者写缓存时只更新写入的数据读操作不更新顺序结果整个LRU规则从第一步就错了。《微信读书》上的翻页、电商App里的商品详情每打开一次都应该重新计为“刚刚用过”。所以手撕LRU时get操作除了返回值还隐含一个动作把对应节点挪到“最近使用”的位置。这是面试考察的核心细节也是很多人容易漏掉的地方。2. 三种手撕LRU的实现思路2.1 基于数组的实现直观但代价太大第一反应往往是数组。维护一个数组按访问时间从新到旧存放key每次访问某个key就把这个key移到数组头部淘汰时直接丢数组尾部的元素。听上去能工作但仔细一想全是问题。数组移动元素的平均复杂度是O(n)当缓存容量达到几十万、上百万时每次访问都要触发大量元素搬移系统根本扛不住。更麻烦的是为了O(1)地判断一个key在不在缓存里你还得额外配一个哈希表来记录位置。即便如此哈希表里的位置信息在每次移动后也需要同步更新复杂度并没有降下来。数组实现几乎只出现在讲解“什么是顺序结构”的入门场景中作为手撕算法答案它是不及格的。实现方式定位key复杂度更新顺序复杂度淘汰复杂度综合评定数组 哈希表O(1)O(n)O(1)更新代价太高单向链表 哈希表O(1)O(1)O(n)找前驱删除时卡脖子双向链表 哈希表O(1)O(1)O(1)标准答案双向链表无哈希表O(n)O(1)O(1)定位太慢2.2 基于链表的实现淘汰容易但查找拉胯既然数组移动元素代价高自然会想到链表。链表天然适合表达“顺序关系”每次访问某节点把它摘下来挂到头部容量满时把链表尾部的节点摘掉。插入和删除都是O(1)时间复杂度问题解决了。但新的问题出现了链表定位节点需要遍历。缓存里一个key对应的节点可能在链表中间如果不知道它在哪就得从头到尾找一遍又是一个O(n)。所以纯链表实现也不可行。有人可能会说“那我在链表节点里存key访问时先遍历找到key再操作不就行了”可以但这就回到了O(n)定位的困境。缓存系统的核心诉求就是高并发下的低延迟任何O(n)操作在大流量下都是定时炸弹。2.3 哈希表双向链表教科书级的组合拳真正工业级的解法是哈希表加双向链表打通。哈希表负责O(1)定位双向链表负责O(1)插入删除。这个组合几乎成了LRU的代名词面试官看到你写出这个结构基本就放心了。这里有两个关键设计点值得展开。为什么必须是双向链表我们删除一个链表节点时需要让“前一个节点的next”指向“后一个节点”那就必须找到前驱节点。如果是单向链表只能从头遍历找前驱摊下来还是O(n)。双向链表每个节点都持有prev指针摘除节点时直接通过prev定位前驱删除操作变成纯O(1)。打个比方单向链表就像排队买奶茶时只知道后面是谁前面是谁得挨个问双向链表则是前后都清楚有人插队时直接拽住他前后两个人就能把他请出去。为什么带头尾两个虚拟节点很多初学者手写链表时最怕头节点和尾节点的空指针问题删除的是头节点怎么办插入时链表为空怎么办解决办法是引入两个不存数据的虚拟节点head和tail让head.next指向第一个真实节点tail.prev指向最后一个真实节点。链表永远不为“空”所有操作都变成“在head和真实节点之间插”、“在tail和真实节点之间删”边界条件被统一消灭了。用虚拟节点后还有一个好处淘汰时直接找tail.prev就是最久未使用的节点不需要额外判断tail.prev是否为空代码写起来非常顺手。3. 手撕核心代码的完整过程3.1 从类结构开始成员变量与节点定义这部分以Java为例。先定义一个双向链表节点包含key、value、prev、next四个字段。key必须存下来因为淘汰节点时要靠它去哈希表里删除对应条目。class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() {} public DLinkedNode(int key, int value) { this.key key; this.value value; } }主类里维护四个东西一个哈希表cache、一个int类型size记录当前数量、capacity记录容量上限、和两个虚拟节点head与tail。public class LRUCache { private MapInteger, DLinkedNode cache new HashMap(); private int size; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity) { this.size 0; this.capacity capacity; head new DLinkedNode(); tail new DLinkedNode(); head.next tail; tail.prev head; } }初始化时让head.next指向tailtail.prev指向head链表结构就已经是自洽的了。capacity为0的场景也要考虑后面put操作里会体现。提示size是真实节点数不是链表长度。head和tail是虚拟节点不参与计数。这个细节直接关系到后续的淘汰判断别搞混。3.2 get操作定位、提升、返回get的逻辑分三步先在哈希表里找key找不到返回-1找到了就把对应节点移动到链表头部然后返回节点的value。public int get(int key) { DLinkedNode node cache.get(key); if (node null) { return -1; } moveToHead(node); return node.value; }为什么找不到时不用动缓存因为get不存在的key本来就不在缓存里不影响任何数据的“新鲜度”直接返回-1即可。有些初学同学会在这时候遍历一遍链表纯属多余还可能引入了竞态条件。moveToHead是两个基础操作“移除节点”和“插入到头部”的组合下面会统一说明。3.3 put操作新增与更新两条路径put要考虑的情况比较多我习惯把它分成两大分支。情况一key不存在。创建一个新节点放进哈希表挂到双向链表头部size加1。加完如果发现size大于capacity说明超容量了需要把链表尾部的节点摘掉然后从哈希表里删除对应条目size减1。情况二key已存在。更新节点里的value把节点移动到头部。size不需要变化哈希表也不需要重新put因为key对应的对象引用没变。public void put(int key, int value) { DLinkedNode node cache.get(key); if (node null) { DLinkedNode newNode new DLinkedNode(key, value); cache.put(key, newNode); addToHead(newNode); size; if (size capacity) { DLinkedNode tailNode removeTail(); cache.remove(tailNode.key); size--; } } else { node.value value; moveToHead(node); } }你可能注意到新增时先addToHead再removeTail而不是先淘汰再插入。这个顺序是我故意定的。如果先removeTail再addToHead当容量为0时就会出现“淘汰了节点但插不进去”的尴尬先插入再淘汰则天然兼容capacity0新节点会被自己立刻淘汰掉逻辑上自洽。3.4 四个辅助操作链表的灵魂addToHead、removeNode、moveToHead、removeTail这四兄弟是手撕LRU最容易翻车的地方尤其是前两个指针连接顺序写错一步就是断链或死循环。private void addToHead(DLinkedNode node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } private void removeNode(DLinkedNode node) { node.prev.next node.next; node.next.prev node.prev; } private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } private DLinkedNode removeTail() { DLinkedNode res tail.prev; removeNode(res); return res; }addToHead的顺序是先设置node自己的prev和next指针再修改head.next的人的前驱最后修改head的next。很多人会先把head.next node写在前面导致node.next拿到的还是旧的头节点链表直接断掉。removeNode则必须同时维护前驱的next和后继的prev只写一个指针等于没删。moveToHead就是先摘下来再插上去幂等且安全。removeTail直接摘掉tail.prev之所以能这么放心就是因为虚拟tail保证了tail.prev在链表不为“空”时一定指向真实节点。3.5 完整可运行的参考代码把上面的片段拼起来就是一份可以直接跑起来的LRU实现。import java.util.HashMap; import java.util.Map; public class LRUCache { class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() {} public DLinkedNode(int key, int value) { this.key key; this.value value; } } private MapInteger, DLinkedNode cache new HashMap(); private int size; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity) { this.size 0; this.capacity capacity; head new DLinkedNode(); tail new DLinkedNode(); head.next tail; tail.prev head; } public int get(int key) { DLinkedNode node cache.get(key); if (node null) { return -1; } moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node cache.get(key); if (node null) { DLinkedNode newNode new DLinkedNode(key, value); cache.put(key, newNode); addToHead(newNode); size; if (size capacity) { DLinkedNode removed removeTail(); cache.remove(removed.key); size--; } } else { node.value value; moveToHead(node); } } private void addToHead(DLinkedNode node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } private void removeNode(DLinkedNode node) { node.prev.next node.next; node.next.prev node.prev; } private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } private DLinkedNode removeTail() { DLinkedNode res tail.prev; removeNode(res); return res; } }如果面试时间紧还有一种基于JDK自带LinkedHashMap的偷懒写法class LRUCache extends LinkedHashMapInteger, Integer { private int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true); this.capacity capacity; } Override protected boolean removeEldestEntry(Map.EntryInteger, Integer eldest) { return size() capacity; } }构造函数里第三个参数accessOrder传true表示按照访问顺序排序removeEldestEntry方法在插入后判断当前容量是否超限超限就自动把头节点移除。这套写法适合快速验证逻辑但面试时建议还是手写双向链表更能体现功底。3.6 边界条件的测试用例设计写完代码一定要自己跑测试。我平时习惯先跑这几种用例capacity为1连续put两个不同key第一个应该被淘汰。capacity为0随时putget永远返回-1不抛异常。重复keyput同一个key两次容量不增加value更新。get不到key返回-1不触发淘汰。put满后get老数据get会把老数据重新变成“最新”此时如果再put新key淘汰的是次老的而不是刚get过的。一个经典的验证序列长这样容量2put(1,1)、put(2,2)、get(1)、put(3,3)此时缓存里应该是1和32被淘汰。如果代码打印出2还在说明get时没有提升顺序或者淘汰逻辑有问题。4. 面试和实战中的高频变种4.1 LRU-K为什么需要记录访问次数经典LRU有一个致命弱点一次偶发的批量访问就能把热数据挤出去。比如系统平时只访问A、B、C三个核心数据某天凌晨一个任务批量扫描了D、E、F、G、H一系列冷数据它们瞬间占据了缓存头部把真正的热数据挤出缓存。LRU-K就是对这个缺点的改进。核心思想是只有访问次数达到K次的数据才进入缓存否则只记录访问时间戳。淘汰时比较的是“倒数第K次访问时间”最早的那个被淘汰。K通常取2或3既过滤掉了单次偶发访问的污染又不会要求太高的访问频次才能进缓存。实现上LRU-K需要维护两个结构一个访问历史队列记录还没进入缓存的key的最近K次访问时间一个缓存队列记录已进入缓存的key。当某个key在历史队列里的访问次数达到K才被提升进缓存队列。代价是额外一套数据结构和判断逻辑所以业务中如果热点数据相对稳定、偶发扫描不常见经典LRU其实已经够用。4.2 手撕时的边界条件与测试用例面试官不会只盯着主流程他们往往从边界条件里看出你的代码“地基”稳不稳。capacity传0构造函数不能抛异常put任何key都装不下size需要保证不会大于0。重复key的put不能忘更新value也不能让size增加。get一个刚被淘汰的key返回-1缓存结构不能出现脏数据。缓存中只有一个真实节点时淘汰addToHead和removeTail要正常工作借助虚拟节点这一步不会出错但如果你没写虚拟节点而用null处理十有八九要翻车。淘汰后残留引用removeTail之后必须从哈希表删除对应key否则缓存只有1个容量你put后get却还能找到那个早该“消失”的数据。我最常看到的错误是新增节点时先在哈希表里put再addToHead如果哈希表put成功但链表操作抛异常数据不一致。虽然Java里链表操作不会抛异常但这个顺序习惯一旦带到其他语言或复杂场景会埋雷。稳妥的顺序是先完成链表链接再更新哈希表删除时则反过来先删哈希表再摘链表节点。4.3 多线程场景下的LRU优化方向面试官问到“你的LRU能用于线程安全场景吗”标准答案是不行因为HashMap和链表操作不是原子的。最简单的方式是给get和put加synchronized但这样所有访问都串行化缓存性能优势全没了。优化方向是锁粒度细化哈希表换成ConcurrentHashMap提供并发读链表操作仍然需要一把全局锁因为链表本身的结构修改无法分段加锁。再进一步可以借鉴分段缓存的设计按key哈希分片每个分片独立维护一套LRU结构分片之间互不干扰锁粒度被分散到多个分片整体吞吐量大幅提升。但这也意味着每个分片的容量需要单独分配实际工程里很少自己造轮子直接用Caffeine这类成熟库更靠谱。5. 生产环境中的LRU不只存在于面试题里5.1 Redis的近似LRURedis作为内存数据库内存就是它的核心资产淘汰策略必须优中选优。你可能以为Redis用的是教科书里的严格LRU其实它用的是“近似LRU”。为什么不用严格LRU严格LRU需要维护一条全局双向链表每次访问都要移动节点Redis是单线程处理命令任何O(1)但高频的操作都会挤占命令执行时间。更重要的是链表结构本身要额外占用内存Redis每条key的元数据已经不小了再来一条链表指针内存开销直接翻倍。Redis的做法是给每个key维护一个24位的LRU时钟记录最近一次访问的时间戳。淘汰时不是扫描全部key而是随机抽取若干个key默认5个通过maxmemory-samples配置淘汰其中LRU时钟最小的那个。3.0版本之后还加了一个淘汰候选池每次抽样的结果放进池子里淘汰池中最旧的整体命中率比纯随机采样更接近严格LRU。这个设计给我们一个启示很多时候“足够近似”比“完全准确”更重要。为了一个理论上的精确模型付出性能或复杂度的巨大代价生产环境里往往不划算。5.2 操作系统中的LRU变体Clock算法操作系统页面置换是LRU的老家。但严格LRU在那里同样不好实现每个页面的访问时间维护成本太高硬件也未必支持精确到每次访问的时间戳。于是有了Clock算法也叫二次机会算法。它把物理页面排成一个环形链表每个页面带一个引用位use bit。页面被访问时引用位设为1。淘汰时从当前指针位置开始扫描如果引用位是0淘汰这个页面。如果引用位是1把它改为0指针移向下一个页面相当于给这个页面“第二次机会”。环形扫描一圈后必然能找到引用位为0的页面。这个算法本质上是LRU的粗粒度版它不精确记录“多久没被访问”而是记录“这一轮扫描里有没有被访问过”。硬件实现简单性能也够用。还有MySQL的InnoDB Buffer Pool用的也是改良LRU——把链表分成young区和old区数据读入先放在old区头部只有待在old区超过一定时间后再次被访问才提升到young区。这样设计的目的就是防止全表扫描一次性占用整个缓冲区把真正的热数据挤出去。5.3 Java生态里的现成实现LinkedHashMap与Caffeine实际写业务代码时很少有人真的从零实现LRU。Java里最简单的方式就是前面提过的LinkedHashMap重写适用于中小规模场景。但LinkedHashMap有一些明显短板它不是线程安全的它的淘汰动作发生在put之后如果你希望在淘汰时做额外清理比如通知下游需要子类覆盖removeEldestEntry并在里面做副操作容量控制也不够灵活只能按元素个数淘汰不支持基于内存权重淘汰。生产里更推荐用Caffeine。Caffeine内部实现了高性能的近似LRU叫做W-TinyLFU结合了LRU和LFU的优点支持基于内存权重和访问频率的淘汰策略性能远超手写的简单LRU。如果你的项目里有一个本地缓存需要频繁读写研究一下Caffeine的配置参数比自己在LinkedHashMap上打补丁要省心得多。6. 手撕LRU的常见问题与排查经验6.1 高频错误清单我把这些年看到过的翻车现场整理成了一张表你手撕完可以对照自查。错误类型具体表现根本原因链表断链打印时卡死或报空指针addToHead指针顺序写错head.next先被覆盖删除不彻底删了一个节点但结构里还能找到它removeNode只改了后继的前驱没改前驱的后继计数错乱缓存实际节点数和size不一致put已存在的key时错误地size淘汰不及时容量早超了还不淘汰忘记在put里判断size capacityget不更新访问了老数据可它还是被淘汰get里没调moveToHead容量为零崩溃put(1,1)后get反而异常没处理capacity0的极端场景删哈希表漏删节点被淘汰但cache里还在removeTail返回的节点key没用上6.2 怎么快速定位LRU实现里的Bug手撕完如果心里没底我建议用一个“双实现对照法”来验证。先用Java自带的LinkedHashMap实现一个行为完全一致的LRU然后让手写的和它跑同一批随机操作序列任何一步结果不同立刻就能定位到问题。操作序列怎么构造用Random函数随机决定put和getkey范围控制在容量范围内每次操作后在两个实现里都执行一遍比较get结果和“get后缓存里哪些key存在”。超过1000次随机操作后如果两边完全一致正确性基本可以放心。如果你在无IDE环境下纸上手撕那就重点验三件事get之后最老的是不是被挪走了、put新key后超容量时被删的是不是最老的、重复put会不会导致size变大。这三个点覆盖了LRU的全部语义。6.3 个人实战体会我在实际练习中发现手撕LRU最大的价值不是背熟一份代码而是建立“通过结构组合换取性能”的意识。单看哈希表数据没有顺序单看双向链表数据定位太慢但两者一结合各自的问题都被对方补齐了。很多系统设计题比如设计一个缓存、设计一个限流器、设计一个最近联系人列表本质上都是在“定位结构”和“顺序结构”之间做组合。想通了LRU这一道题设计这类题目时思路会开阔很多。还有一个小技巧如果你用的是Java面试时没必要现场写import、getter、setter把核心类、四个辅助方法、get和put写清楚就足以证明能力。代码风格上我习惯把变量命名得直白一点少用缩写比如capacity直接写全size直接操作这样面试官扫一眼就能看懂沟通成本最低。另外每次写完LRU我都会顺手做一次复杂度分析get和put都是O(1)空间复杂度O(capacity)。这个分析不只是说给面试官听的也是在提醒自己——如果哪一步实现里出现了循环遍历链表那一定不符合LRU的初衷代码还需要再优化。LRU这个算法长得简单内涵不少。从面试考卷到操作系统内核再到Redis、MySQL这些工业级软件它的影子无处不在。彻底的掌握它不只是背会一个数据结构更是理解缓存系统设计的核心思路。