1. 什么是LRU面试常问但你真的理解了吗先聊一个面试场景。很多同学在简历上写“熟悉常用数据结构”面试官基本不会直接问你“数组和链表的区别是什么”而是会挑一个看似简单、实际能一层层挖下去的问题“你了解LRU吗手写一个LRU Cache。”如果你只是回答“Least Recently Used最近最少使用”那大概率只能拿到一句“回去等通知”。因为这个问题考察的不是你能不能背出定义而是你有没有真正理解“缓存淘汰”这件事的本质以及能不能用代码把思想落地。LRU的全称是Least Recently Used翻译过来就是“最近最少使用”。它的核心逻辑很简单当缓存空间满了优先淘汰那些最久没被访问过的数据。这个策略背后有一个经典的局部性原理刚被访问过的数据在短时间内大概率还会被再次访问反过来已经很长时间没被访问的数据未来被访问的概率也比较低。所以与其留着一个“冷数据”占地方不如把它清掉给新数据腾位置。听起来很简单对不对但真到了实现层面事情就没那么轻松了。你需要保证每一项操作的时间复杂度都是O(1)也就是说不管是查询一个数据、插入一个新数据还是淘汰一个旧数据都不能因为数据量变大而变慢。能做到这一点才算是真正把LRU吃透了。这篇文章我就从零开始把LRU的原理、数据结构选型、手写实现、真实场景里的演进以及面试中容易被追问的细节一次讲清楚。2. 核心思想与数据结构选型为什么偏偏是双向链表加哈希表2.1 用生活场景理解LRU的“淘汰逻辑”先别急着看代码我用一个特别常见的场景帮大家建立直觉。假设你手机后台只能同时运行3个App这时候你打开了第四个App系统必须杀掉一个才能腾出内存杀谁按照LRU的思想应该杀掉“最久没被重新打开”的那个。比如你依次打开了微信、抖音、淘宝然后切回微信回了个消息。这时候后台三个App的使用时间排序就变了微信是刚用过的淘宝虽然打开得早但比抖音晚抖音是最早打开、之后一直没碰过的那个。如果再开一个App被杀的应该是抖音而不是淘宝。你会发现这个过程中有两个关键动作一是记录每个数据被访问的先后顺序二是当容量满了找到那个最久没被访问的“倒霉蛋”并删掉它。LRU的所有实现思路本质上都是在解决这两个问题。2.2 常见方案逐个排除数组、链表、哈希表谁不行既然要记录“访问顺序”最容易想到的就是给每个数据加一个时间戳每次访问就更新时间戳淘汰时扫一遍找最旧的那个。这个方案查询要O(1)但找最旧的要O(n)数据一多就废了。那用数组呢数组按访问顺序存储每次访问后要把这个元素挪到末尾数组挪动元素的代价是O(n)大数据量下也是灾难。用单向链表呢链表插入和删除确实是O(1)但你要“找到”这个节点才能操作。在链表里找一个节点需要遍历又是O(n)。另外如果你只知道要删除某个节点的前驱节点单向链表还得从头遍历才能找到前驱同样慢。这时候你可能会想能不能用哈希表来直接定位节点但是哈希表本身是无序的它只解决“快速找到”的问题解决不了“知道谁最久没被访问”的问题。所以结论已经很清晰了单独用任何一种基础数据结构都无法同时满足“快速查找”和“有序淘汰”两个要求。很多人在这里卡住是因为总想着用一个结构搞定所有事而LRU的经典解法从一开始就是“组合拳”。2.3 双向链表加哈希表各自负责什么最终的标准答案哈希表加双向链表。哈希表HashMap负责快速定位节点key是缓存的键value是链表节点的引用。这样你能在O(1)时间内找到任何一个节点在链表中的位置。双向链表负责维护访问顺序。每次访问某个节点就把它移动到链表头部链表尾部的节点就是最久没被访问的节点淘汰时直接删尾部。你可能会问为什么一定要双向链表单向不行吗这里有个特别关键的细节。当你要把一个节点移动到头部时需要先把它从当前位置摘下来然后让它的前一个节点和后一个节点接上。单向链表只有next指针你根本不知道某个节点的前驱是谁。而双向链表有prev指针摘除节点只要O(1)就能完成。这就是为什么面试时你写单向链表基本会被直接判定不合格。用一张简化的流程来说明查询某个key时先从HashMap里拿Node引用然后把该Node移动到链表头部返回value。插入新key时如果key已存在更新value并把Node移到头部如果不存在创建新Node放到头部同时放进HashMap。如果插入后链表长度超过容量就删除尾部节点同时把HashMap里对应的key删掉。整套操作下来每一步都只用O(1)时间完美满足要求。2.4 HashMap的value为什么要存Node而不是value本身这又是一个很容易被问到的细节。有些人会想HashMapKey, Value不是已经很方便了吗为什么value还要包一层Node原因是你不仅要根据key找到value还要在O(1)时间内修改这个节点在链表中的位置。如果value直接存String或Integer你在链表里移动它的时候还得在HashMap里再查一次才知道对应哪个节点根本没有节点的引用移动操作根本无法在常数时间内完成。把value设计成Node节点相当于在HashMap和双向链表之间建立了“桥梁”HashMap的value指向链表中的某一个节点。链表节点里又存了key、value、prev、next。这样你拿到一个Node既能改它的值又能操作它在链表里的位置。这也是LRU实现中最容易想不明白的一个点一旦想通代码基本就顺了。3. 手写LRU Cache一份面试能直接默写的Java实现篇幅有限我不讲太多废话直接把一份完整、可运行的Java实现放出来再逐段拆解。3.1 完整代码import java.util.HashMap; import java.util.Map; public class LRUCacheK, V { // 双向链表节点定义 static class NodeK, V { K key; V value; NodeK, V prev; NodeK, V next; Node(K key, V value) { this.key key; this.value value; } } private final int capacity; private final MapK, NodeK, V map new HashMap(); // 虚拟头尾节点省去大量空指针判断 private final NodeK, V head new Node(null, null); private final NodeK, V tail new Node(null, null); public LRUCache(int capacity) { if (capacity 0) { throw new IllegalArgumentException(capacity must be positive); } this.capacity capacity; head.next tail; tail.prev head; } public V get(K key) { NodeK, V node map.get(key); if (node null) { return null; } // 访问了就要更新位置先摘除再移到头部 removeNode(node); addToHead(node); return node.value; } public void put(K key, V value) { NodeK, V node map.get(key); if (node ! null) { // key 已存在更新值并移到头部 node.value value; removeNode(node); addToHead(node); return; } // 新增节点 NodeK, V newNode new Node(key, value); map.put(key, newNode); addToHead(newNode); if (map.size() capacity) { // 删除尾部节点也就是最久未使用的 NodeK, V tailNode tail.prev; removeNode(tailNode); map.remove(tailNode.key); } } private void removeNode(NodeK, V node) { node.prev.next node.next; node.next.prev node.prev; } private void addToHead(NodeK, V node) { node.next head.next; node.next.prev node; head.next node; node.prev head; } public int size() { return map.size(); } }3.2 为什么使用虚拟头尾节点新手最容易在这里翻车。如果你不用虚拟头节点那么当链表为空时往头部插入节点或者从头部删除节点都要专门写if判断头节点是不是null极其容易漏判断然后抛NullPointerException。有了head和tail这两个虚拟节点整个链表永远不为空插入和删除的代码逻辑就统一了。你可以把虚拟头尾理解为“哨兵”它们不存业务数据只是让边界处理变简单。这在工程上也是一个很常见的技巧。不只是LRU很多链表的题目反转链表、删除倒数第N个节点用上虚拟头节点都能少写不少分支判断。3.3 每次get都在修改数据这说明了什么有同学可能会疑惑我只是查一个数据为什么还要在链表里移动它因为get操作本身就是一次“访问”LRU判断“谁最久没被使用”靠的就是每一次访问的记录。如果一个数据只是被反复查询那它应该被保留如果一个数据已经很久没人查了它才应该被淘汰。如果get不更新顺序那你无法区分“最近被查过很多次”和“很早查过一次再也没查过”的数据淘汰策略就失效了。所以只要执行了get就必须把节点挪到链表头部。这也是面试里经常被追问的细节之一我见过很多候选人在put里记得维护顺序到了get里就忘了直接返回value这种实现是不完整的。3.4 复杂度分析get操作HashMap查一次O(1)拆节点和插头部都是O(1)。put操作HashMap查一次O(1)如果更新或新增拆节点、插头部、删除尾部也都是O(1)。因为链表节点在内存中不是连续存储的链表操作和数组不同不需要搬移大量元素所以“移动到头部”这个动作无论缓存多大耗时都是恒定的。空间复杂度是O(capacity)因为HashMap最多存capacity个key双向链表最多存capacity个节点。3.5 测试代码用数据验证正确性写完了不能光看着直接跑个测试public class LRUTest { public static void main(String[] args) { LRUCacheInteger, String cache new LRUCache(3); cache.put(1, A); cache.put(2, B); cache.put(3, C); System.out.println(cache.get(1)); // 输出 A此时访问顺序变为 1,3,2 cache.put(4, D); // 容量3已满最久未使用的2应该被淘汰 System.out.println(cache.get(2)); // 输出 null因为2已被淘汰 System.out.println(cache.get(3)); // 输出 C System.out.println(cache.get(4)); // 输出 D } }测试结果应该依次输出A null C D跑通这个用例说明基本逻辑没问题。但是面试官不会只满足于“能跑”他大概率会继续追问边界情况这部分我在最后一章统一讲。4. 从LRU到LRU-K真实系统里是怎么演进的4.1 经典LRU有什么硬伤标准LRU虽然在面试中够用但真放在生产环境里它有一个非常明显的问题缓存污染。什么叫缓存污染举个例子某个冷门数据在某个瞬间被批量访问了一次比如定时任务扫了一批历史数据它的“最近使用时间”会被顶得很靠前把真正热的数据挤出去了。但这一批数据其实以后几乎不会再被访问。结果就是缓存里留着一堆“刚被用过一次但从此冷掉”的数据真正的热数据反而被淘汰了缓存命中率直线下降。用一句话概括就是一次性的偶发访问把高频热点数据挤掉了。4.2 LRU-K多一次观察窗口为了解决缓存污染业界提出了LRU-K。这里的K不是指容量而是指“访问K次之后才进入缓存”。它的思路也很直接数据第一次被访问时不直接放进缓存而是放进一个“候选区”只记录访问次数和最近访问时间。只有当这个数据被访问的次数达到K次通常K取2才被认为有缓存价值正式进入缓存。一旦进入缓存再按照标准的LRU规则进行维护。这样做的好处是那些只被临时访问一次的数据根本进不了缓存自然也就不会污染真正的热点数据。代价是实现更复杂你需要维护一个额外的访问记录队列存储开销更大。在真实系统里很多自研缓存组件的底层其实就是LRU-2的变种。4.3 Redis的近似LRU不追求精确只追求性价比还有一个大家经常听说的场景是Redis。Redis明明有内存淘汰机制但它并没有用严格的LRU而是用了一种近似LRU的策略因为严格LRU需要维护一个双向链表对Redis这种单线程模型来说额外内存开销和操作开销都不小。Redis的近似LRU做法是给每个key记录一个最后一次访问的时间戳LRU时钟淘汰时随机采样若干个key淘汰其中空闲时间最长的那个。你可以把它理解为“抽样淘汰”不保证全局最优但大概率合理。从Redis 3.0开始Redis还引入了淘汰池pool每次随机采样之后把候选key放进一个池子里新采样的key和池子里的key比较淘汰最旧的。这样经过多轮淘汰后池子里保留的key越来越接近全局最久未使用的key效果直逼严格LRU但成本低很多。这个演进过程其实说明了一个很朴素的道理在工程上我们往往不是追求理论最优而是在效果和成本之间找一个平衡点。这个思路写进简历的项目里会显得你对问题的理解不止停留在“背出LRU”这一层。4.4 MySQL的Buffer PoolLRU也要分层另一个经典案例是MySQL的InnoDB Buffer Pool它也有类似的改进。MySQL的Buffer Pool把LRU链表分成两段young区域和old区域默认比例是5比3。新读入的数据页先放进old区域只有再次被访问到才会被提升到young区域。这个设计和LRU-K其实是同一个思路给新数据一个“观察期”避免全表扫描这种一次性读入大量冷页把真正的热页全部挤出内存。如果你在面试时能主动提到“MySQL的Buffer Pool也是这么做的”面试官对你的评价通常会高不少因为这说明你真的在平时积累过这类系统设计而不是死记硬背。5. 高频追问与避坑指南实战中容易踩的坑我一次说清楚5.1 容量为1的时候会怎样这是面试官最爱问的边界条件之一。当capacity等于1时你put一个数据进去再put第二个数据第一个数据会被立刻淘汰。这要求你的代码在链表只有1个节点的情况下remove和add操作不能出错。用虚拟头尾节点实现的话这个场景天然安全。但如果你用的是裸Node即不使用虚拟节点的实现这里就要小心了删除尾部节点的时候如果尾部正好是头节点你得把head也置空否则下一次addToHead操作就会出现悬空引用。所以我的建议是面试时直接用虚拟头尾节点的写法能少踩一半的坑。5.2 key已存在时要不要删除再插入有些同学实现put时遇到key已存在的情况会把旧节点删掉再new一个新节点插到头部。这也能实现功能但有一个隐患如果你在put过程中先删除了旧节点还没来得及把新节点放进HashMap此时如果代码抛出异常比如内存分配失败HashMap里的旧节点引用还在但链表里的节点已经被拆掉了整个缓存结构就损坏了。更优雅的做法是命中已存在的key时直接复用旧节点只更新value然后移动到头部。这样能避免频繁创建对象减少GC压力也让结构始终保持一致。5.3 并发场景下LRU怎么写如果你给面试官说“我这份代码可以用于生产环境”对方可能会追问多线程同时get和put你的HashMap会怎样答案是HashMap在多线程下扩容时会形成循环链表导致CPU飙到100%。所以生产环境里的LRU Cache至少有几种方案最简单给get和put都加synchronized变成线程安全版本但并发度很低。更好使用ConcurrentHashMap 双向链表的CAS操作这也是Redis、Guava Cache等组件实际采用的方向。最实用Java的LinkedHashMap本身就是“哈希表双向链表”的组合重写removeEldestEntry方法就能实现LRU再配合Collections.synchronizedMap或者使用并发容器能快速得到线程安全LRU。这里我多说一句如果你只是想在日常开发中快速实现一个LRU完全没必要自己手写链表。import java.util.LinkedHashMap; import java.util.Map; public class SimpleLRUK, V extends LinkedHashMapK, V { private final int capacity; public SimpleLRU(int capacity) { super(capacity, 0.75f, true); this.capacity capacity; } Override protected boolean removeEldestEntry(Map.EntryK, V eldest) { return size() capacity; } }LinkedHashMap的构造方法里第三个参数传true表示开启访问顺序模式每次get都会把对应Entry移动到链表尾部。配合重写removeEldestEntry当容量超过阈值时自动删除最老的Entry。这是日常开发中最快的LRU实现方式。不过面试官通常不满足于你用现成容器他问“手撕LRU”就是要看你能不能从底层原理出发独立实现。所以LinkedHashMap的写法适合作为“补充玩法”来展示核心还是你手写的那份。5.4 面试追问为什么不用数组加时间戳这个问题我在前面已经提到过这里集中整理成一张对比表方便你记忆方案查找效率更新顺序淘汰最旧数据综合评价数组时间戳O(1)O(n) 扫描O(n) 扫描数据量大时性能差单向链表哈希表O(1)删除需要找前驱O(n)O(1)移动节点效率低双向链表哈希表O(1)O(1)O(1)标准解法LinkedHashMapO(1)O(1)内部封装O(1)内部封装快速开发首选Redis近似LRUO(1)不维护链表随机采样淘汰成本低、效果接近5.5 常见错误自查清单我总结了几个手写LRU时最容易犯的错误写完代码后对照检查一遍能少踩很多坑是否忘了在get时更新节点顺序。删除尾部节点时是否忘了从HashMap里删掉对应的key。移动节点时是先把节点摘下来再插入头部还是直接修改了指针导致链表断裂。addToHead时新节点的prev是否指向了head。容量是否在构造时做了合法性校验。使用LinkedHashMap时是否把accessOrder参数设成了true。如果你写的版本能通过这一串检查基本就不用担心面试官在代码层面挑毛病了。最后说点我的个人感受LRU这题我前前后后看过不下几十遍自己也面试过不少人。我发现一个规律能把原理讲清楚的候选人很多但能在纸上把代码写对、写干净、还能应对追问的人其实不多。原因在于很多人习惯了“看得懂”就觉得自己“会写了”但实际上手一写就漏洞百出。所以如果你正在准备面试或者复习数据结构我的建议是不要只看我的代码自己拿纸笔手写一遍再跑几个测试用例特别是容量为1、key重复、get不存在的key这几个边界场景。写完再思考一下“如果我想把它改成LRU-K需要加哪些结构”。这样练过一轮之后LRU就不再是一个需要死记硬背的答案而是真正变成你自己的东西了。这份功夫在面试里往往最容易被看出来也最值得花时间。