手写LRU缓存算法这个话题网上已经有很多版本了但大部分都停在用LinkedHashMap重写一个removeEldestEntry的程度。我能理解面试或者日常开发里碰到缓存淘汰需求第一反应就是找个现成的轮子。但如果你真的打算手写一版LRU并且想把它写明白、写对、写到能在生产环境里扛住压力那这篇文章应该能帮到你。我会从最基础的场景说起讲到HashMap加双向链表的经典实现再深入到几个真正会让人翻车的细节最后聊一些面试和工作里更进阶的思考比如热点数据污染、多级缓存和并发安全。全程都是我自己写过的代码、踩过的坑不绕弯子。1. LRU缓存到底在解决什么问题1.1 一个真实场景缓存失效带来的连锁反应先来说个实际场景。假设你在维护某个订单查询接口数据库里存着几千万订单数据用户端会高频查询最近半小时的订单状态。最开始你直接查库QPS一上去数据库连接池就告警了慢查询日志里全是同一条SQL。然后你引入了缓存把最近查过的订单放进去。缓存一上接口P99从800ms降到了50ms效果立竿见影。但问题来了缓存空间是有限的不可能把所有订单都放在内存里。当缓存满了新数据要进来就得有人出去。谁出去这就是淘汰策略的职责。最朴素的思路是先进先出FIFO谁先进来谁先走。但你很快发现这有问题某个订单虽然是很早之前查过一次但它其实仍然在被高频查询只是查询频率是间歇性的。如果它进来了却被FIFO无情淘汰下一次访问就会再次穿透到数据库。LRULeast Recently Used最近最少使用的思路就是当一个数据被访问过就把它标记为最近使用当缓存满优先淘汰那些最久没被访问的数据。它解决的核心问题是把有限的内存资源优先留给那些近期活跃的数据。1.2 怎样理解最近最少使用这个定义LRU的淘汰依据不是使用次数而是距离现在的时间间隔。你可以把它想象成一个原始的登记表每个数据进来时在表上盖一个时间戳每次被访问时间戳刷新成当前时间淘汰时扫描整张表找到时间戳最旧的那条删掉。这个逻辑用直觉就能理解但如果真用每次访问都更新时间戳、淘汰时全表扫描的方式实现性能会非常糟糕。访问一次的时间复杂度是O(n)缓存越大越慢根本扛不住高并发。所以工程上几乎不会用时间戳方案。真正普遍采用的数据结构组合是哈希表加双向链表哈希表负责O(1)地定位数据是否存在、数据在链表哪个节点双向链表负责维护访问时间顺序最近访问的节点在链表头部最久未访问的在尾部。你的每一次访问核心动作就两个把被访问的节点摘下来、再挂到链表头部。淘汰时直接删除链表尾部节点就行。全部操作都是O(1)。这个组合是整个LRU实现的灵魂也是手写时最应该先想清楚的部分。2. 最容易跑偏的初版实现为什么能用不等于够用2.1 用数组维护访问时间的版本很多第一次手写LRU的人都会先写一个直观版用一个Map存key和value用一个数组或者List存key的访问顺序。访问某个key时先把key从数组里删掉再把它放到数组末尾淘汰时取数组第一个元素删掉。这样写起来确实很快二十分钟就能跑通功能。如果面试官只问讲讲你LRU怎么实现的这个版本勉强也能说。但一旦被问到get和put的时间复杂度是多少就露馅了。从数组中间删除一个元素需要把后续元素全部往前移动一位这是O(n)。当缓存容量是几千甚至几万时删除操作会变成性能瓶颈。我见过有人用ArrayList然后调remove(key)在容量1万、每秒几百次写操作的情况下接口RT直接翻了好几倍。另一个隐蔽问题是并发。ArrayList本身线程不安全如果同一个缓存实例被多个线程同时访问删除和插入操作会造成数据覆盖、元素丢失甚至ArrayIndexOutOfBounds。网上很多demo级别代码根本不考虑这个但你在真实项目里敢这么用线上迟早会给你颜色看。2.2 为什么能用和够用差距那么大手写LRU很容易写出功能正确但性能不合格的版本问题就出在对操作复杂度的理解上。你需要对每个操作都问一句它是不是O(1)查询一个key是否存在O(1)用HashMap。把一个节点从当前位置移到链表头部O(1)前提是你直接持有这个节点的引用而不是遍历链表去找它。淘汰最久未使用的节点O(1)删除尾部节点本身很快关键是能O(1)地拿到这个节点对应的key从而同步删除HashMap里的映射。第二条是重点。很多实现里把节点移到头部靠的是先删除再重新遍历链表这就是O(n)的来源。正确做法是用HashMap记录key到节点Node的映射节点持有prev和next两个指针。拿到引用之后摘除和插入都是指针操作没有任何遍历。这个设计理念可以延伸到很多场景。比如你做热更新配置、做任务调度器的超时管理凡是需要快速定位某个元素 按顺序淘汰的组合几乎都可以套用哈希表加链表的结构。LRU手写一遍真正练的是这种思考方式而不仅仅是背一道面试题。3. HashMap加双向链表的经典组合核心实现拆解3.1 数据结构选型背后的逻辑在动手写代码前先把三个角色想清楚Cache接口对外暴露get和put两个方法。Node节点链表的基本单元包含key、value、prev、next四个字段。LRUCache类内部持有一个HashMap和一个双向链表HashMap的value类型直接设置为Node节点。为什么要用双向链表而不是单向链表未经深思熟虑的选择——如果用一个HashMap维护key到节点的映射那么把某个节点移到头部时按照单向链表你要把它的前驱节点的next指针指向当前节点的next。问题是单向链表不知道前驱是谁你得从头遍历才能找到前驱。双向链表天生就能通过node.prev拿到前驱摘除节点这一步就变成了O(1)。这是双向链表在手写LRU中几乎不可替代的原因。3.2 逐段拆解一个可直接运行的版本以下是Java实现。不用第三方依赖纯JDK就能跑。import java.util.HashMap; import java.util.Map; public class LRUCacheK, V { private 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; private final NodeK, V head; private final NodeK, V tail; public LRUCache(int capacity) { if (capacity 1) { throw new IllegalArgumentException(capacity must be positive); } this.capacity capacity; this.map new HashMap(capacity); this.head new Node(null, null); this.tail new Node(null, null); head.next tail; tail.prev head; } public V get(K key) { NodeK, V node map.get(key); if (node null) { return null; } // 访问过的节点移到链表头部 moveToHead(node); return node.value; } public void put(K key, V value) { NodeK, V node map.get(key); if (node ! null) { node.value value; moveToHead(node); return; } NodeK, V newNode new Node(key, value); map.put(key, newNode); addToHead(newNode); if (map.size() capacity) { NodeK, V tailNode removeTail(); map.remove(tailNode.key); } } private void addToHead(NodeK, V node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } private void removeNode(NodeK, V node) { node.prev.next node.next; node.next.prev node.prev; } private void moveToHead(NodeK, V node) { removeNode(node); addToHead(node); } private NodeK, V removeTail() { NodeK, V result tail.prev; removeNode(result); return result; } }这段代码是我在实际项目里用过的精简版。逻辑核心就是四段初始化虚拟节点、get时移动、put时插头、容量超限时删尾。3.3 为什么引入虚拟头尾节点这里有个很实用的细节在双向链表里声明两个哨兵节点head和tail。一个表示链表头部一个表示链表尾部但实际上它们不存储任何业务数据。哨兵节点的好处是不管链表是空的、只有一个节点、还是有很多节点头部插入和尾部删除的指针操作代码都完全一样。不需要再写特判逻辑来处理如果链表为空怎么办这类分支。如果没有哨兵节点头插和尾删都得判断head、tail是否为null代码会多出一堆分支不说还特别容易在边界状态下出错。我见过不少初版实现最后崩溃都发生在缓存里只有一个元素的时候。哨兵节点直接把这个坑填平了。4. 手写过程中最容易翻车的几个细节4.1 容量边界的差一错误容量边界是手写LRU时最经典的问题。核心判断是map.size() capacity还是map.size() capacity还是一次写入时要先插后删还是先删后插假设容量是3当前map里已经有3个元素。现在put一个新key。如果写的是if (map.size() capacity) { removeTail(); }那就意味着只要达到容量上限就先删一个再插入。表面看没什么问题但如果你刚开始缓存还不满比如现在只有2个元素put第3个时map.size() capacity成立会把最老的还没被淘汰的节点删掉再插新节点。结果容量永远用不满。正确做法是先插入后判断是否超容量判断条件用map.size() capacity只删多出来的那一个。这也是上面代码里的写法。如果先把某个节点删掉再插入也是一样的结果只是要小心删除之前别忘了把对应的map映射也删掉。4.2 更新已有key时的顺序问题当put一个已经存在的key时有两个动作要做更新value、把节点移到头部。我见过有人写先删掉旧节点再new一个新节点重新插入。这样做功能没问题但白白多了一次节点对象分配和一次指针摘除操作在高频更新场景下会产生不必要的GC压力。更优雅的方式直接复用原节点找到节点修改value然后移动节点位置。整个过程中节点在链表里的邻居关系不变只是当前节点被摘除再插到头部。对应的更新value之后不需要重新put到map因为map里存的引用本来就是同一个节点对象value是节点内部的字段。有人会问如果我把value改成新值但map里没动会不会出现map里的node和链表里的node不是同一个在正确实现中不会。map的value就是链表节点的引用两者始终指向同一个对象。如果你在任何一处重新new了Node而忘记更新map就会出现这种幽灵节点——链表里有个节点但map根本查不到它或者map指向的节点已经不在链表里了。4.3 链表自环与引用丢失还有一个特别隐蔽的bug在removeNode和addToHead里如果指针更新的顺序不对链表会自环。比如在addToHead里如果你先执行head.next node再执行head.next.prev node此时head.next已经变成新节点了所以node.prev指向了node自己。没错节点自己指向自己链表直接死循环。正确顺序是先处理新节点自己的prev和next再更新前驱和后继的指针。也就是node.prev head; node.next head.next; head.next.prev node; head.next node;这个顺序的要点是先把新节点的指针都安排好再去碰链条上的其他节点。一旦你动了head.next后面引用head.next.prev时拿到的是新节点自己而不是原来的第一个业务节点。这类bug在功能测试阶段很难暴露因为链表自环后正常的插入、查询、淘汰流程可能还能跑一阵子直到某个操作遍历到死循环才会卡住。想快速定位的话调试时直接打印链表长度发现它和map.size()对不上基本就锁定问题在指针操作上。5. 进阶思考一只保留访问顺序还不够如何防止缓存被热点污染5.1 LRU的固有短板LRU虽然经典但有明显的短板它只关注最近是否被访问不关注被访问的频率。极端情况下一个热点key在短时间内被高频访问之后就不再访问了而另一个key访问频率不高但一直稳定地每隔一会访问一次。在LRU的视角里热点key因为最近被访问过会一直留在缓存里而那个稳定的低频key反而可能被淘汰。这在业务上有个很直观的场景某个秒杀活动开始后活动商品id被瞬间刷爆大量进入缓存活动结束这些商品再也不被访问但它们霸占了缓存空间把其他正常业务的缓存全挤出去了。这就是缓存污染问题。缓存的命中率会明显下降数据库压力反而上升。针对这个场景最简单的策略之一是给缓存项设置过期时间而且这个过期时间不能用固定值而是要根据业务类型分成几档。比如热点数据给30秒普通数据给5分钟。再配合LRU本身容量淘汰可以缓解大部分污染问题。5.2 LFU和LRU的取舍LFULeast Frequently Used最近最不常使用用访问次数代替访问时间作为淘汰依据。对于上面秒杀场景LFU可能表现更好因为访问频率高的key会一直待着。但LFU也有自己的问题一个key曾经被猛烈访问过之后冷下来了但因为历史计数很高它会一直赖在缓存里不走。LRU天然会把它洗掉LFU却不一定。所以在实际系统里LRU和LFU都不是银弹。很多框架会做折中比如Redis的近似LRU加上volatile-lfu策略允许用户根据场景选择。在你手写算法时也要想清楚时间维度和频率维度哪种更适合你的业务流量特征。5.3 LRU-K的近似实现思路如果面试被问到如何改进LRU一个很好的回答方向是LRU-K。简单说LRU-K记录每个key的最近K次访问时间只有当访问次数达到K次才把key放进真正的LRU缓存。这样偶尔一两次的冷访问不会立刻把数据带进缓存能有效过滤掉低质量的访问流量。而一个真正会被高频访问的数据会尽快通过K次阈值进入缓存。实现LRU-K并不需要完整再写一套。可以拆成两个阶段第一阶段是历史访问记录用一个容量小得多的LRU只记录key和时间不存value第二阶段才是真正的缓存放value。当第一阶段某个key被访问超过K次就把value写入第二阶段。这个方案对内存的额外开销很小但能明显提升缓存命中率适合读多写少、访问模式相对稳定的业务。6. 进阶思考二工程落地时的并发、一致性与成本6.1 并发安全从加锁到分段锁上面那段代码严格来说是单线程版本。真实项目里缓存必然被多个线程共享。最简单的做法是给get和put加synchronized但这样会引入全局锁竞争。当一个线程正在执行耗时较长的淘汰操作时其他所有线程的get都得排队。更好的思路是使用ConcurrentHashMap来存储映射再配合一个显式锁来保护链表的修改操作。因为get操作需要修改链表移动到头部所以不能只靠ConcurrentHashMap自身保证线程安全还是需要锁但锁的粒度可以细一些。我见过一种工程上比较平衡的做法使用ReentrantReadWriteLock读操作get获取读锁写操作put获取写锁。在读多写少的缓存场景中读锁可以并发持有只有put才串行性能比全局synchronized好不少。代价是代码复杂度上升锁的获取与释放要格外小心避免死锁。6.2 缓存与数据库的一致性问题手写LRU只是解决了缓存里放什么、满了淘汰谁的问题但还有一个更难的问题淘汰之后如果缓存再被访问怎么保证拿到的是最新的数据常见做法是旁路缓存Cache-Aside模式读时先查缓存未命中再查数据库并把结果写入缓存写时先更新数据库再删除缓存。删除不是直接更新缓存是很多团队踩过坑之后总结出来的经验——直接更新缓存会有并发写导致的数据不一致删除缓存则会强迫下一次读去数据库拉最新值。这里面还有一个坑删除缓存失败怎么办很多系统引入消息队列做异步重试在数据库写完binlog后由消费端去删除对应缓存。如果binlog消费有延迟可能会短暂出现缓存里还是旧值的情况。这个问题没有银弹只能在实时性和一致性之间做取舍。6.3 多级缓存与淘汰策略的成本权衡最后聊一点工程视野。真正的生产环境通常不是单层缓存。CPU有L1/L2/L3本地有堆内缓存下面还有Redis这一类集中式缓存再下面才是数据库。每一层都有不同的访问速度和容量成本淘汰策略的选择也不一样。在堆内缓存这一层我们可以用LRU或者LRU-K控制内存占用容量一般很小几十到几百MB级在Redis这一层虽然容量更大但仍然有限需要配置maxmemory和淘汰策略。不同数据的重要性和访问QPS差异很大因此还可以在业务代码里给缓存项设置不同的等级等级高的用独立缓存实例或独立Redis避免被其他数据挤掉。有意思的是在Java生态里LinkedHashMap本身就实现了LRU的大部分能力它内部维护了双向链表accessOrder设为true时每次get会触发afterNodeAccess把节点移到链表尾部。你只需要重写removeEldestEntry就能得到一个可用的LRU。但真正的面试题往往要求你手动实现原因就是考察你对指针操作、边界条件、复杂度分析的掌握程度。把这些基本功练扎实了写一遍LRU再去做缓存框架的二次开发或者去阅读Redis、Caffeine这类优秀开源项目的源码会顺畅很多。我在实际写这一段代码并拿去压测时最大的体会是LRU看着简单但要写得有质量核心不在于链表操作本身而在于对每一个操作复杂度的敏感度以及对缓存策略选择背后业务语义的理解。如果你也被要求写一个LRU别急着背代码先想想业务方到底需要什么访问模式再来设计你的数据结构——这样写出来的才不是一个玩具。