手写LRU缓存：从LinkedHashMap到高并发缓存设计-北京尧图网络

1. 面试官问出这道题时到底在考察什么大概没有一个Java岗位的面试能绕开“手写LRU缓存”这道题。我在哈罗出行的面试中就碰到了而且面试官不是简单丢一句“你实现一个LRU”而是先抛了一个场景假设线上有个热点商品列表QPS很高每次请求都查数据库肯定扛不住需要你设计一个本地缓存但内存又有限不能把所有数据都放进去你会怎么做如果你一上来就答“用LinkedHashMap把accessOrder设为true重写removeEldestEntry”那算是及格但大概率拿不到加分项。因为这道题真正的考察点有三个层次第一层是数据结构功底。LRULeast Recently Used最近最少使用的核心语义是“当缓存满了优先淘汰最久没被访问的条目”这句话背后需要一个能在O(1)时间内完成插入、查找、删除的数据结构组合哈希表加双向链表。哈希表负责快速定位节点双向链表负责维护访问顺序。第二层是对Java集合底层实现的理解。很多人背过LinkedHashMap的源码知道构造参数里有个accessOrder但问他accessOrder默认值是什么、为什么设置为true之后get操作会改变链表顺序、removeEldestEntry的触发时机是什么就答不上来了。面试官想确认你是真的懂还是只是背了面经。第三层是工程落地意识。实现一个玩具版LRU很简单但线上环境里的缓存还要考虑并发安全、命中率统计、容量动态调整、防止缓存击穿和雪崩。面试官往往会在你写完基础版本之后追问“如果多线程访问怎么办”“如果缓存过期了怎么处理”“如何统计命中率”这些问题才是区分初级和高级的分水岭。我当时在哈罗的面试流程里这道题属于二面手写代码环节。面试官把题摆在共享文档里要求先讲思路再动手写写完还要自己补充测试用例。整个过程大概持续了二十分钟考察的深度明显比背一道LeetCode题要狠得多。2. 先别急着写代码把LRU的淘汰逻辑吃透面试时最忌讳的就是拿到题就闷头写。我先在共享文档里画了一个简单的示意图把数据流动过程讲清楚面试官点头之后才开始写代码。LRU的全称是Least Recently Used翻译过来就是“最近最少使用”。它的淘汰逻辑非常符合直觉假如你的手机里装了50个App但你平时常用的只有五六个当手机存储不够需要清理时你肯定会把那些很久没打开过的App删掉而不是删掉每天都要用的微信。LRU做的事情就是这个当缓存容量达到上限优先淘汰那些最久没有被访问过的数据。这里有一个关键点需要理解LRU的“访问”包括读和写。读了一个缓存条目这个条目就会被标记为“最近使用”写入一个新条目或者更新一个旧条目同样会把它提到最前面。而被淘汰的一定是链表尾部那些“最久没被碰过”的数据。用哈希表加双向链表来实现LRU好处非常明显哈希表HashMap保存key到链表节点的映射这样查找一个key对应的节点时不需要遍历链表直接通过哈希表定位时间复杂度O(1)。双向链表维护数据的访问顺序。链表头部是最新被访问的节点链表尾部是最久未被访问的节点。每次访问一个节点就把它从当前位置摘下来移动到链表头部。每次新增节点也是插入到链表头部。当容量满了直接删除链表尾部的节点。删除链表节点时由于是双向链表可以拿到节点的前驱和后继指针不需要遍历查找前驱删除操作的时间复杂度同样是O(1)。如果把数据结构换成数组加哈希表数组移动元素的时间复杂度是O(n)换成单向链表删除节点时需要遍历找前驱时间复杂度也是O(n)。LRU要求所有核心操作都是O(1)所以“哈希表加双向链表”这个组合就成了唯一的标准答案。不过面试的时候可以多提一句为什么不是哈希表加单向链表因为单向链表删除一个节点时需要知道它的前驱节点才能把前驱的next指向后继。你只是通过哈希表拿到了当前节点并不知道前驱是谁只能从头遍历。双向链表每个节点都保存了prev指针删除时直接操作prev和next就可以这才是LRU引入双向链表的根本原因。3. 基于LinkedHashMap的面试版本三分钟写出及格答案在讲完整的手写实现之前先说说大多数面试者最常用到的方案基于LinkedHashMap。这个方案代码量小逻辑清晰适合在面试时间紧张的时候使用。LinkedHashMap本身就是HashMap的子类它在HashMap的基础上维护了一个双向链表用来记录插入顺序或者访问顺序。关键代码就三块import java.util.LinkedHashMap; import java.util.Map; public class LRUCacheK, V extends LinkedHashMapK, V { private final int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true); this.capacity capacity; } Override protected boolean removeEldestEntry(Map.EntryK, V eldest) { return size() capacity; } public V get(Object key) { return super.get(key); } public V put(K key, V value) { return super.put(key, value); } }这段代码里有两个关键点面试官几乎必问。第一个是super(capacity, 0.75f, true)这行。第三个参数accessOrder如果传falseLinkedHashMap就按照插入顺序维护链表如果传true就按照访问顺序维护。为什么必须传true因为LRU依赖的是“最近访问”而不是“最近插入”。一个key被get了之后它应该变成最新的如果accessOrder为falseget操作不会改变链表顺序这个key仍然是按插入时间排列淘汰时可能错误地淘汰掉一个刚被访问过的数据。第二个是removeEldestEntry方法的触发时机。这个方法在每次put之后都会被调用参数eldest是链表的头节点。这里注意LinkedHashMap的链表头其实是最老的节点不是最新的节点。它的链表结构是“头部最老尾部最新”。当size() capacity时返回trueLinkedHashMap就会自动把链表头部的节点删除。所以这个版本里removeEldestEntry的作用不是主动删除而是告诉LinkedHashMap“现在容量超了你可以把最老的清掉了”。如果一个面试者只写了LinkedHashMap版本我建议最好主动补充一句这个方案虽然简单但它的get和put都依赖LinkedHashMap内部的entry结构每个节点除了key和value还额外存了before和after两个指针内存占用比纯手写实现要高而且LinkedHashMap本身不是线程安全的多线程环境下需要额外加锁。4. 手写哈希表加双向链表版本这才是面试官想看的完整答案如果面试官追问“如果不允许使用LinkedHashMap你手写一个”或者你希望展示自己真正的功底那就需要从零实现。代码结构分三部分链表节点类、LRU缓存类、操作逻辑。先定义双向链表节点class NodeK, V { K key; V value; NodeK, V prev; NodeK, V next; public Node(K key, V value) { this.key key; this.value value; } }然后定义LRU缓存类这里用到了哨兵节点技巧也就是dummy head和dummy tail避免在插入和删除时处理头尾为空的边界条件import java.util.HashMap; import java.util.Map; public class LRUCacheK, V { private final int capacity; private final MapK, NodeK, V map; private final NodeK, V head; private final NodeK, V tail; public LRUCache(int capacity) { 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) { 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); } } else { node.value value; moveToHead(node); } } 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 node tail.prev; removeNode(node); return node; } }代码看起来不多但其实每一行都有讲究。我挑几个重点拆解。为什么需要哨兵节点如果链表初始时head和tail都指向null那么插入第一个节点时就得判断“如果链表为空head和tail都指向这个新节点”删除最后一个节点时又得判断“如果删除后链表为空head和tail都指向null”。这些边界判断会污染核心逻辑。用两个哨兵节点把空链表状态也伪装成“有头有尾”的普通链表head和tail永远不被删除插入和删除操作就可以无脑写代码更简洁也不容易出bug。为什么put的时候要先判断key是否存在这是很多第一次写的人容易忽略的。如果key已经存在不需要新增节点只需要更新value并把节点移动到链表头部如果key不存在才需要创建新节点并插入头部。如果你不管三七二十一每次都往头部插一个新节点那么同一个key就会出现多个节点哈希表里存的映射和链表里的节点就对不上了。为什么淘汰的时候要先删除链表尾部节点再删除map里的映射顺序上其实没有强制要求但要注意必须先拿到尾部节点的key才能从map中删除。所以标准做法是先通过removeTail拿到被淘汰的节点然后map.remove(tailNode.key)。如果你先删map再想通过node找到keynode还在链表里没任何问题但反过来如果先移除链表节点又没保存引用后续就找不到key了。为什么get的时候也要moveToHead这是LRU的核心语义。“访问”包括读操作。如果只写一个key算访问读一个key不算那这个缓存实际上退化成了FIFO先进先出策略很久以前写入但一直在被频繁读取的数据反而会被淘汰掉。既然叫LRU就必须在读和写两个操作上都更新访问顺序。5. 多线程环境下的进阶拷问从玩具到生产级缓存基本上你手写完毕面试官不会就此打住。哈罗的面试官当时问了一个很实际的问题“线上这个缓存肯定有多个线程同时读你这个实现线程安全吗”答案当然是不安全。HashMap本身就不是线程安全的多线程并发put时可能出现数据覆盖链表操作更可能在并发时出现指针错乱甚至死循环。JDK 7的HashMap在并发扩容时形成环形链表导致CPU 100%的经典问题很多老程序员都踩过。那么怎么改造有三种思路按推荐程度排序。5.1 最简单粗暴加锁给get和put方法加上synchronized或者用Lock锁。这个方案的优点是实现简单缺点是并发度太低所有读操作全部串行化本地缓存一旦读取量大了锁竞争会成为新的瓶颈。5.2 读写分离ReadWriteLock因为大多数业务场景是“读多写少”可以用ReentrantReadWriteLock读锁共享写锁独占import java.util.concurrent.locks.ReentrantReadWriteLock; public class ThreadSafeLRUCacheK, V { private final LRUCacheK, V cache; private final ReentrantReadWriteLock lock new ReentrantReadWriteLock(); public ThreadSafeLRUCache(int capacity) { this.cache new LRUCache(capacity); } public V get(K key) { lock.readLock().lock(); try { return cache.get(key); } finally { lock.readLock().unlock(); } } public void put(K key, V value) { lock.writeLock().lock(); try { cache.put(key, value); } finally { lock.writeLock().unlock(); } } }这个方案的亮点在于多个线程可以同时执行get操作互不阻塞只有put操作才会拿到写锁其他读线程和写线程都得等待。读多写少的场景下并发能力比synchronized方案强很多。但需要提醒一点moveToHead本质上是一个写操作因为它修改了链表结构。如果用ReadWriteLockget里也会调用moveToHead这就意味着读操作内部其实涉及链表指针修改也就是说“读”不再是纯读。所以严格来说get操作也要持有写锁才能保证链表结构安全这样ReadWriteLock的读锁就没有意义了。如果面试官较真你最好主动说明这个细节然后换用下面的方案。5.3 分段加锁或ConcurrentHashMap定制想要真正的高并发业界通常不会直接给整个LRU结构加一把锁。更常见的是用ConcurrentHashMap做数据存储把LRU的淘汰逻辑改成“近似LRU”——也就是不维护严格的双向链表而是定期基于访问计数或时间戳做清理。Redis的LRU就是这种思路它并不追求严格淘汰最久未访问的key而是采用抽样淘汰策略近似达到LRU效果目的就是为了避免在每次访问时都更新链表带来的锁开销。面试时把这条链路讲清楚比单纯写出一个线程安全的LRU更能打动面试官。因为这说明你有分布式缓存或者高并发系统的设计意识而不只是停留在语法层面。6. 缓存过期、命中率统计和防止击穿这些“附加题”必须答出来写到这里一个“能用”的LRU缓存已经出来。但如果你想在面试中把这道题答成加分项必须提前练习下面几个追问。6.1 如何支持过期时间业务场景里缓存数据很少是永久有效的。商品价格可能五分钟变一次用户登录态可能半小时过期。一个完整的缓存组件需要支持TTLTime To Live存活时间。实现思路是在Node节点上增加一个expireAt字段写入数据时记录当前时间加上过期时长。读取数据时先判断当前时间是否大于expireAt如果大于说明已过期直接返回null并从map和链表中移除。需要有一个后台线程定期扫描过期节点并清理否则过期条目会一直占据内存。class NodeK, V { K key; V value; long expireAt; NodeK, V prev; NodeK, V next; }这个方法能淘汰过期数据但它和LRU的淘汰逻辑是两套独立的机制面试时要分清楚LRU管的是“容量满了淘汰谁”TTL管的是“数据过期了清除谁”。6.2 如何统计命中率面试官问命中率是在考量你是否关注缓存的实际效果。没有命中率的缓存就像没有仪表的汽车你根本不知道当前驾驶状态好不好。实现很简单在缓存里维护两个计数器totalRequests和hitCount。每次get的时候totalRequests自增如果命中则hitCount自增。命中率就是hitCount / totalRequests。关键是你拿到命中率之后要会分析。命中率偏低说明缓存的数据和实际访问的数据匹配度不高可能是淘汰策略不合理也可能是缓存容量太小或者热点数据过于集中。线上一般通过监控平台实时展示面试时你把这个分析逻辑说出来就已经超出一般候选人的认知范围了。6.3 如何防止缓存击穿缓存击穿指的是某一个热点key过期的一瞬间大量并发请求同时打到数据库。本地缓存也存在这个问题比如你缓存了一个热搜榜单某个瞬间缓存过期失效恰好有上千个请求来查这个榜单就可能把后端服务打垮。常见方案是互斥锁只有一个线程能去数据库加载数据并回填缓存其他线程等待并重试。代码思路public V getWithMutex(K key) { V value cache.get(key); if (value ! null) { return value; } lock.lock(); try { value cache.get(key); if (value null) { value loadFromDB(key); cache.put(key, value); } return value; } finally { lock.unlock(); } }这里有个Double-Check的操作拿到锁之后要再查一次缓存不然可能重复加载数据库。这套思路在Caffeine、Guava Cache里都有内置支持叫做“单飞”。7. 并发工具包里的现成实现看看Caffeine和Guava是怎么做的如果你以为LRU只能靠手写那说明面试准备还不够。生产环境里Java生态中已经有成熟的本地缓存库面试官如果问到“实际项目中你会怎么选型”只要提到下面两个库就能展示出你的工程视野。Guava Cache是Google Guava提供的本地缓存组件它不完全是LRU默认采用的是一种类似LRU的访问顺序淘汰策略同时支持过期时间、弱引用、统计命中率、自动加载等能力。Caffeine是后起之秀性能比Guava Cache更高底层基于Java 8的ConcurrentHashMap结合Window TinyLFU淘汰算法命中率比纯LRU更高Spring Boot 2.x之后的默认本地缓存就是Caffeine。这里想提醒一个容易混淆的点Caffeine默认淘汰算法不是LRU而是TinyLFUTiny Least Frequently Used。它通过一个频率过滤器记录每个key的访问频率结合一个窗口缓存来应对突发流量。简单理解就是它不只是淘汰“最久没访问”的还会考虑“访问频率最低”的这样做的好处是避免那些偶发高频访问的数据被误淘汰。面试时提到这种进化会给人留下“这个人的知识不是停留在教科书层面”的印象。8. 我在面试现场踩过的一个坑忘记处理key为null的情况分享一个真实经历。我第一版手写LRU时没有考虑key为null的情况。面试官看了一眼问“如果调用put(null, value)会发生什么”我当时一愣意识到HashMap允许null键它会把null哈希成0所以代码不会报错但这个null key会被正常缓存如果业务代码里大量误传null可能是bug的根源。实际上对于缓存组件来说null值的处理策略是要提前设计的。有些缓存设计为“不缓存null”因为null往往表示数据不存在缓存下来会掩盖真实的数据状态但有些场景又需要缓存null防止恶意key反复查询数据库布隆过滤器也是类似思路。面试时遇到这种开放问题最好的回答方式是先说明你们业务里对null的定义再说明缓存组件的设计如何与之对齐。还有一个容易忽略的坑重写equals和hashCode。如果使用自定义对象作为key而没有正确重写这两个方法那么HashMap里两个语义上相等的对象会被当成不同的key缓存会出现数据错乱。面试写代码时用Integer、String这种基础类型作为key最安全如果你非要展示自定义key一定记得补充说明hashCode和equals的重要性。9. 把这些知识点串成一套面试话术最后聊聊怎么把上面的知识点组织成一个完整的回答。面试官让你手写LRU很多人一上来就是写代码写完了就等下一题。其实更好的方式是按照“设计理念—数据结构—代码实现—进阶优化—工程实践”这条线索来展开。9.1 先说设计理念“LRU要解决的核心问题是有限内存下的数据淘汰。它基于时间局部性原理认为最近被访问过的数据在未来也更有可能被访问所以淘汰时优先淘汰最久未使用的。”这一句话能让面试官知道你不仅会写代码还理解背后的计算机系统原理。9.2 再说数据结构选型“我用哈希表加快慢指针的双向链表。哈希表保证O(1)的查找双向链表保证O(1)的插入和删除。每个节点同时保存key、value、prev和next引用。”9.3 然后写核心代码按前面手写版本的逻辑写出来即可边写边注释每一步的作用。9.4 最后主动聊进阶写完代码不要停主动说“这个版本是单线程安全的实现。如果多线程环境我会用锁或者参考Caffeine的近似淘汰算法。如果考虑过期时间和命中率统计我还需要扩展节点字段……”这时候面试官往往会顺着你的话往下问整个面试节奏就掌握在你手里了。9.5 一个可以加分的类比如果面试官看起来对Java不太熟悉或者你想把问题讲得更通俗可以用食堂窗口来比喻食堂窗口有限每个窗口后面排队的人就是缓存里的数据。窗口最前面的菜是最多人点的相当于链表头部。当窗口满了新菜要上架就得把排队最少、最不受欢迎的那个窗口后面的菜撤掉。如果有人突然点了某个菜这个菜就要被挪到最前面去。这个比喻虽然简单但能反映出你具备把抽象概念转化为具象场景的表达能力而这恰恰是团队协作里非常重要的素质。10. 从这道题延伸出去值得补的底层知识面试结束不代表学习结束。LRU缓存这道题背后延伸出的知识点几乎覆盖了Java工程师需要掌握的核心领域如果你在这道题上被问住了建议按下面几个方向补齐。10.1 LinkedHashMap源码精读花一个下午把LinkedHashMap的源码通读一遍重点看这三个方法afterNodeAccessget时调整顺序、afterNodeInsertionput后清理最老节点、afterNodeRemoval删除节点后维护链表。理解了这三个钩子方法就能明白为什么LinkedHashMap只需要一行removeEldestEntry就能实现LRU。10.2 ConcurrentHashMap的并发原理LRU的哈希表部分如果换成ConcurrentHashMap数据结构还能保持同步吗答案是不能因为双向链表的操作不是原子的。要深入理解CAS和synchronized在不同JDK版本中的配合方式才能明白Caffeine为什么能实现那么高的并发性能。10.3 Redis的过期与淘汰策略Redis作为生产环境最常用的分布式缓存它的内存淘汰策略是考察Java工程师的常见延伸问题。Redis默认的noeviction策略不淘汰任何数据如果内存满了直接返回错误allkeys-lru策略会对所有key执行LRU算法volatile-lru只对带过期时间的key执行。Redis实现的近似LRU算法非常有意思它只随机采样几个key然后淘汰其中最旧的不是全局扫描这个思路值得深入理解。10.4 缓存一致性写了一个本地缓存之后紧接着要回答的就是“数据库和缓存不一致怎么办”。Cache Aside Pattern是最常见的方案读的时候先读缓存读不到就读数据库再回填写的时候先更新数据库再删除缓存。为什么是删除缓存而不是更新缓存因为更新缓存的并发问题更多而删除缓存让下次读取时自然回填更简单可靠。11. 写在最后这道题的真正价值哈罗出行的面试已经过去一段时间了但我对这道LRU缓存题印象依然很深。它看起来是一道算法题实际上考的是一个人的基础功、工程意识和沟通能力。算法题本身可能只值五分钟但围绕它展开的讨论——并发、过期、命中率、缓存击穿、组件选型——才是决定面试成败的关键。如果你最近也在准备Java面试我的建议是不要只背答案。把LinkedHashMap源码打开一行一行读把手写LRU在多线程场景下跑一跑用jstack看看线程状态把Caffeine的官方文档过一遍理解它的淘汰策略为什么比纯LRU更适合现实负载。这些功夫花下去以后再遇到任何“缓存”相关的面试题你都能从原理层面讲清楚而不是停留在“我背过这道题”。最后分享一个实用技巧面试前自己造一个带main方法的工程分别用LinkedHashMap版本、手写版本和Caffeine版本实现LRU缓存然后写一段并发压测代码对比性能差异和命中率差异。这个实验做完你对缓存的认知会比其他面试者高出一个维度而且面试时你能拿出真实的对比数据来讲说服力远超干巴巴地背八股文。

手写LRU缓存：从LinkedHashMap到高并发缓存设计

相关推荐

Hallmark T3 组件原型：Single Huge Quote——用一句巨型引言撑起整块版面的排版设计指南

芯片级EMI设计：从源头治理电磁干扰

嵌入式四大方向本质：MCU、Linux应用、驱动与硬件的能力坐标系

更多资讯

CORE API 接入指南：用 scientific-agent-skills 的 paper-lookup 技能解锁开放获取全文检索

Label Studio Interface 详情页完全指南：预览、版本管理与项目关联

STM32 SPI驱动AD7172：从Flash例程迁移到24位ADC的完整实践

小米的问题从来不在舆情：产品、品牌、组织与用户的底层逻辑解析

OI-wiki 计算几何扫描线算法全解：矩形面积并、二维数点与 B 维正交范围

校园奶茶店微信小程序毕业设计：从登录支付到订单管理的全流程实践

今日更新

SpacetimeDB C++ 模块库实战：用 C++20 在数据库内构建 WebAssembly 模块

别踩雷！不是所有 AI 写作工具都靠谱，2026 高校认可工具精选

SSM+MySQL幼儿园管理系统源码解析：从部署到优化

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？