LRU缓存Least Recently Used最久未访问缓存这道题在算法题单里的出现频率相当高面试手写更是家常便饭。我见过不少同学能把这个概念讲得头头是道但一上手写代码就开始变形有人忘更新链表顺序有人删节点时把链表搞断有人在容量满的时候漏掉哈希表的同步删除。这些问题背后其实不是代码量不够而是没想清楚“哈希表双向链表”这个组合到底各自承担了什么职责。这篇文章把LRU拆开来讲先聊它要解决的真正问题再从零推演一遍数据结构选型接着给出可以直接抄的完整实现和边界处理最后延伸到工程里的LinkedHashMap、Redis近似LRU和并发场景。无论你是在准备面试还是工作中需要设计自己的缓存淘汰逻辑这篇都值得花十分钟读完。1. LRU要解决的真正问题不只是“删除最久的数据”1.1 为什么缓存非得淘汰不可缓存的本质是用额外空间换访问速度把热数据放在离计算更近的地方省掉昂贵的回源开销。但空间永远有限不可能把所有数据都塞进缓存所以当容量满了之后必须做出选择——谁留下谁出去。这个选择策略的质量直接决定了缓存命中率也决定了整个系统的性能表现。淘汰策略看似简单实际是三个指标之间的平衡命中率淘汰掉的数据如果很快又被访问缓存就白做了。时间开销淘汰逻辑本身不能太贵否则一次缓存访问比直接查一次数据库还慢那就本末倒置了。空间开销为了维护淘汰信息额外占用的内存也要控制在可接受范围内。LRU在这个平衡里属于“直觉最自然”的那一类如果一个数据刚被访问过那么它在短时间内再次被访问的概率会更高。所以保留最近用过的淘汰最久没用过的。这个假设在绝大多数业务场景下都成立这也是它被广泛应用的根本原因。1.2 三个操作与O(1)硬指标面试题里的LRU抽象成三个核心操作get(key)如果key存在返回对应value同时把该键标记为“最近被访问”不存在则返回-1。put(key, value)如果key已存在更新value并标记为“最近被访问”如果不存在则插入新键值对。此时若容量已满必须先淘汰最久未访问的键再执行插入。所有操作的时间复杂度要求是O(1)。这里注意题目要求是get和put全部O(1)。为什么这个约束如此关键因为缓存本身是热路径上的组件每次业务查询都可能触发一次缓存访问。如果访问一次缓存需要O(log n)甚至O(n)的时间数据量一上来缓存带来的收益会被复杂的淘汰逻辑吞掉。所以LRU这道题表面考的是数据结构实际考的是“如何用多个数据结构协作拼出极致的读写性能”。1.3 LRU语义里容易忽略的一点访问顺序才是本质很多人把LRU理解为“删除最老的数据”这个说法没有错但不够精确。LRU维护的核心状态是所有键的相对访问顺序而不是某个绝对时间戳。最近被访问过的键排在最前面最久没有访问的键排在最后面。这里的“访问”同时覆盖读和写——get命中算访问put新值也算访问put更新已有key同样算访问。也就是说只要触碰到这个key它在淘汰顺序里的位置就要被挪到最新。这个点很容易被忽略尤其是面试手写时有人写成“get只读不改只有put才更新顺序”。后面我在边界case的章节会用一个具体反例说明这种写法在特定访问序列下会直接违背LRU语义。2. 为什么“哈希表双向链表”是标准答案从暴力方案一路推演2.1 从最朴素的思路开始排除如果没学过标准解让我凭直觉去实现LRU第一版很可能是这样的用一个数组或者列表保存所有键值对每个元素附带一个lastAccessTime时间戳。访问某个key时遍历所有元素找出这个key并更新时间戳容量满时遍历所有元素找出时间戳最小的那个淘汰掉。这个方案逻辑完全正确但性能没法看。每次get和put都要O(n)地扫描一遍几万条数据之后就会明显感觉到操作变慢几十万条数据时基本就卡住了。问题出在“时间戳”这个抽象上面——为了知道谁最久没被访问需要全局比较为了更新某个key的时间需要线性查找。换个思路我干脆用队列来维护访问顺序。队首是最久未访问的队尾是最近访问的。淘汰时直接弹出队首看起来很完美。但接下来的问题是如果一个老key被重新访问了它应该从队列中间被薅出来放到队尾。普通队列做不了这个操作因为只能从一端进出。用链表可以实现从中间摘除但关键问题是——我要先找到这个节点。单链表从头遍历是O(n)等于前面所有努力白费。于是很自然地想到能不能再加一层结构让我O(1)地根据key定位到链表里的节点哈希表正好干这个事。到了这一步“哈希表链表”的组合已经呼之欲出但为什么一定是双向链表还得再往前走一步。2.2 从单链表到双向链表的关键一跃哈希表负责“根据key快速找到节点”这个没什么争议。真正卡住很多人的是找到节点之后怎么把它从链表中间摘出来在单链表里要删除节点B你必须先找到B的前驱节点A然后让A.next B.next。但你的手里只有B自己的引用B又没有指向前驱的指针所以你得从头遍历一次链表才能找到A。哈希表正好是能救命但哈希表里存的也只是B它同样不知道B的前驱是谁。解决办法只有一个让每个节点多存一个prev指针指向自己的前驱。这样一来删除操作就变成了纯粹的指针交换——不需要遍历不需要额外查找O(1)完成。双向链表由此而来。整个推导过程可以用一个表格来收束方案get定位删除任意节点维护访问顺序是否有O(1)全操作数组时间戳O(n)遍历O(n)扫描O(n)更新否哈希表优先队列O(1)O(log n)O(log n)更新否哈希表单链表O(1)O(n)找前驱O(1)否哈希表双向链表O(1)O(1)O(1)是只有最后一行才是标准答案。2.3 两个数据结构的分工一张花名册一支队伍把这个组合拆开看其实是两个数据结构在分工协作哈希表存储key - Node的映射是“花名册”。它的职责是让我在O(1)时间内通过一个key直接定位到链表里的对应节点。双向链表维护所有节点的访问顺序是“队伍”。队头是最近访问的节点队尾是最久未访问的节点。它的职责是让“删除尾部节点”和“把任意节点挪到头部”都变成O(1)操作。打个比方哈希表好比食堂的点名册你可以直接翻到某个人双向链表就是排队打饭的队伍本身每个人都知道自己前头是谁、后头是谁。现在要让排在中途的人重新排到队首只有知道前一个人是谁才能把中间的“空档”接起来。单人单向的链条做不到这点因为没法回头去改前一个人的指向。想明白这两样东西各自负责什么后面写代码就不容易乱套了。3. 手写LRU的落地细节伪节点、更新与边界3.1 Java完整实现与逐段拆解代码直接给出来这一段是能直接跑的标准实现class LRUCache { private static class Node { int key; int value; Node prev; Node next; Node(int key, int value) { this.key key; this.value value; } } private final int capacity; private final HashMapInteger, Node map; private final Node head; private final Node tail; public LRUCache(int capacity) { this.capacity capacity; this.map new HashMap(); this.head new Node(-1, -1); this.tail new Node(-1, -1); head.next tail; tail.prev head; } public int get(int key) { Node node map.get(key); if (node null) { return -1; } moveToHead(node); return node.value; } public void put(int key, int value) { Node node map.get(key); if (node ! null) { node.value value; moveToHead(node); return; } if (capacity 0) { return; } if (map.size() capacity) { Node removed removeTail(); map.remove(removed.key); } Node newNode new Node(key, value); map.put(key, newNode); addToHead(newNode); } private void addToHead(Node node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } private void removeNode(Node node) { node.prev.next node.next; node.next.prev node.prev; } private void moveToHead(Node node) { removeNode(node); addToHead(node); } private Node removeTail() { Node node tail.prev; removeNode(node); return node; } }这段代码里的head和tail是两个哨兵节点。什么是哨兵节点就是两个不存真实数据的占位节点它们不是数据的一部分而是用来简化边界处理的。如果没有它们你在处理“链表为空”“链表只有一个节点”这些情况时就要写大量判断头部插入时判断头节点是否为空删除尾部时判断尾节点是否为空……用两个哨兵把链表结构固定住之后任何真实节点都在head和tail之间插入和删除的逻辑就统一了根本不需要关心链表到底是空还是满。3.2 写代码时最容易出错的几个细节第一addToHead的指针修改顺序。上面代码里是四步node.prev head; node.next head.next; head.next.prev node; head.next node;前两步是设置新节点自己的前后指针后两步才是修改链表上原有节点的指向。这个顺序不能乱。如果你先把head.next改成node再去执行head.next.prev node那改的其实是node.prev链表就原地断掉了。建议先让新节点接好前后关系再动list上的引用。第二Node里必须存key不能只存value。原因在put的淘汰逻辑里容量满时我们要从哈希表里删掉最老的那个key靠的是map.remove(removed.key)。如果链表节点只存value那在removeTail()拿到节点之后根本不知道这个节点对应的key是什么哈希表就删不掉。这句话也经常被面试官当追问点。第三更新已存在的key时也要moveToHead。很多人写put时遇到key已存在只更新value就返回了忘了把节点挪到头部。这是最常见的逻辑遗漏之一。put命中已经存在的key也算一次“访问”访问就必须更新顺序。第四容量满时的顺序。我的写法是先删除最老的节点再插入新节点。也可以先插入再判断超容量删除但那样浪费一步。面试时你要能说清楚自己为什么选择这个顺序。提示面试手写时建议先和面试官讲清楚设计再动手写。先写Node和四个私有方法再写get/put外层比从头按get/put的顺序边想边写要稳得多。3.3 Python实现与测试用例设计Java之外Python版本也很常见。核心逻辑完全一致class Node: 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 Node() self.tail Node() self.head.next self.tail self.tail.prev self.head 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 if len(self.cache) self.capacity: old self._remove_tail() del self.cache[old.key] new_node Node(key, value) self.cache[key] new_node self._add_to_head(new_node) 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 _remove_node(self, node): node.prev.next node.next node.next.prev node.prev def _move_to_head(self, node): self._remove_node(node) self._add_to_head(node) def _remove_tail(self): node self.tail.prev self._remove_node(node) return node写完代码至少跑四个用例基础读写put(1,1)之后get(1)等于1不存在的key返回-1。容量淘汰容量2依次put(1,1)、put(2,2)再put(3,3)此时get(1)应返回-1因为最老的1被淘汰了。重复key容量2put(1,1)、put(1,2)此时缓存里还是两个节点get(1)返回2链表顺序变成1在前。get更新顺序容量2依次put(1,1)、put(2,2)、get(1)、get(2)此时最久未访问的是1再put(3,3)时被淘汰的应该是1而不是2。这个用例专门验证get是否更新顺序。4. 工程里的LRULinkedHashMap一行版、Redis近似与并发考量4.1 Java标准库的LinkedHashMap能直接当LRU用如果你的项目里不限定手写Java标准库其实已经提供了一个几乎能当LRU直接用的类——LinkedHashMap。关键在于它的构造函数第三个参数accessOrderclass LRUCache extends LinkedHashMapInteger, Integer { private final int capacity; LRUCache(int capacity) { super(capacity, 0.75f, true); this.capacity capacity; } int get(int key) { return getOrDefault(key, -1); } void put(int key, int value) { super.put(key, value); } Override protected boolean removeEldestEntry(Map.EntryInteger, Integer eldest) { return size() capacity; } }这段代码背后的机制是accessOrdertrue时LinkedHashMap内部的双向链表会按访问顺序来维护元素位置——每次访问一个元素它就会被移动到链表末尾。注意这里的方向和手写版是反的手写版头部是最近访问LinkedHashMap里尾部是最近访问。而removeEldestEntry这个钩子方法会在每次put完成后被调用返回true时就自动删除链表头部的元素也就是最久未访问的那个。这里有个细节值得说构造函数的capacity参数在LinkedHashMap里是初始容量不是最大容量。真正限制最大容量的是你覆写的removeEldestEntry里的判断逻辑只要当前size()超过设定的capacity就删除最老元素。所以这两个capacity含义不同面试时如果提到这个方案千万别被追问住。那面试时能不能直接写这个我的建议是可以提但别只提。面试官想考察的是你对数据结构组合的理解而不是你背Java API的能力。更好的回答是先独立实现一遍哈希表双向链表然后主动提一句“Java的LinkedHashMap本质就是这种结构生产环境我会优先考虑它因为不用自己维护链表的增删细节”。这样既展示了你懂底层也展示了工程判断力。4.2 并发场景手写LRU不是终点锁与粒度才是重点上面手写的LRUCache是线程不安全的。多线程同时读写时HashMap本身就不安全链表增删也会互相干扰。最简单的做法是在get和put上直接加synchronized但整个缓存就退化成了串行访问在高并发场景下可能比不加缓存还慢。工程里常见的优化思路有三个方向全局锁细粒度操作用一个ReentrantReadWriteLock读多写少场景下读锁可以并发只有写操作互斥。但LRU的“读也要更新顺序”意味着每次get命中都会触发一次链表写操作读锁的优势会被削弱。分段锁或Striped锁把哈希表分成多个段每个段一把锁不同段的读写互不干扰。但链表是全局共享的结构分段后“全局淘汰最老节点”的操作仍然需要全局协调复杂度大幅上升。局部缓存最终一致给每个线程或CPU核心一份独立的局部LRU缓存定期合并或互相同步。这种思路在很多高性能缓存框架里都能看到变体。Caffeine就是一个典型代表。它的核心结构是Window-TinyLFU里面不仅有LRU的影子还加入了LFU的频率统计、频率草图Frequency Sketch和W-TinyLFU窗口设计。在这种设计里LRU只是构造成分之一不再需要每次get都精确地挪动链表节点而是通过概率性采样和近似记数来维持高命中率。这里要传达的认知是手写LRU追求的是逻辑上的“严格正确”工程化的LRU则经常选择“近似正确极低开销”。理解了这两者之间的差异你看生产代码时就不会觉得它们“不够标准”了。4.3 Redis为什么不做严格LRU抽样淘汰的工程智慧Redis是一个绕不开的例子。它支持maxmemory-policy配置其中就有allkeys-lru和volatile-lru。很多人默认Redis的LRU是“严格LRU”其实不然——Redis用的是近似LRU。为什么不直接上严格LRU因为Redis存储的key数量可能达到百万级甚至更多。如果给每个key都维护一套双向链表前驱后继指针内存占用至少翻倍而且每次访问都要更新链表顺序在高并发访问下还要处理锁竞争这笔账算下来太贵了。Redis的近似做法是在RedisObject里保存一个LRU时钟字段记录这个key最近一次被访问的近似时间。每次需要淘汰内存时并不扫描全部key而是从数据库里随机抽取maxmemory-samples个key默认是5个选出其中空闲时间最长的那个淘汰掉。抽样的结果是淘汰质量不如严格LRU——可能刚好错过真正的“最久未访问”——但在10万级key里5个样本选出来的淘汰目标已经足够接近最优解了。如果调大maxmemory-samples比如到10甚至20近似程度会更好但CPU消耗也会相应增加。Redis 4.0之后还加了LFU模式allkeys-lfu采样方式不变只是把判断依据从“最近多久没访问”换成了“最近访问频率”。底层同样是抽样近似统计而不是全量精确计数。这个例子很能说明问题业务规模一大“严格正确”的内存和维护成本会压倒一切优雅性近似方案才是立足点。4.4 从LRU衍生出来的其他淘汰策略LRU之外还有一串变体值得知道LFULeast Frequently Used按访问频次淘汰适合“某些key长期高频、但并不是刚刚被访问”的场景。实现难点在于频次统计的更新标准解法是哈希表频次桶链表比LRU的实现复杂一个档次。LRU-K一个key要被访问满K次之后才被认为值得进入缓存核心区。这样做能有效过滤掉“一次性扫描”对缓存的冲击——海量数据里的每个key都只访问一次如果全部进缓存真正高频的热点数据反而被挤出去了。2Q把缓存分成两个队列一个是FIFO队列存放第一次访问的数据一个是LRU队列存放被二次访问晋升的热数据。效果和LRU-K类似但实现更贴近工程。Clock算法操作系统页面置换里的经典方案。每个页面有一个“使用位”指针像时钟一样循环扫描遇到使用位为0的页面就淘汰为1的就把使用位置0继续扫。这是严格LRU在资源受限环境下最著名的近似替代。这些变体的核心思想都是同一个用可控的开销去逼近“按访问时间或频率淘汰”的理想策略。理解LRU本身等于拿到了理解这些变体的钥匙。5. 面试追问环节四个最容易被问倒的边界case5.1 删除尾节点时用什么从哈希表里移除这是一个高频追问。很多手写版本在removeTail时只把链表尾节点摘掉了然后就没有然后了。哈希表里那个key还留在map里后面再次get这个key时哈希表返回一个已经被摘除的节点逻辑直接错乱甚至触发空指针。正确的做法是链表节点里不止存value还要存key。这样在removeTail()之后用map.remove(removed.key)把哈希表里的对应条目也删掉。这也是整个链表中“唯一通过key在哈希表里定位不到、却必须反向删除哈希表条目”的位置所以节点本身必须带着key这个信息。5.2 get操作要不要更新节点顺序这个问题我在前面提过一次但值得单独展开。面试里最容易写错的就是把get当成“纯读操作”。看下面这个序列容量为2依次执行put(1, 1) put(2, 2) get(1) // 命中1被标记为最近访问 get(2) // 命中2被标记为最近访问 put(3, 3) // 容量满需要淘汰一个如果get不更新顺序那么此时链表顺序从头到尾是3新插入- 1 - 2最老的是1淘汰1。但按照LRU语义最近访问的是2接着是1最久没被访问的反而是刚插入的3。真正的LRU应该淘汰3而不是1。标准答案里get(1)和get(2)都要把对应节点挪到头部所以插入3时链表顺序是3 - 1 - 2尾部是2还是1取决于最后一次访问谁最老的那个被淘汰。一句话总结LRU里的“访问”既包括put也包括getget命中后同样要moveToHead。5.3 容量为1和容量为0的极端情况容量为1是最常见的边界。连续put(1, 1)、put(2, 2)之后1必须被淘汰然后get(1)返回-1get(2)返回2。这个逻辑只要容量判断写得正确一般不会出错。容量为0就要小心了。标准实现里我在put开头加了一个防御if (capacity 0) { return; }如果没加这个判断容量0时map.size() capacity成立removeTail()会尝试把头节点或空节点摘掉代码直接蹦出空指针。有的解法会直接不创建缓存对象但面试时题目层面还是建议加上这个防御分支同时保证get永远返回-1。5.4 如何自测以及常见bug的定位思路写完之后我习惯在脑子里跑一遍链表顺序而不是只盯返回值。比如上面用例4可以用文字模拟一遍链表的节点序列确保每一步插入和删除都符合预期。面试时能主动说“我可以用打印链表顺序来验证写错了哪一步”面试官会觉得你是有工程意识的人。常见bug基本集中在三个地方指针修改顺序addToHead写错导致链表断成环表现方式是单测死循环或者遍历输出异常。哈希表与链表不同步要么漏删要么漏插。每次put新key时记得先插入哈希表再插入链表或者反过来但一定要成对出现。忘记容量判断插入超过容量后没有淘汰缓存大小越滚越大内存被吃满。自测时多跑几个差异场景比只测一个“能跑通”的happy path要管用得多。定位的时候优先对比“链表里实际包含哪些节点”和“HashMap里实际包含哪些key”两者不一致的地方就是bug所在。面试手写还有一个实用的技巧——边写边小声说思路或者至少在心里走一遍。不要上来就闷头敲代码先让面试官知道你的设计是哈希表定位、双向链表维护顺序再去动笔。这样哪怕代码有些小错沟通分数也已经拿到了。最后说一点我个人带新人时的体会很多刚接触LRU的人会把重心放在“背下双向链表操作”上但我更建议你花时间想清楚两件事——第一每个数据结构在这个场景里的职责边界是什么第二当get和put命中时对缓存状态的影响是不是完全一致的。想明白了这两点手写只是水到渠成的事。工作几年后你会发现LRU这道题背后考的不是链表而是你面对一个需要多结构协作的问题时能不能先拆职责、再定方案。这个习惯放在任何系统设计题里都不过时。