尧图网页设计 
架构师面试里有个很经典的“送命题”让你讲讲缓存置换策略然后紧接着来一句“如果让你自己实现你是怎么设计的”。不少人在第一步还能侃侃而谈LRU、LFU的区别一旦要求落到源码层面瞬间就卡壳了。说白了面试官不是想听你背策略的定义而是想确认你有没有真正深入过底层实现有没有在工程层面思考过“数据结构和算法的取舍”这件事。这篇文章我要做的事非常明确从零开始手写一版带完整缓存置换策略的缓存组件代码用纯JDK实现不依赖任何第三方框架。你会看到LRU、LFU、FIFO、随机淘汰这几种策略的源码实现思路以及它们各自适用的业务场景。读完你能直接动手敲出一版可运行的代码面试时候再聊到缓存不再是背概念而是真的有货可以聊。1. 缓存组件设计的整体思路拆解1.1 为什么面试总爱问“手写缓存置换策略”先说一个我的观察。很多面试者会把“缓存”等同于Redis一聊就是Redis怎么怎么样。这种回答不能说错但它暴露了一个问题你只是在用工具并没有真正理解缓存的核心机制。面试官问“源码实现”本质上是想确认三件事第一你有没有透过Redis、Caffeine这些成熟组件去看过它们底层的设计逻辑。第二你清不清楚“缓存存储”和“缓存淘汰”其实是两层独立的东西存储解决的是“怎么放”淘汰解决的是“放不下怎么办”。第三当你面对一个“设计一个缓存组件”这种开放题时能不能快速拆解出关键模块给出合理的选型理由。我见过不少候选人能熟练背诵LRU、LFU的定义但问到底层用什么数据结构实现的时候就支支吾吾了。还有人会写“LRU就是最近最少使用”但你问他“为什么LinkedHashMap可以实现LRU”又答不上来。这就是典型的“知道概念没看过源码”。所以这篇文章我会刻意把重点放在“数据结构选型”和“源码落地”上。缓存相关的理论已经有很多文章讲过了真正稀缺的是那种能直接运行、能讲清楚每一步为什么这么写的代码。1.2 缓存的本质一个Map加一套淘汰机制剥离所有复杂的概念缓存组件最核心的就三块。存储容器不用多说就是那个“放数据的地方”。它是整个缓存的心脏所有的查询、插入、删除都要经过它。大多数缓存组件会用哈希表做存储因为哈希表能保证O(1)的读写性能。淘汰策略是“容量满了之后怎么办”的那套规则。它是缓存的灵魂决定了哪些数据应该被优先保留。淘汰器负责执行淘汰策略它需要实时跟踪每个key的访问情况、频率信息用来在容量满的时候“算账”看看谁该走。这三块之间的关系可以类比成一家餐厅的运作存储容器是餐桌客人来了有地方坐淘汰策略是餐厅的排位规则没位置的时候判断谁该被请走淘汰器是门口的那个服务员他对每位客人的“消费情况”了如指掌才能给出谁该走、谁该留的建议。控制器则是对外暴露的那层门面它统一处理get、put、remove这些操作并在这个过程中协调存储容器和淘汰器的关系。每次get的时候记录访问信息调整key的“热度”每次put的时候检查容量是否已满满了就触发淘汰每次remove的时候同步清理掉淘汰器里的访问记录防止数据残留。1.3 选型对比链表、哈希表、队列、堆各自适合谁既然要做源码级实现数据结构的选择就是第一道关卡。我直接给你一个对比表后面实现的时候你会反复用到这里的关键点数据结构核心特点适用场景复杂度哈希表HashMapO(1)的读写随机访问能力强所有缓存策略的底层存储O(1)双向链表LinkedList插入删除效率高但随机访问O(n)LRU、LFU中维护访问顺序O(1)增删O(n)查找队列QueueFIFO天然匹配先进先出语义FIFO淘汰策略O(1)入队出队小顶堆PriorityQueue能快速拿到最小值按频率排序的淘汰如LFU变种O(log n)调整堆哈希表双向链表组合既能O(1)查又能O(1)调整顺序工程级LRU、LFU标准解法O(1)这里我特别想展开说一句为什么LRU的标准解法是“哈希表双向链表”而不是单纯用一个哈希表。原因很简单单纯哈希表是无序的你无法知道哪个key是“最近最少使用”的。如果每次操作都去遍历哈希表找最小值复杂度就退化成O(n)容量一旦上去就废了。双向链表在这里的价值是维护“访问顺序”。每次访问一个key就把它移动到链表的头部那么链表尾部的自然就是“最久没被访问的”。哈希表负责存“key到链表节点的映射”这样在找某个key对应的节点时不用去链表里遍历直接O(1)拿到。这个设计思路就是LinkedHashMap底层的实现逻辑。所以面试时候你如果能把这段讲明白就已经超越80%的候选人了。2. 核心细节解析数据结构选型与失效策略2.1 双向链表节点缓存世界里最小的单元无论是LRU还是LFU双向链表节点都是最小的数据结构单元。先看一个最简单的节点定义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; } }每个节点里既存着key又存着value。有人可能会问为什么存value的时候还要单独存一个key这是因为当淘汰器要从链表中移除一个节点时它需要根据这个key去哈希表里做同步清理。如果节点里只存value不存key那到淘汰的时候你就没法反推出key哈希表里那条记录就成了永远清不掉的内存泄漏。这个细节特别重要。我在实际开发中见过有人把这个key省略掉结果到了线上排查内存占用的时候就傻眼了。内存泄漏这种东西平时不显山不露水一旦触发GC频繁排查起来极其痛苦。2.2 哈希表双向链表的联动LRU的物理基础现在我们假设缓存容量固定为3然后依次执行一系列put操作。当put(A)时A被放入哈希表同时被链接到链表头部。链表现在是A。继续put(B)、put(C)此时链表从头部到尾部是C、B、A哈希表里也存着这三个键的映射关系。现在缓存已经满了容量是3。接下来put(D)因为容量不够必须淘汰一个。按照LRU的规则链表尾部就是最久没被访问的于是淘汰A把D放到链表头部。整个过程哈希表负责O(1)定位到A对应的节点并删除链表负责O(1)在头部插入D、尾部移除A。两边配合完美实现O(1)的淘汰。如果此时你get(B)B被访问了要从链表里把B摘出来移动到头部。链表从C、B、A变成B、C、A。这个“摘出来、放到头部”的操作依赖双向链表的prev和next指针原因很简单你知道了B的prev是C、B的next是A直接让C.next A、A.prev C就完成了摘除操作。如果是单向链表你还得从头开始遍历找到B前面的节点复杂度就退化了。2.3 触发淘汰的时机put时引发的连锁反应很多人有个误解以为淘汰是“定期扫描”触发的其实绝大多数缓存组件都是“惰性触发”。所谓惰性就是只有在put新数据、且容量已满的时候才触发淘汰。这很像你手机里的照片满了只有在拍新照片的时候系统才提醒你清理空间而不是每时每刻都在后台整理相册。这种设计的好处很多。最大的好处是节省性能如果你做定时扫描就得额外维护一个后台线程还要处理并发问题。而惰性触发完全不需要这些它把淘汰的压力分摊到每次put操作上逻辑简单且没有额外开销。当然惰性触发也有它的代价就像Redis的过期清理其实也依赖于“惰性删除定期删除”的组合策略一样缓存系统中如果一个key在过期后一直没被访问它就会一直占用内存。这在某些场景下是可以接受的但在Cache-Aside这种模式里如果你对内存的敏感性很高就还需要引入额外的定期扫描机制来兜底。2.4 初始化容量与负载因子性能的第一道关卡写缓存组件的时候初始化容量的设置特别容易被人忽略。很多人直接new HashMap()就完事了这在数据量大的时候性能会非常难看。HashMap有个机制叫扩容。当元素个数达到threshold阈值等于容量乘以负载因子时HashMap会把自己的内部数组扩大一倍然后把原来的元素全部重新哈希一遍。这个过程极其耗时如果缓存组件频繁触发扩容每次扩容还会造成一次明显的延迟尖刺对要求低延迟的业务来说几乎是不可接受的。所以合理的做法是在初始化时就估算好容量尽量减少扩容次数。有个经典公式预估容量 / 负载因子 1。比如你预估最多放1万个数据默认负载因子是0.75那初始化容量就应该是10000 / 0.75 1约等于13334。这样就能做到几乎不触发扩容。这个公式背后其实还有一层考量预留一点冗余空间能让哈希分布更均匀减少冲突。哈希冲突多了链表会变长查询效率就从O(1)退化成O(n)那就得不偿失了。2.5 三种失效策略对比TTL、懒清理、定期清理大多数缓存组件真正落地的时候不会只用“容量满”这一个触发条件还会配合“过期时间”。常见的组合有三种TTL策略、懒清理策略、定期清理策略。TTL策略最好理解给每个key设置一个过期时间到了时间就直接失效。不过TTL有个坑就是key到了时间并不会自己消失还是在内存里躺着只是访问的时候会判断“你这个key是不是过期了”。所以TTL必须要跟懒清理搭配使用。懒清理是当get请求来的时候先检查key是否过期过期了就直接返回null同时删除这个key。这样虽然不额外占用后台线程但那些“过期了但一直没人访问”的key就成了漏网之鱼会一直占着内存。定期清理是额外起一个线程每隔一段时间扫描一部分key把过期的移除掉。注意是“一部分”不是全部。全量扫描太耗资源所以一般会分批执行。这种“懒清理定期清理”的组合其实就是Redis过期键删除策略的组合思路也是工程中比较稳妥的做法。3. 实操过程与核心环节实现手写LRU、FIFO、LFU缓存3.1 通用缓存接口与基础实现先定义一个通用的Cache接口方便后续扩展不同策略。接下来用一个抽象类收敛公共逻辑比如容量管理、数据统计这些。public interface CacheK, V { V get(K key); void put(K key, V value); void remove(K key); int size(); void clear(); }有了接口之后就是核心实现。我先从最简单、最容易理解的FIFO策略开始因为它最直观后面再讲LRU然后是难度最高的LFU。3.2 FIFO缓存源码队列与哈希表的经典组合FIFOFirst In First Out是最朴素的淘汰策略谁先进来谁先被淘汰。它不需要记录访问频率也不需要移动节点只需要维护一个先进先出的队列即可。public class FifoCacheK, V implements CacheK, V { private final MapK, V map new HashMap(); private final QueueK queue new LinkedList(); private final int capacity; public FifoCache(int capacity) { this.capacity capacity; } Override public synchronized V get(K key) { return map.get(key); } Override public synchronized void put(K key, V value) { if (map.containsKey(key)) { map.put(key, value); return; } if (map.size() capacity) { K oldestKey queue.poll(); if (oldestKey ! null) { map.remove(oldestKey); } } queue.offer(key); map.put(key, value); } Override public synchronized void remove(K key) { map.remove(key); queue.remove(key); } Override public synchronized int size() { return map.size(); } Override public synchronized void clear() { map.clear(); queue.clear(); } }这段代码里有个细节值得注意如果put一个已经存在的key我直接更新value并return不会重新入队。这是很关键的一步因为如果已经存在的key再次入队队列里会出现重复的key淘汰的时候就会误删一个实际上还“活着”的key。你可能已经发现了FIFO有个致命弱点它不感知访问频率。假设有一条缓存数据是热点数据每秒被访问一万次但另一条冷数据只是一次性地插入。FIFO在容量满的时候依然会把热点数据给淘汰掉因为它的判断依据是“进入时间”不是“使用频率”。这在大部分业务场景下是没法接受的。但FIFO并非一无是处。在数据访问模式相对均匀、或者你对缓存命中率的容忍度比较高的场景下FIFO因为实现简单、开销极小反而是个不错的选择。比如某些批量预热数据的场景数据是一次性加载的没有冷热之分FIFO就能满足需求。3.3 LRU缓存源码LinkedHashMap的优雅实现与手写双链表接下来是面试的重头戏LRU。先给出一版基于LinkedHashMap的实现。你只需要重写一个方法就能实现完整的LRU淘汰。这可能是JDK里最简单优雅的一段缓存代码。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; } }就这么简单。LinkedHashMap的第三个构造参数是accessOrder传true之后它就会在每次get的时候把被访问的Entry移动到链表尾部。而removeEldestEntry这个钩子方法会在每次put后检查是否需要移除链表头部那个最老的节点。这里“链表头部”对应的就是“最久未被访问”因为最新访问的都被移到了尾部。这段代码写起来容易但理解起来有一个难点为什么“最老的”在头部而不是尾部关键在于LinkedHashMap的内部实现默认是按照插入顺序维护的头部的Entry是最早插入的尾部是最晚插入的。开启了accessOrder之后它会在每次访问时把该Entry移到尾部所以头部的Entry就变成了“最久没被访问的”。容量满的时候removeEldestEntry返回trueLinkedHashMap就会把头部那个Entry删掉正好符合LRU的淘汰逻辑。不过面试如果只写这段有些面试官可能会觉得你是在“走捷径”。所以我还得给你一版手写双向链表的LRU实现。这不仅能展示你真正理解了底层原理也更接近真实项目里“自己设计一个缓存”的需求。public class LruCacheK, V implements CacheK, V { private final MapK, NodeK, V map; private final int capacity; private final NodeK, V head; private final NodeK, V tail; 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; } } public LruCache(int capacity) { this.capacity capacity; this.map new HashMap(capacity * 4 / 3 1); this.head new Node(null, null); this.tail new Node(null, null); head.next tail; tail.prev head; } Override public synchronized V get(K key) { NodeK, V node map.get(key); if (node null) { return null; } moveToHead(node); return node.value; } Override public synchronized void put(K key, V value) { NodeK, V node map.get(key); if (node ! null) { node.value value; moveToHead(node); return; } node new Node(key, value); map.put(key, node); addToHead(node); if (map.size() capacity) { NodeK, V last removeTail(); map.remove(last.key); } } Override public synchronized void remove(K key) { NodeK, V node map.remove(key); if (node ! null) { removeNode(node); } } Override public synchronized int size() { return map.size(); } Override public synchronized void clear() { map.clear(); head.next tail; tail.prev head; } 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; node.prev null; node.next null; } private void moveToHead(NodeK, V node) { removeNode(node); addToHead(node); } private NodeK, V removeTail() { NodeK, V node tail.prev; removeNode(node); return node; } }如果你要画一下这个双向链表的结构它大概是这样的head - A - B - C - tail。head和tail是哨兵节点它们不存储实际数据只是用来简化链表的边界操作。这样做的好处是无论链表里有几个节点对头尾的操作代码都是一样的不需要单独处理空链表的情况。头插和尾删的复杂度都是O(1)因为只需要调整前后节点的指针不需要遍历。哈希表负责O(1)定位双链表负责O(1)调整顺序两者配合就完成了一个时间复杂度全面O(1)的LRU。3.4 LFU缓存源码最复杂也最能拉开差距的实现LFULeast Frequently Used和LRU最大的区别是它看频率不看过期时间。LRU判断“谁最久没被用”LFU判断“谁用得最少”。这听起来更合理但实现起来难度上了一个台阶。朴素思路是给每个key维护一个计数器每次访问就加一。淘汰的时候遍历所有计数器找最小那个。这个思路能跑但有两个大问题第一每次淘汰都要全量遍历复杂度O(n)数据量一大就废了第二如果一个key在短时间内被疯狂访问它的计数器会飙到一个很高的值之后即使这个key再也不被访问也因为“历史频率太高”而永远不会被淘汰这被称为“频率污染”。工程上比较标准的LFU实现方案是用频率作为分桶把相同访问次数的key放在同一个双向链表里同时维护一个全局最小频率minFreq。这样淘汰的时候只需要从minFreq对应的桶里取链表尾部就能完成复杂度O(1)。这个思路的核心数据结构是三层嵌套外层Map存储“频率”映射到“该频率下的key列表”内层是每个频率对应的双向链表再加上存储key到“频率节点”映射的索引Map。public class LfuCacheK, V implements CacheK, V { private final MapK, V values new HashMap(); private final MapK, Integer counts new HashMap(); private final MapInteger, LinkedHashSetK frequencyMap new HashMap(); private final int capacity; private int minFreq; public LfuCache(int capacity) { this.capacity capacity; this.minFreq 0; } Override public synchronized V get(K key) { if (!values.containsKey(key)) { return null; } increaseFreq(key); return values.get(key); } Override public synchronized void put(K key, V value) { if (capacity 0) return; if (values.containsKey(key)) { values.put(key, value); increaseFreq(key); return; } if (values.size() capacity) { evict(); } values.put(key, value); counts.put(key, 1); frequencyMap.computeIfAbsent(1, k - new LinkedHashSet()).add(key); minFreq 1; } private void increaseFreq(K key) { int count counts.get(key); counts.put(key, count 1); frequencyMap.get(count).remove(key); if (frequencyMap.get(count).isEmpty()) { frequencyMap.remove(count); if (count minFreq) { minFreq; } } frequencyMap.computeIfAbsent(count 1, k - new LinkedHashSet()).add(key); } private void evict() { LinkedHashSetK keys frequencyMap.get(minFreq); K key keys.iterator().next(); keys.remove(key); if (keys.isEmpty()) { frequencyMap.remove(minFreq); } values.remove(key); counts.remove(key); } Override public synchronized void remove(K key) { values.remove(key); Integer count counts.remove(key); if (count ! null) { frequencyMap.get(count).remove(key); if (frequencyMap.get(count).isEmpty()) { frequencyMap.remove(count); if (count minFreq) { minFreq; } } } } Override public synchronized int size() { return values.size(); } Override public synchronized void clear() { values.clear(); counts.clear(); frequencyMap.clear(); minFreq 0; } }这段代码里的关键就是minFreq指针。当需要淘汰的时候minFreq指向的那个频率桶里装的就是“访问次数最少”的key们。淘汰时直接从这个桶里取最前面的就可以了。因为LinkedHashSet保证了插入顺序所以最早进入该频率的会先被淘汰。minFreq的更新逻辑也很巧妙当某个key从频率n升到n1时如果频率n变得空了而且n恰好等于minFreq说明“当前最少访问次数”的桶空了那就把minFreq加1。这样的话minFreq永远指向“实际上存在”的最小频率。这里有一个需要特别注意的坑如果直接new LinkedHashSet()而不指定初始容量每次扩容也会带来额外的开销虽然不像HashMap那么严重但也值得优化。LFU面临的典型问题是“频率污染”。那怎么解决呢工程上常见的做法是给频率加衰减机制比如定期把所有频率都除以2或者记录最近一次访问时间超过一定时间后把频率重置。这样那些“曾经很热、后来变冷”的key就不会永远占着位置不走了。3.5 Random Cache最简单但工程上也有用的策略很多人可能觉得随机淘汰太“没技术含量”实际上在分布式缓存系统中随机淘汰反而在某些场景下表现不错。它的实现比FIFO还简单只需要在容量满的时候从哈希表里随机挑一个key删掉。public class RandomCacheK, V implements CacheK, V { private final MapK, V map new HashMap(); private final int capacity; private final Random random new Random(); public RandomCache(int capacity) { this.capacity capacity; } Override public synchronized V get(K key) { return map.get(key); } Override public synchronized void put(K key, V value) { if (map.containsKey(key)) { map.put(key, value); return; } if (map.size() capacity) { int index random.nextInt(map.size()); K keyToRemove (K) map.keySet().toArray()[index]; map.remove(keyToRemove); } map.put(key, value); } Override public synchronized void remove(K key) { map.remove(key); } Override public synchronized int size() { return map.size(); } Override public synchronized void clear() { map.clear(); } }随机淘汰的工程价值有两个一是代码极简二是它没有“频率污染”的问题。在访问分布完全无规律、甚至LRU和LFU都不好使的场景随机淘汰因为“一视同仁”反而可能给出比预期更好的表现。另外当缓存命中率不是核心KPI、而“实现简单可靠”才是重点时随机淘汰也是个可行的兜底方案。4. 策略选择指南与真实业务场景映射4.1 策略对比速查表不同策略在具体场景中的表现差异很大我整理了一个对比表面试时候可以直接用策略核心依据实现复杂度时间复杂度典型场景主要缺陷FIFO插入时间低O(1)批量数据加载访问均匀不感知访问频率冷热不分LRU最近访问时间中O(1)热点数据明显的业务偶发扫描会污染缓存LFU访问频率高O(1)访问频率稳定、冷热区分明显的场景频率污染实现复杂Random随机概率低O(1)访问完全无规律的场景淘汰不确定性高命中率波动大4.2 何时用LRU何时用LFULRU的核心优势在于它特别擅长应对“时间局部性”特征明显的场景也就是“最近被访问的数据很可能在短时间内再次被访问”。比如商品详情页缓存、登录会话信息、用户最近浏览过的内容这些数据天然就有时间局部性用LRU就非常合适。但LRU有一个很难避免的问题如果某次定时任务或者批量脚本一次性扫描了大量冷数据这些冷数据会被移到链表头部把原本的热点数据挤出去。等热点数据再次被访问时缓存已经把它们淘汰了命中率就会瞬间下降。这种现象叫“LRU污染”。LFU则更擅长应对“频率分布稳定”的场景也就是“访问次数多的数据未来大概率还会被多次访问”。比如CDN的内容缓存、某些统计分析场景里的高频key。LFU的劣势在于实现复杂度高以及那个天然的“频率污染”问题。如果业务对“短时突发热点”特别敏感比如大促时的秒杀页LFU反而可能反应迟钝因为它更看重历史频率而不是最近热度。4.3 Redis缓存淘汰策略对照聊到缓存策略绕不开Redis。很多面试者一说到Redis的缓存淘汰脑子里只有volatile-lru和allkeys-lru这两个。实际上Redis 4.0之后已经提供了非常丰富的策略选项我把它们整理成了一张表策略淘汰范围核心逻辑使用场景noeviction不淘汰内存满时直接返回错误数据必须全部保留禁止淘汰allkeys-lru全部key按LRU淘汰最久未访问的key数据无明显生命周期追求命中率volatile-lru设置了过期时间的key按LRU淘汰最久未访问的key只淘汰会过期的数据保证稳定性allkeys-random全部key随机淘汰任意key无热点数据纯随机分布volatile-random设置了过期时间的key随机淘汰有过期时间的数据随机淘汰volatile-ttl设置了过期时间的key淘汰剩余时间最少的key优先淘汰即将过期的数据Redis的实现细节也值得提一嘴它并没有做完整的LRU链表而是采用了一种近似LRU算法。为了保证性能Redis会从设置了过期时间的key中随机抽样每次抽出一部分然后从中挑出最久没被访问的那个进行淘汰。这个方案牺牲了有限的精确度换来了更好的性能。这其实给了我们一个工程启示当数据量足够大的时候不必追求完美策略近似策略往往性价比更高。你只要让淘汰逻辑在大多数情况下表现得“足够合理”就可以投入使用了。4.4 生产级缓存组件是怎么做的Caffeine的启示生产环境中你直接用的缓存组件底层已经做得非常成熟。以目前Java领域最流行的本地缓存Caffeine为例它的默认策略叫W-TinyLFU本质上是LFU的升级版。W-TinyLFU并没有简单地给每个key维护一个计数器。它用了布隆过滤器类似的概率计数结构来降低内存占用并通过“分段老化”机制来应对LFU的频率污染问题。这意味着在Caffeine里一个key即使曾经访问频率很高只要它长时间不再被访问它的历史频率也会逐步“衰退”不会永远霸占着缓存里的位置。作为对比你自己手写的LRU、LFU主要价值在于帮助理解策略的本质并不适合直接上生产环境。但如果你能从一个手写版本出发逐步演进成带TTL、带统计指标、带并发控制的组件那你的架构设计能力就已经达到一个比较高的水准了。面试时候能完整演出一遍这样的设计过程本身就是很强的加分项。4.5 我在真实项目中踩过的一个坑缓存策略切换引发的“雪崩”多年前我在一个网关项目里本地缓存策略最开始用的是LRU一切正常。后来有一位同事为了“优化命中率”把策略切换成了LFU。上线之后前半小时确实很稳但等到一个批处理任务开始疯狂读一批冷数据后事情就不对了——那批冷数据因为短时间访问频率很高把原本的热点接口参数全部从缓存里挤了出去。结果核心接口的响应时间从20毫秒飙到了2秒差点把下游数据库打挂。那次故障排查到最后才发现LFU的频率计数模型天然会放大“短时高频访问”的影响。而网关场景里真正核心的数据是那些长期稳定高频访问的key反而是那些“瞬时突刺”的数据恰恰不应该被当成热点。后来我们换回了LRU并且补了一个频率衰减的逻辑才彻底解决了问题。我讲这个案例是想提醒你策略的选择从来不是“越先进越好”。LFU在某些场景真的不如LRU甚至不如一个简单的FIFO。你必须在动手实现之前先想清楚你的业务数据模型到底是什么样的。5. 常见问题与排查技巧实录5.1 为什么我的缓存命中率一直很低排查命中率问题时第一件事不是去看缓存策略选得对不对而是先确认这个策略和数据访问特征是否匹配。如果你是热点数据非常集中的场景用了FIFO那命中率肯定上不去。换个LRU大概率立刻好转。第二个常见原因是容量设置太小了缓存还没积累够足够的热点数据就被新数据淘汰了。第三个原因可能是缓存key的设计有问题同一个逻辑数据因为参数拼接方式不同生成了大量“伪不同”的key导致同样一份数据被重复缓存、互相挤占。一个比较实用的排查方法是给缓存组件加一个统计面板记录put次数、get命中次数、淘汰次数、当前容量等指标。观察一段时间你就知道数据是怎么涌入、怎么被淘汰的然后根据自己的业务特征去调整策略。5.2 为什么缓存清除不干净总有内存占用这种情况通常是因为“淘汰器里的数据没有和存储容器同步删除”。比如你在remove的时候只删了map里的数据但频率表里或者顺序链表里的节点还在那这些残留数据就会一直占着内存。这种问题在你的缓存组件里特别容易发生因为你得同时维护两套数据结构任何一处漏删都会导致泄漏。解决方案是谨记“一个key的完整生命周期”原则put的时候同时写存储和索引get的时候同时更新存储和索引remove的时候同时清理存储和索引clear的时候所有结构一并清空。每当你新增一个辅助结构就必须把这四类操作全部过一遍。5.3 并发读写场景下缓存组件应该怎么做上面的代码为了演示方便用的都是synchronized。这在面试答题和单线程场景下没问题但真实生产环境里synchronized会导致所有读写请求串行化在高并发场景下性能会非常难看。如果你想优化并发性能有几个方向可以考虑用ConcurrentHashMap做存储容器把锁粒度从“整个缓存”降低到“单个key的链表”或者引入分段锁不同key的访问互不干扰或者干脆读写分离把淘汰决策做成异步的避免阻塞正常的读写流程。关于锁粒度我自己在实际设计中有一个比较推荐的折中方案用ConcurrentHashMap存数据用Striped Lock或者Striped64的计数机制来维护访问频率淘汰的时候再加全局锁。好处是读多写少的场景下get操作几乎不会被阻塞而put和淘汰本身就不频繁加锁也能接受。不过这里必须提醒一句并发编程的水很深特别是锁顺序、原子性、可见性这几个问题稍微设计不好就容易出死锁或者数据不一致。面试能把这个方案说清楚就够了真要是做生产级组件还是优先考虑CompletableFuture异步化或者自带的并发容器方案。5.4 缓存抖动频繁GC压力很大怎么办缓存组件频繁抖动很大概率是因为存取的数据量太大晋升到老年代的对象太多频繁触发Full GC。遇到这种情况建议先做两件事一是检查缓存的容量设置和业务模型的预估总数据量看是不是设置得过于激进了二是检查淘汰器里是否维护了过多的辅助结构LFU那种“每个频率一个LinkedHashSet”的做法在频率分布极其分散时会产生大量小集合对象每个集合都是独立的对象头内存开销很可观。如果你用的就是LFU可以试试把频率分桶改成“按区间划分”比如1次、2-5次、6-10次、10次以上这样桶的数量就是固定的能省下不少内存。虽然精度下降了但命中率的损失往往在可接受范围内。5.5 缓存组件扩容、淘汰、过期同时发生怎么办先说结论处理优先级应当是先处理过期数据再处理容量满触发的淘汰。因为过期的数据本来就是无效的优先清理它们不会对命中率有任何影响同时还能腾出空间给新数据。实现上可以这样设计put的逻辑先检查key是否已经存在且过期如果真的过期了直接清除旧值再插入新值然后检查容量是否已满满了才执行淘汰逻辑最后写入新值和相应的频率、时间戳信息。这个顺序如果反了先淘汰后清过期很可能出现一种尴尬局面明明有几个过期key占着空间你却没清它们反而把一个还有热度的key给淘汰了这会让命中率白白损失。5.6 最容易忽略的边界情况容量为0和key为null这两个边界情况虽然简单但在面试代码里特别容易踩。容量为0的缓存任何put操作都应该直接不做否则一插入就触发淘汰旧key还没放进去就被清了逻辑上会出问题。key为null的情况如果你用的是HashMap系列它本身不允许null key调用方一旦传入null就会在map查询阶段直接抛出异常。所以应该在接口层面就做好防御比如get传入null直接返回nullput传入null直接忽略。这些看似微不足道的边界情况恰恰是面试官判断你“有没有真实工程经验”的一个很重要的指标。毕竟生产环境里的输入从来都不会按你的预期来。6. 从手写缓存到框架设计一次面试题的完整演进6.1 自研缓存组件vs 直接用Caffeine各自的定位有同学可能会问既然已经有Caffeine、Guava Cache这么成熟的本地缓存组件了为什么还要自己手写一个是不是重复造轮子要分场景看。如果是在正式项目中我强烈建议直接用Caffeine它能帮你规避掉太多的并发和内存细节问题。但如果你想真正理解缓存背后的每一个细节想成为一个“架构师”而不是“API调用者”那我建议你在业余时间一定要手写一遍。而且自研组件在特定场景下也有它的价值。比如你的业务有非常特殊的淘汰需求像“按用户维度淘汰”“按权限等级淘汰”“按外部命令动态调整容量”等通用缓存组件往往没法优雅支持。这时候能从底层自研缓存的能力就很值钱了。6.2 如何扩展一个支持TTL的缓存组件如果你想在自己的缓存组件上加TTL核心思路是给每个缓存项追加一个expireTime字段并且在get的时候加一个判断如果当前时间大于expireTime就认为这个key已经过期。这里也有一个优化点过期key的清理最好是懒清理定期清理双管齐下。懒清理是get时发现过期顺手删掉定期清理是后台线程定时扫描把过期比例很高的那一批key统一清掉。你不一定需要扫描全部缓存只需要随机抽一批key检查过期比例。如果比例高就再多扫几轮如果比例低就说明你的懒清理已经做得足够好不必额外消耗资源。6.3 一个开放式TOCTOU问题手写缓存组件的思路完整闭环面试官如果给你一个完整的开放题“请设计一个可用的本地缓存组件”你应该怎么答我的建议是搭出一个有层次、有闭环的框架先说存储层用什么结构为什么再说淘汰层用什么策略为什么以及如何做到O(1)第三说过期管理TTL怎么存、怎么清第四说并发控制锁粒度怎么设计第五说统计监控怎么观测命中率、淘汰率、容量水位。把这五层全部串下来你不仅是在答题更是在展示架构思维。其中每个环节都有可以深挖的细节存储层可以聊哈希表扩容的代价、负载因子的选择淘汰层可以聊LRU和LFU的数据结构差异聊W-TinyLFU的工程优化思路过期管理可以聊惰性删除和定期删除的调度策略并发控制可以聊分段锁、ReadWriteLock、Striped Lock的取舍统计监控可以聊穿刺明率、淘汰数、平均过期时间等关键指标以及这些指标如何反哺容量配置的调优。你看一道“源码实现”的面试题最后展开出来的是一整套缓存系统的完整设计。这也就是为什么面试官特别喜欢问这道题的原因——它能筛选出真正具备系统设计能力的人而不是单纯的“API搬运工”。6.4 进阶思考缓存一致性、缓存穿透、缓存雪崩既然已经把缓存策略聊透了我顺手把几个关联概念也点一下因为它们在面试里经常连着一起考。缓存一致性说的是数据库和缓存之间如何保持同步。常见的方案是Cache-Aside也就是先更新数据库再删除缓存。这个顺序非常重要你如果先删缓存再更新数据库中间有个时间窗口别人可能读到旧数据。缓存穿透说的是查询一个根本不存在的数据缓存里没有数据库里也没有导致每个请求都打到数据库。解决思路是布隆过滤器拦截或者缓存空值并设一个较短的TTL。缓存雪崩说的是大量key集中在同一时间过期或者缓存节点挂了导致全部请求直达数据库。解决办法包括过期时间加随机值打散、多级缓存、热点数据永不过期等。这些内容虽然是缓存面试的常客但因为有太多资料在讲我不想在这里过多展开。我只是想传达一个观点如果你能把“缓存置换策略”这一件事理解到源码层面那么这些衍生问题的理解深度会完全不一样。因为你已经站在“设计者”的角度去看问题了而不是“使用者”的角度。7. 面试现场的高分表达策略7.1 从“背诵”到“讲解”讲清楚Why比What更重要很多候选人聊缓存策略的时候习惯性从“LRU是什么”开始介绍然后背出定义。这种答法的问题在于它只回答了“What”没有回答“Why”。面试官想听的是你为什么这么选。高分的表达方式是这样的先描述业务场景再引出问题和痛点然后说明设计目标最后落到实现。比如这样讲“我们这个业务里用户最近浏览的商品有极高的重复访问概率而且总量非常大我不可能全量缓存必须做淘汰。考虑到热点数据具有明显的时间局部性我选择了LRU。实现上用哈希表加双向链表保证读写和淘汰都是O(1)。”你看这段话里既没有干巴巴地背定义又能让面试官清晰get到你的决策链路。它展示的是一个架构师思考问题的方式从业务出发推导技术方案。7.2 主动暴露“权衡”思考展示架构级视野在讲完LRU的优势之后千万不要停在那里要主动补充一句“不过LRU也有它的缺陷比如批量扫描会污染缓存。反观LFU它对频率稳定型业务更友好但实现复杂度更高而且在短时突刺场景下反应反而迟钝。所以我最终选择LRU是因为我们业务的访问模式是时间局部性主导而不是频率主导。”这个方法叫做“主动暴露权衡”。面试官最怕听到那种“我的方案完美无缺”的候选人因为真实世界里没有这种方案。你主动指出方案的适用边界反而让面试官觉得你考虑问题全面有真实的工程项目经验做支撑。7.3 当面试官追问“能不能再优化”的时候在讲完基础实现之后大概率面试官会追加一句“如果线上QPS非常高你这个synchronized缓存还能扛得住吗”这时候千万别慌这是一个展示进阶能力的机会。我会这样答如果读多写少我会考虑用ReentrantReadWriteLock让读操作并行、写操作互斥如果并发度更高我会用ConcurrentHashMap做存储配合Striped Lock来降低锁粒度如果还有更高的扩展性要求我可以把淘汰策略做成异步的让读写线程只管数据存储由独立的消费者线程负责频率统计和淘汰执行这样读写链路上就没有任何锁了。这段回答展示了三个层次的能力能识别性能瓶颈、能给出量化优化方案、能抽象出“读多写少”“高并发写”等不同场景。相比单纯背诵一个现成实现这才能让面试官印象深刻。7.4 代码能力展示的小技巧必须有跑得通的测试这里也是我最想强调的一点面试手写代码不要求一字不差地背出源码但你的代码必须逻辑自洽。很多时候候选人写了一个LRU自己却没跑过代码里到处都是bug。面试官几眼看过去就发现这个候选人的代码是没有经过验证的。我建议你把这些实现全部下载到本地IDEA里跑一遍下面的测试逻辑容量设为3依次put进A、B、C然后get一次A再put D看A是否还在、B是否被淘汰。如果这个用例能通过说明你的LRU核心逻辑没问题。LFU就验证“先访问A三次、访问B两次、访问C一次容量满时淘汰C而不是A”。能现场写出通过验证的代码本身就是一种很强的信号它说明你不只是记忆代码而是真正理解了算法和数据结构的运行机理。8. 写在最后缓存策略的修炼路径这篇文章从代码层面带你走了一遍缓存置换策略的完整实现链路。回到开头那个面试题如果你能把这套内容讲清楚我估摸着已经超越了绝大多数候选人。但比面试更重要的是你通过这个“手写一遍”的过程真正建立了关于缓存技术的底层认知。这套能力不会只用在面试上。你日常写代码的时候遇到需要做本地缓存、需要设计淘汰机制、需要评估一个组件的内存开销时这些“手写一遍”带来的肌肉记忆都会帮你做出更合理的判断。等你设计过一个完整的缓存组件之后再回头看Redis的源码、Caffeine的源码你会觉得豁然开朗因为他们不过是在你已经掌握的地基上盖了一座更豪华的房子而已。缓存策略这条路入门容易精通难。你愿意花时间把它从源码层面啃下来这个动作本身就说明你有成为架构师的潜质。只要保持住这股钻研劲其他的都只是时间问题。 手写缓存置换策略：LRU、LFU、FIFO源码实现与工程实践
架构师面试里有个很经典的“送命题”让你讲讲缓存置换策略然后紧接着来一句“如果让你自己实现你是怎么设计的”。不少人在第一步还能侃侃而谈LRU、LFU的区别一旦要求落到源码层面瞬间就卡壳了。说白了面试官不是想听你背策略的定义而是想确认你有没有真正深入过底层实现有没有在工程层面思考过“数据结构和算法的取舍”这件事。这篇文章我要做的事非常明确从零开始手写一版带完整缓存置换策略的缓存组件代码用纯JDK实现不依赖任何第三方框架。你会看到LRU、LFU、FIFO、随机淘汰这几种策略的源码实现思路以及它们各自适用的业务场景。读完你能直接动手敲出一版可运行的代码面试时候再聊到缓存不再是背概念而是真的有货可以聊。1. 缓存组件设计的整体思路拆解1.1 为什么面试总爱问“手写缓存置换策略”先说一个我的观察。很多面试者会把“缓存”等同于Redis一聊就是Redis怎么怎么样。这种回答不能说错但它暴露了一个问题你只是在用工具并没有真正理解缓存的核心机制。面试官问“源码实现”本质上是想确认三件事第一你有没有透过Redis、Caffeine这些成熟组件去看过它们底层的设计逻辑。第二你清不清楚“缓存存储”和“缓存淘汰”其实是两层独立的东西存储解决的是“怎么放”淘汰解决的是“放不下怎么办”。第三当你面对一个“设计一个缓存组件”这种开放题时能不能快速拆解出关键模块给出合理的选型理由。我见过不少候选人能熟练背诵LRU、LFU的定义但问到底层用什么数据结构实现的时候就支支吾吾了。还有人会写“LRU就是最近最少使用”但你问他“为什么LinkedHashMap可以实现LRU”又答不上来。这就是典型的“知道概念没看过源码”。所以这篇文章我会刻意把重点放在“数据结构选型”和“源码落地”上。缓存相关的理论已经有很多文章讲过了真正稀缺的是那种能直接运行、能讲清楚每一步为什么这么写的代码。1.2 缓存的本质一个Map加一套淘汰机制剥离所有复杂的概念缓存组件最核心的就三块。存储容器不用多说就是那个“放数据的地方”。它是整个缓存的心脏所有的查询、插入、删除都要经过它。大多数缓存组件会用哈希表做存储因为哈希表能保证O(1)的读写性能。淘汰策略是“容量满了之后怎么办”的那套规则。它是缓存的灵魂决定了哪些数据应该被优先保留。淘汰器负责执行淘汰策略它需要实时跟踪每个key的访问情况、频率信息用来在容量满的时候“算账”看看谁该走。这三块之间的关系可以类比成一家餐厅的运作存储容器是餐桌客人来了有地方坐淘汰策略是餐厅的排位规则没位置的时候判断谁该被请走淘汰器是门口的那个服务员他对每位客人的“消费情况”了如指掌才能给出谁该走、谁该留的建议。控制器则是对外暴露的那层门面它统一处理get、put、remove这些操作并在这个过程中协调存储容器和淘汰器的关系。每次get的时候记录访问信息调整key的“热度”每次put的时候检查容量是否已满满了就触发淘汰每次remove的时候同步清理掉淘汰器里的访问记录防止数据残留。1.3 选型对比链表、哈希表、队列、堆各自适合谁既然要做源码级实现数据结构的选择就是第一道关卡。我直接给你一个对比表后面实现的时候你会反复用到这里的关键点数据结构核心特点适用场景复杂度哈希表HashMapO(1)的读写随机访问能力强所有缓存策略的底层存储O(1)双向链表LinkedList插入删除效率高但随机访问O(n)LRU、LFU中维护访问顺序O(1)增删O(n)查找队列QueueFIFO天然匹配先进先出语义FIFO淘汰策略O(1)入队出队小顶堆PriorityQueue能快速拿到最小值按频率排序的淘汰如LFU变种O(log n)调整堆哈希表双向链表组合既能O(1)查又能O(1)调整顺序工程级LRU、LFU标准解法O(1)这里我特别想展开说一句为什么LRU的标准解法是“哈希表双向链表”而不是单纯用一个哈希表。原因很简单单纯哈希表是无序的你无法知道哪个key是“最近最少使用”的。如果每次操作都去遍历哈希表找最小值复杂度就退化成O(n)容量一旦上去就废了。双向链表在这里的价值是维护“访问顺序”。每次访问一个key就把它移动到链表的头部那么链表尾部的自然就是“最久没被访问的”。哈希表负责存“key到链表节点的映射”这样在找某个key对应的节点时不用去链表里遍历直接O(1)拿到。这个设计思路就是LinkedHashMap底层的实现逻辑。所以面试时候你如果能把这段讲明白就已经超越80%的候选人了。2. 核心细节解析数据结构选型与失效策略2.1 双向链表节点缓存世界里最小的单元无论是LRU还是LFU双向链表节点都是最小的数据结构单元。先看一个最简单的节点定义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; } }每个节点里既存着key又存着value。有人可能会问为什么存value的时候还要单独存一个key这是因为当淘汰器要从链表中移除一个节点时它需要根据这个key去哈希表里做同步清理。如果节点里只存value不存key那到淘汰的时候你就没法反推出key哈希表里那条记录就成了永远清不掉的内存泄漏。这个细节特别重要。我在实际开发中见过有人把这个key省略掉结果到了线上排查内存占用的时候就傻眼了。内存泄漏这种东西平时不显山不露水一旦触发GC频繁排查起来极其痛苦。2.2 哈希表双向链表的联动LRU的物理基础现在我们假设缓存容量固定为3然后依次执行一系列put操作。当put(A)时A被放入哈希表同时被链接到链表头部。链表现在是A。继续put(B)、put(C)此时链表从头部到尾部是C、B、A哈希表里也存着这三个键的映射关系。现在缓存已经满了容量是3。接下来put(D)因为容量不够必须淘汰一个。按照LRU的规则链表尾部就是最久没被访问的于是淘汰A把D放到链表头部。整个过程哈希表负责O(1)定位到A对应的节点并删除链表负责O(1)在头部插入D、尾部移除A。两边配合完美实现O(1)的淘汰。如果此时你get(B)B被访问了要从链表里把B摘出来移动到头部。链表从C、B、A变成B、C、A。这个“摘出来、放到头部”的操作依赖双向链表的prev和next指针原因很简单你知道了B的prev是C、B的next是A直接让C.next A、A.prev C就完成了摘除操作。如果是单向链表你还得从头开始遍历找到B前面的节点复杂度就退化了。2.3 触发淘汰的时机put时引发的连锁反应很多人有个误解以为淘汰是“定期扫描”触发的其实绝大多数缓存组件都是“惰性触发”。所谓惰性就是只有在put新数据、且容量已满的时候才触发淘汰。这很像你手机里的照片满了只有在拍新照片的时候系统才提醒你清理空间而不是每时每刻都在后台整理相册。这种设计的好处很多。最大的好处是节省性能如果你做定时扫描就得额外维护一个后台线程还要处理并发问题。而惰性触发完全不需要这些它把淘汰的压力分摊到每次put操作上逻辑简单且没有额外开销。当然惰性触发也有它的代价就像Redis的过期清理其实也依赖于“惰性删除定期删除”的组合策略一样缓存系统中如果一个key在过期后一直没被访问它就会一直占用内存。这在某些场景下是可以接受的但在Cache-Aside这种模式里如果你对内存的敏感性很高就还需要引入额外的定期扫描机制来兜底。2.4 初始化容量与负载因子性能的第一道关卡写缓存组件的时候初始化容量的设置特别容易被人忽略。很多人直接new HashMap()就完事了这在数据量大的时候性能会非常难看。HashMap有个机制叫扩容。当元素个数达到threshold阈值等于容量乘以负载因子时HashMap会把自己的内部数组扩大一倍然后把原来的元素全部重新哈希一遍。这个过程极其耗时如果缓存组件频繁触发扩容每次扩容还会造成一次明显的延迟尖刺对要求低延迟的业务来说几乎是不可接受的。所以合理的做法是在初始化时就估算好容量尽量减少扩容次数。有个经典公式预估容量 / 负载因子 1。比如你预估最多放1万个数据默认负载因子是0.75那初始化容量就应该是10000 / 0.75 1约等于13334。这样就能做到几乎不触发扩容。这个公式背后其实还有一层考量预留一点冗余空间能让哈希分布更均匀减少冲突。哈希冲突多了链表会变长查询效率就从O(1)退化成O(n)那就得不偿失了。2.5 三种失效策略对比TTL、懒清理、定期清理大多数缓存组件真正落地的时候不会只用“容量满”这一个触发条件还会配合“过期时间”。常见的组合有三种TTL策略、懒清理策略、定期清理策略。TTL策略最好理解给每个key设置一个过期时间到了时间就直接失效。不过TTL有个坑就是key到了时间并不会自己消失还是在内存里躺着只是访问的时候会判断“你这个key是不是过期了”。所以TTL必须要跟懒清理搭配使用。懒清理是当get请求来的时候先检查key是否过期过期了就直接返回null同时删除这个key。这样虽然不额外占用后台线程但那些“过期了但一直没人访问”的key就成了漏网之鱼会一直占着内存。定期清理是额外起一个线程每隔一段时间扫描一部分key把过期的移除掉。注意是“一部分”不是全部。全量扫描太耗资源所以一般会分批执行。这种“懒清理定期清理”的组合其实就是Redis过期键删除策略的组合思路也是工程中比较稳妥的做法。3. 实操过程与核心环节实现手写LRU、FIFO、LFU缓存3.1 通用缓存接口与基础实现先定义一个通用的Cache接口方便后续扩展不同策略。接下来用一个抽象类收敛公共逻辑比如容量管理、数据统计这些。public interface CacheK, V { V get(K key); void put(K key, V value); void remove(K key); int size(); void clear(); }有了接口之后就是核心实现。我先从最简单、最容易理解的FIFO策略开始因为它最直观后面再讲LRU然后是难度最高的LFU。3.2 FIFO缓存源码队列与哈希表的经典组合FIFOFirst In First Out是最朴素的淘汰策略谁先进来谁先被淘汰。它不需要记录访问频率也不需要移动节点只需要维护一个先进先出的队列即可。public class FifoCacheK, V implements CacheK, V { private final MapK, V map new HashMap(); private final QueueK queue new LinkedList(); private final int capacity; public FifoCache(int capacity) { this.capacity capacity; } Override public synchronized V get(K key) { return map.get(key); } Override public synchronized void put(K key, V value) { if (map.containsKey(key)) { map.put(key, value); return; } if (map.size() capacity) { K oldestKey queue.poll(); if (oldestKey ! null) { map.remove(oldestKey); } } queue.offer(key); map.put(key, value); } Override public synchronized void remove(K key) { map.remove(key); queue.remove(key); } Override public synchronized int size() { return map.size(); } Override public synchronized void clear() { map.clear(); queue.clear(); } }这段代码里有个细节值得注意如果put一个已经存在的key我直接更新value并return不会重新入队。这是很关键的一步因为如果已经存在的key再次入队队列里会出现重复的key淘汰的时候就会误删一个实际上还“活着”的key。你可能已经发现了FIFO有个致命弱点它不感知访问频率。假设有一条缓存数据是热点数据每秒被访问一万次但另一条冷数据只是一次性地插入。FIFO在容量满的时候依然会把热点数据给淘汰掉因为它的判断依据是“进入时间”不是“使用频率”。这在大部分业务场景下是没法接受的。但FIFO并非一无是处。在数据访问模式相对均匀、或者你对缓存命中率的容忍度比较高的场景下FIFO因为实现简单、开销极小反而是个不错的选择。比如某些批量预热数据的场景数据是一次性加载的没有冷热之分FIFO就能满足需求。3.3 LRU缓存源码LinkedHashMap的优雅实现与手写双链表接下来是面试的重头戏LRU。先给出一版基于LinkedHashMap的实现。你只需要重写一个方法就能实现完整的LRU淘汰。这可能是JDK里最简单优雅的一段缓存代码。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; } }就这么简单。LinkedHashMap的第三个构造参数是accessOrder传true之后它就会在每次get的时候把被访问的Entry移动到链表尾部。而removeEldestEntry这个钩子方法会在每次put后检查是否需要移除链表头部那个最老的节点。这里“链表头部”对应的就是“最久未被访问”因为最新访问的都被移到了尾部。这段代码写起来容易但理解起来有一个难点为什么“最老的”在头部而不是尾部关键在于LinkedHashMap的内部实现默认是按照插入顺序维护的头部的Entry是最早插入的尾部是最晚插入的。开启了accessOrder之后它会在每次访问时把该Entry移到尾部所以头部的Entry就变成了“最久没被访问的”。容量满的时候removeEldestEntry返回trueLinkedHashMap就会把头部那个Entry删掉正好符合LRU的淘汰逻辑。不过面试如果只写这段有些面试官可能会觉得你是在“走捷径”。所以我还得给你一版手写双向链表的LRU实现。这不仅能展示你真正理解了底层原理也更接近真实项目里“自己设计一个缓存”的需求。public class LruCacheK, V implements CacheK, V { private final MapK, NodeK, V map; private final int capacity; private final NodeK, V head; private final NodeK, V tail; 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; } } public LruCache(int capacity) { this.capacity capacity; this.map new HashMap(capacity * 4 / 3 1); this.head new Node(null, null); this.tail new Node(null, null); head.next tail; tail.prev head; } Override public synchronized V get(K key) { NodeK, V node map.get(key); if (node null) { return null; } moveToHead(node); return node.value; } Override public synchronized void put(K key, V value) { NodeK, V node map.get(key); if (node ! null) { node.value value; moveToHead(node); return; } node new Node(key, value); map.put(key, node); addToHead(node); if (map.size() capacity) { NodeK, V last removeTail(); map.remove(last.key); } } Override public synchronized void remove(K key) { NodeK, V node map.remove(key); if (node ! null) { removeNode(node); } } Override public synchronized int size() { return map.size(); } Override public synchronized void clear() { map.clear(); head.next tail; tail.prev head; } 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; node.prev null; node.next null; } private void moveToHead(NodeK, V node) { removeNode(node); addToHead(node); } private NodeK, V removeTail() { NodeK, V node tail.prev; removeNode(node); return node; } }如果你要画一下这个双向链表的结构它大概是这样的head - A - B - C - tail。head和tail是哨兵节点它们不存储实际数据只是用来简化链表的边界操作。这样做的好处是无论链表里有几个节点对头尾的操作代码都是一样的不需要单独处理空链表的情况。头插和尾删的复杂度都是O(1)因为只需要调整前后节点的指针不需要遍历。哈希表负责O(1)定位双链表负责O(1)调整顺序两者配合就完成了一个时间复杂度全面O(1)的LRU。3.4 LFU缓存源码最复杂也最能拉开差距的实现LFULeast Frequently Used和LRU最大的区别是它看频率不看过期时间。LRU判断“谁最久没被用”LFU判断“谁用得最少”。这听起来更合理但实现起来难度上了一个台阶。朴素思路是给每个key维护一个计数器每次访问就加一。淘汰的时候遍历所有计数器找最小那个。这个思路能跑但有两个大问题第一每次淘汰都要全量遍历复杂度O(n)数据量一大就废了第二如果一个key在短时间内被疯狂访问它的计数器会飙到一个很高的值之后即使这个key再也不被访问也因为“历史频率太高”而永远不会被淘汰这被称为“频率污染”。工程上比较标准的LFU实现方案是用频率作为分桶把相同访问次数的key放在同一个双向链表里同时维护一个全局最小频率minFreq。这样淘汰的时候只需要从minFreq对应的桶里取链表尾部就能完成复杂度O(1)。这个思路的核心数据结构是三层嵌套外层Map存储“频率”映射到“该频率下的key列表”内层是每个频率对应的双向链表再加上存储key到“频率节点”映射的索引Map。public class LfuCacheK, V implements CacheK, V { private final MapK, V values new HashMap(); private final MapK, Integer counts new HashMap(); private final MapInteger, LinkedHashSetK frequencyMap new HashMap(); private final int capacity; private int minFreq; public LfuCache(int capacity) { this.capacity capacity; this.minFreq 0; } Override public synchronized V get(K key) { if (!values.containsKey(key)) { return null; } increaseFreq(key); return values.get(key); } Override public synchronized void put(K key, V value) { if (capacity 0) return; if (values.containsKey(key)) { values.put(key, value); increaseFreq(key); return; } if (values.size() capacity) { evict(); } values.put(key, value); counts.put(key, 1); frequencyMap.computeIfAbsent(1, k - new LinkedHashSet()).add(key); minFreq 1; } private void increaseFreq(K key) { int count counts.get(key); counts.put(key, count 1); frequencyMap.get(count).remove(key); if (frequencyMap.get(count).isEmpty()) { frequencyMap.remove(count); if (count minFreq) { minFreq; } } frequencyMap.computeIfAbsent(count 1, k - new LinkedHashSet()).add(key); } private void evict() { LinkedHashSetK keys frequencyMap.get(minFreq); K key keys.iterator().next(); keys.remove(key); if (keys.isEmpty()) { frequencyMap.remove(minFreq); } values.remove(key); counts.remove(key); } Override public synchronized void remove(K key) { values.remove(key); Integer count counts.remove(key); if (count ! null) { frequencyMap.get(count).remove(key); if (frequencyMap.get(count).isEmpty()) { frequencyMap.remove(count); if (count minFreq) { minFreq; } } } } Override public synchronized int size() { return values.size(); } Override public synchronized void clear() { values.clear(); counts.clear(); frequencyMap.clear(); minFreq 0; } }这段代码里的关键就是minFreq指针。当需要淘汰的时候minFreq指向的那个频率桶里装的就是“访问次数最少”的key们。淘汰时直接从这个桶里取最前面的就可以了。因为LinkedHashSet保证了插入顺序所以最早进入该频率的会先被淘汰。minFreq的更新逻辑也很巧妙当某个key从频率n升到n1时如果频率n变得空了而且n恰好等于minFreq说明“当前最少访问次数”的桶空了那就把minFreq加1。这样的话minFreq永远指向“实际上存在”的最小频率。这里有一个需要特别注意的坑如果直接new LinkedHashSet()而不指定初始容量每次扩容也会带来额外的开销虽然不像HashMap那么严重但也值得优化。LFU面临的典型问题是“频率污染”。那怎么解决呢工程上常见的做法是给频率加衰减机制比如定期把所有频率都除以2或者记录最近一次访问时间超过一定时间后把频率重置。这样那些“曾经很热、后来变冷”的key就不会永远占着位置不走了。3.5 Random Cache最简单但工程上也有用的策略很多人可能觉得随机淘汰太“没技术含量”实际上在分布式缓存系统中随机淘汰反而在某些场景下表现不错。它的实现比FIFO还简单只需要在容量满的时候从哈希表里随机挑一个key删掉。public class RandomCacheK, V implements CacheK, V { private final MapK, V map new HashMap(); private final int capacity; private final Random random new Random(); public RandomCache(int capacity) { this.capacity capacity; } Override public synchronized V get(K key) { return map.get(key); } Override public synchronized void put(K key, V value) { if (map.containsKey(key)) { map.put(key, value); return; } if (map.size() capacity) { int index random.nextInt(map.size()); K keyToRemove (K) map.keySet().toArray()[index]; map.remove(keyToRemove); } map.put(key, value); } Override public synchronized void remove(K key) { map.remove(key); } Override public synchronized int size() { return map.size(); } Override public synchronized void clear() { map.clear(); } }随机淘汰的工程价值有两个一是代码极简二是它没有“频率污染”的问题。在访问分布完全无规律、甚至LRU和LFU都不好使的场景随机淘汰因为“一视同仁”反而可能给出比预期更好的表现。另外当缓存命中率不是核心KPI、而“实现简单可靠”才是重点时随机淘汰也是个可行的兜底方案。4. 策略选择指南与真实业务场景映射4.1 策略对比速查表不同策略在具体场景中的表现差异很大我整理了一个对比表面试时候可以直接用策略核心依据实现复杂度时间复杂度典型场景主要缺陷FIFO插入时间低O(1)批量数据加载访问均匀不感知访问频率冷热不分LRU最近访问时间中O(1)热点数据明显的业务偶发扫描会污染缓存LFU访问频率高O(1)访问频率稳定、冷热区分明显的场景频率污染实现复杂Random随机概率低O(1)访问完全无规律的场景淘汰不确定性高命中率波动大4.2 何时用LRU何时用LFULRU的核心优势在于它特别擅长应对“时间局部性”特征明显的场景也就是“最近被访问的数据很可能在短时间内再次被访问”。比如商品详情页缓存、登录会话信息、用户最近浏览过的内容这些数据天然就有时间局部性用LRU就非常合适。但LRU有一个很难避免的问题如果某次定时任务或者批量脚本一次性扫描了大量冷数据这些冷数据会被移到链表头部把原本的热点数据挤出去。等热点数据再次被访问时缓存已经把它们淘汰了命中率就会瞬间下降。这种现象叫“LRU污染”。LFU则更擅长应对“频率分布稳定”的场景也就是“访问次数多的数据未来大概率还会被多次访问”。比如CDN的内容缓存、某些统计分析场景里的高频key。LFU的劣势在于实现复杂度高以及那个天然的“频率污染”问题。如果业务对“短时突发热点”特别敏感比如大促时的秒杀页LFU反而可能反应迟钝因为它更看重历史频率而不是最近热度。4.3 Redis缓存淘汰策略对照聊到缓存策略绕不开Redis。很多面试者一说到Redis的缓存淘汰脑子里只有volatile-lru和allkeys-lru这两个。实际上Redis 4.0之后已经提供了非常丰富的策略选项我把它们整理成了一张表策略淘汰范围核心逻辑使用场景noeviction不淘汰内存满时直接返回错误数据必须全部保留禁止淘汰allkeys-lru全部key按LRU淘汰最久未访问的key数据无明显生命周期追求命中率volatile-lru设置了过期时间的key按LRU淘汰最久未访问的key只淘汰会过期的数据保证稳定性allkeys-random全部key随机淘汰任意key无热点数据纯随机分布volatile-random设置了过期时间的key随机淘汰有过期时间的数据随机淘汰volatile-ttl设置了过期时间的key淘汰剩余时间最少的key优先淘汰即将过期的数据Redis的实现细节也值得提一嘴它并没有做完整的LRU链表而是采用了一种近似LRU算法。为了保证性能Redis会从设置了过期时间的key中随机抽样每次抽出一部分然后从中挑出最久没被访问的那个进行淘汰。这个方案牺牲了有限的精确度换来了更好的性能。这其实给了我们一个工程启示当数据量足够大的时候不必追求完美策略近似策略往往性价比更高。你只要让淘汰逻辑在大多数情况下表现得“足够合理”就可以投入使用了。4.4 生产级缓存组件是怎么做的Caffeine的启示生产环境中你直接用的缓存组件底层已经做得非常成熟。以目前Java领域最流行的本地缓存Caffeine为例它的默认策略叫W-TinyLFU本质上是LFU的升级版。W-TinyLFU并没有简单地给每个key维护一个计数器。它用了布隆过滤器类似的概率计数结构来降低内存占用并通过“分段老化”机制来应对LFU的频率污染问题。这意味着在Caffeine里一个key即使曾经访问频率很高只要它长时间不再被访问它的历史频率也会逐步“衰退”不会永远霸占着缓存里的位置。作为对比你自己手写的LRU、LFU主要价值在于帮助理解策略的本质并不适合直接上生产环境。但如果你能从一个手写版本出发逐步演进成带TTL、带统计指标、带并发控制的组件那你的架构设计能力就已经达到一个比较高的水准了。面试时候能完整演出一遍这样的设计过程本身就是很强的加分项。4.5 我在真实项目中踩过的一个坑缓存策略切换引发的“雪崩”多年前我在一个网关项目里本地缓存策略最开始用的是LRU一切正常。后来有一位同事为了“优化命中率”把策略切换成了LFU。上线之后前半小时确实很稳但等到一个批处理任务开始疯狂读一批冷数据后事情就不对了——那批冷数据因为短时间访问频率很高把原本的热点接口参数全部从缓存里挤了出去。结果核心接口的响应时间从20毫秒飙到了2秒差点把下游数据库打挂。那次故障排查到最后才发现LFU的频率计数模型天然会放大“短时高频访问”的影响。而网关场景里真正核心的数据是那些长期稳定高频访问的key反而是那些“瞬时突刺”的数据恰恰不应该被当成热点。后来我们换回了LRU并且补了一个频率衰减的逻辑才彻底解决了问题。我讲这个案例是想提醒你策略的选择从来不是“越先进越好”。LFU在某些场景真的不如LRU甚至不如一个简单的FIFO。你必须在动手实现之前先想清楚你的业务数据模型到底是什么样的。5. 常见问题与排查技巧实录5.1 为什么我的缓存命中率一直很低排查命中率问题时第一件事不是去看缓存策略选得对不对而是先确认这个策略和数据访问特征是否匹配。如果你是热点数据非常集中的场景用了FIFO那命中率肯定上不去。换个LRU大概率立刻好转。第二个常见原因是容量设置太小了缓存还没积累够足够的热点数据就被新数据淘汰了。第三个原因可能是缓存key的设计有问题同一个逻辑数据因为参数拼接方式不同生成了大量“伪不同”的key导致同样一份数据被重复缓存、互相挤占。一个比较实用的排查方法是给缓存组件加一个统计面板记录put次数、get命中次数、淘汰次数、当前容量等指标。观察一段时间你就知道数据是怎么涌入、怎么被淘汰的然后根据自己的业务特征去调整策略。5.2 为什么缓存清除不干净总有内存占用这种情况通常是因为“淘汰器里的数据没有和存储容器同步删除”。比如你在remove的时候只删了map里的数据但频率表里或者顺序链表里的节点还在那这些残留数据就会一直占着内存。这种问题在你的缓存组件里特别容易发生因为你得同时维护两套数据结构任何一处漏删都会导致泄漏。解决方案是谨记“一个key的完整生命周期”原则put的时候同时写存储和索引get的时候同时更新存储和索引remove的时候同时清理存储和索引clear的时候所有结构一并清空。每当你新增一个辅助结构就必须把这四类操作全部过一遍。5.3 并发读写场景下缓存组件应该怎么做上面的代码为了演示方便用的都是synchronized。这在面试答题和单线程场景下没问题但真实生产环境里synchronized会导致所有读写请求串行化在高并发场景下性能会非常难看。如果你想优化并发性能有几个方向可以考虑用ConcurrentHashMap做存储容器把锁粒度从“整个缓存”降低到“单个key的链表”或者引入分段锁不同key的访问互不干扰或者干脆读写分离把淘汰决策做成异步的避免阻塞正常的读写流程。关于锁粒度我自己在实际设计中有一个比较推荐的折中方案用ConcurrentHashMap存数据用Striped Lock或者Striped64的计数机制来维护访问频率淘汰的时候再加全局锁。好处是读多写少的场景下get操作几乎不会被阻塞而put和淘汰本身就不频繁加锁也能接受。不过这里必须提醒一句并发编程的水很深特别是锁顺序、原子性、可见性这几个问题稍微设计不好就容易出死锁或者数据不一致。面试能把这个方案说清楚就够了真要是做生产级组件还是优先考虑CompletableFuture异步化或者自带的并发容器方案。5.4 缓存抖动频繁GC压力很大怎么办缓存组件频繁抖动很大概率是因为存取的数据量太大晋升到老年代的对象太多频繁触发Full GC。遇到这种情况建议先做两件事一是检查缓存的容量设置和业务模型的预估总数据量看是不是设置得过于激进了二是检查淘汰器里是否维护了过多的辅助结构LFU那种“每个频率一个LinkedHashSet”的做法在频率分布极其分散时会产生大量小集合对象每个集合都是独立的对象头内存开销很可观。如果你用的就是LFU可以试试把频率分桶改成“按区间划分”比如1次、2-5次、6-10次、10次以上这样桶的数量就是固定的能省下不少内存。虽然精度下降了但命中率的损失往往在可接受范围内。5.5 缓存组件扩容、淘汰、过期同时发生怎么办先说结论处理优先级应当是先处理过期数据再处理容量满触发的淘汰。因为过期的数据本来就是无效的优先清理它们不会对命中率有任何影响同时还能腾出空间给新数据。实现上可以这样设计put的逻辑先检查key是否已经存在且过期如果真的过期了直接清除旧值再插入新值然后检查容量是否已满满了才执行淘汰逻辑最后写入新值和相应的频率、时间戳信息。这个顺序如果反了先淘汰后清过期很可能出现一种尴尬局面明明有几个过期key占着空间你却没清它们反而把一个还有热度的key给淘汰了这会让命中率白白损失。5.6 最容易忽略的边界情况容量为0和key为null这两个边界情况虽然简单但在面试代码里特别容易踩。容量为0的缓存任何put操作都应该直接不做否则一插入就触发淘汰旧key还没放进去就被清了逻辑上会出问题。key为null的情况如果你用的是HashMap系列它本身不允许null key调用方一旦传入null就会在map查询阶段直接抛出异常。所以应该在接口层面就做好防御比如get传入null直接返回nullput传入null直接忽略。这些看似微不足道的边界情况恰恰是面试官判断你“有没有真实工程经验”的一个很重要的指标。毕竟生产环境里的输入从来都不会按你的预期来。6. 从手写缓存到框架设计一次面试题的完整演进6.1 自研缓存组件vs 直接用Caffeine各自的定位有同学可能会问既然已经有Caffeine、Guava Cache这么成熟的本地缓存组件了为什么还要自己手写一个是不是重复造轮子要分场景看。如果是在正式项目中我强烈建议直接用Caffeine它能帮你规避掉太多的并发和内存细节问题。但如果你想真正理解缓存背后的每一个细节想成为一个“架构师”而不是“API调用者”那我建议你在业余时间一定要手写一遍。而且自研组件在特定场景下也有它的价值。比如你的业务有非常特殊的淘汰需求像“按用户维度淘汰”“按权限等级淘汰”“按外部命令动态调整容量”等通用缓存组件往往没法优雅支持。这时候能从底层自研缓存的能力就很值钱了。6.2 如何扩展一个支持TTL的缓存组件如果你想在自己的缓存组件上加TTL核心思路是给每个缓存项追加一个expireTime字段并且在get的时候加一个判断如果当前时间大于expireTime就认为这个key已经过期。这里也有一个优化点过期key的清理最好是懒清理定期清理双管齐下。懒清理是get时发现过期顺手删掉定期清理是后台线程定时扫描把过期比例很高的那一批key统一清掉。你不一定需要扫描全部缓存只需要随机抽一批key检查过期比例。如果比例高就再多扫几轮如果比例低就说明你的懒清理已经做得足够好不必额外消耗资源。6.3 一个开放式TOCTOU问题手写缓存组件的思路完整闭环面试官如果给你一个完整的开放题“请设计一个可用的本地缓存组件”你应该怎么答我的建议是搭出一个有层次、有闭环的框架先说存储层用什么结构为什么再说淘汰层用什么策略为什么以及如何做到O(1)第三说过期管理TTL怎么存、怎么清第四说并发控制锁粒度怎么设计第五说统计监控怎么观测命中率、淘汰率、容量水位。把这五层全部串下来你不仅是在答题更是在展示架构思维。其中每个环节都有可以深挖的细节存储层可以聊哈希表扩容的代价、负载因子的选择淘汰层可以聊LRU和LFU的数据结构差异聊W-TinyLFU的工程优化思路过期管理可以聊惰性删除和定期删除的调度策略并发控制可以聊分段锁、ReadWriteLock、Striped Lock的取舍统计监控可以聊穿刺明率、淘汰数、平均过期时间等关键指标以及这些指标如何反哺容量配置的调优。你看一道“源码实现”的面试题最后展开出来的是一整套缓存系统的完整设计。这也就是为什么面试官特别喜欢问这道题的原因——它能筛选出真正具备系统设计能力的人而不是单纯的“API搬运工”。6.4 进阶思考缓存一致性、缓存穿透、缓存雪崩既然已经把缓存策略聊透了我顺手把几个关联概念也点一下因为它们在面试里经常连着一起考。缓存一致性说的是数据库和缓存之间如何保持同步。常见的方案是Cache-Aside也就是先更新数据库再删除缓存。这个顺序非常重要你如果先删缓存再更新数据库中间有个时间窗口别人可能读到旧数据。缓存穿透说的是查询一个根本不存在的数据缓存里没有数据库里也没有导致每个请求都打到数据库。解决思路是布隆过滤器拦截或者缓存空值并设一个较短的TTL。缓存雪崩说的是大量key集中在同一时间过期或者缓存节点挂了导致全部请求直达数据库。解决办法包括过期时间加随机值打散、多级缓存、热点数据永不过期等。这些内容虽然是缓存面试的常客但因为有太多资料在讲我不想在这里过多展开。我只是想传达一个观点如果你能把“缓存置换策略”这一件事理解到源码层面那么这些衍生问题的理解深度会完全不一样。因为你已经站在“设计者”的角度去看问题了而不是“使用者”的角度。7. 面试现场的高分表达策略7.1 从“背诵”到“讲解”讲清楚Why比What更重要很多候选人聊缓存策略的时候习惯性从“LRU是什么”开始介绍然后背出定义。这种答法的问题在于它只回答了“What”没有回答“Why”。面试官想听的是你为什么这么选。高分的表达方式是这样的先描述业务场景再引出问题和痛点然后说明设计目标最后落到实现。比如这样讲“我们这个业务里用户最近浏览的商品有极高的重复访问概率而且总量非常大我不可能全量缓存必须做淘汰。考虑到热点数据具有明显的时间局部性我选择了LRU。实现上用哈希表加双向链表保证读写和淘汰都是O(1)。”你看这段话里既没有干巴巴地背定义又能让面试官清晰get到你的决策链路。它展示的是一个架构师思考问题的方式从业务出发推导技术方案。7.2 主动暴露“权衡”思考展示架构级视野在讲完LRU的优势之后千万不要停在那里要主动补充一句“不过LRU也有它的缺陷比如批量扫描会污染缓存。反观LFU它对频率稳定型业务更友好但实现复杂度更高而且在短时突刺场景下反应反而迟钝。所以我最终选择LRU是因为我们业务的访问模式是时间局部性主导而不是频率主导。”这个方法叫做“主动暴露权衡”。面试官最怕听到那种“我的方案完美无缺”的候选人因为真实世界里没有这种方案。你主动指出方案的适用边界反而让面试官觉得你考虑问题全面有真实的工程项目经验做支撑。7.3 当面试官追问“能不能再优化”的时候在讲完基础实现之后大概率面试官会追加一句“如果线上QPS非常高你这个synchronized缓存还能扛得住吗”这时候千万别慌这是一个展示进阶能力的机会。我会这样答如果读多写少我会考虑用ReentrantReadWriteLock让读操作并行、写操作互斥如果并发度更高我会用ConcurrentHashMap做存储配合Striped Lock来降低锁粒度如果还有更高的扩展性要求我可以把淘汰策略做成异步的让读写线程只管数据存储由独立的消费者线程负责频率统计和淘汰执行这样读写链路上就没有任何锁了。这段回答展示了三个层次的能力能识别性能瓶颈、能给出量化优化方案、能抽象出“读多写少”“高并发写”等不同场景。相比单纯背诵一个现成实现这才能让面试官印象深刻。7.4 代码能力展示的小技巧必须有跑得通的测试这里也是我最想强调的一点面试手写代码不要求一字不差地背出源码但你的代码必须逻辑自洽。很多时候候选人写了一个LRU自己却没跑过代码里到处都是bug。面试官几眼看过去就发现这个候选人的代码是没有经过验证的。我建议你把这些实现全部下载到本地IDEA里跑一遍下面的测试逻辑容量设为3依次put进A、B、C然后get一次A再put D看A是否还在、B是否被淘汰。如果这个用例能通过说明你的LRU核心逻辑没问题。LFU就验证“先访问A三次、访问B两次、访问C一次容量满时淘汰C而不是A”。能现场写出通过验证的代码本身就是一种很强的信号它说明你不只是记忆代码而是真正理解了算法和数据结构的运行机理。8. 写在最后缓存策略的修炼路径这篇文章从代码层面带你走了一遍缓存置换策略的完整实现链路。回到开头那个面试题如果你能把这套内容讲清楚我估摸着已经超越了绝大多数候选人。但比面试更重要的是你通过这个“手写一遍”的过程真正建立了关于缓存技术的底层认知。这套能力不会只用在面试上。你日常写代码的时候遇到需要做本地缓存、需要设计淘汰机制、需要评估一个组件的内存开销时这些“手写一遍”带来的肌肉记忆都会帮你做出更合理的判断。等你设计过一个完整的缓存组件之后再回头看Redis的源码、Caffeine的源码你会觉得豁然开朗因为他们不过是在你已经掌握的地基上盖了一座更豪华的房子而已。缓存策略这条路入门容易精通难。你愿意花时间把它从源码层面啃下来这个动作本身就说明你有成为架构师的潜质。只要保持住这股钻研劲其他的都只是时间问题。