知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 05 - 手写 LRU 缓存 > 导读:用一问一答的方式,把"手写一个 get/put 均为 O(1) 的 LRU 缓存"这道高频手写题从思路到两版实现、再到线程安全与生产选型完整讲透。适合准备 Java 后端面试、需要现场白板写代码的读者。 ## 一、先建立全局认知 ### Q:LRU 缓存这道题的面试原题是什么?它在考什么? A:面试官通常这样说: > "实现一个 LRU 缓存,要求 get 和 put 操作都是 O(1)。" LRU(Least Recently Used,最近最少使用)是一种淘汰策略:当缓存容量满了,淘汰掉最久没有被访问的那条数据。这道题考的不是背 API,而是三件事: 1. 你能否在"查找快"和"修改访问顺序快"这两个需求之间,正确组合出数据结构; 2. 你能否手写出边界正确、不出 bug 的链表代码(哨兵节点是加分项); 3. 你是否知道 JDK 已经提供了现成实现(`LinkedHashMap`),以及生产环境更该用什么(Caffeine)。 ### Q:为什么必须用 HashMap + 双向链表?单链表或数组不行吗? A:先把要满足的操作列出来,再倒推数据结构: ```text LRU(Least Recently Used):最近最少使用,淘汰最久没有被访问的数据 需要的操作: get(key):O(1) 查找 put(key, value):O(1) 插入,容量满时 O(1) 删除最久未使用的 数据结构选择: HashMap:O(1) 查找 双向链表:O(1) 移动节点到头部,O(1) 删除尾部节点 两者结合:HashMap 存 key → 链表节点,链表维护访问顺序 ``` 关键取舍在于: - 只用 HashMap:查得快,但无法知道"谁最久没被访问"。 - 只用链表:能维护顺序,但查找要 O(n)。 - 数组:查找需要 O(n),且中间删除要搬移元素,同样不满足 O(1)。 所以答案是"组合":HashMap 负责 O(1) 定位节点,双向链表负责 O(1) 调整顺序和淘汰尾部。之所以必须是**双向**链表,是因为要把任意一个中间节点移动到头部时,需要能拿到它的前驱节点;单链表只能从头遍历找前驱,退化成 O(n)。  [编辑 Excalidraw 源图](/images/java-interview-copy/concurrent/05-lru-cache-lru-cache-structure-diagram.excalidraw) ### Q:为什么需要哨兵节点(dummy head/tail)? A:哨兵节点(dummy node)是链表中不存真实数据、只用来占位的头尾节点,也叫哑节点。它的价值是消除边界判断: - 没有哨兵时,`addToHead` 要区分"链表是否为空",`removeTail` 也要判断"删的是不是最后一个",分支一多就容易写错。 - 有了哨兵,`head.next` 永远存在(最坏是 `tail`),`tail.prev` 也永远存在,`addToHead` 和 `removeTail` 的逻辑对空链表和非空链表完全一致,代码更简洁、更不容易出 bug。 ## 二、理解核心机制 ### Q:方案一——如何手写"双向链表 + HashMap"? A:完整实现如下。注意 `HashMap` 存的是 `key -> Node`,链表从 `head` 到 `tail` 的方向表示"最近使用 → 最久未使用": ```java public class LRUCache { private final int capacity; private final Map<Integer, Node> map = new HashMap<>(); // 哨兵节点(dummy),简化边界处理 private final Node head = new Node(0, 0); private final Node tail = new Node(0, 0); static class Node { int key, val; Node prev, next; Node(int key, int val) { this.key = key; this.val = val; } } public LRUCache(int capacity) { this.capacity = capacity; 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.val; } public void put(int key, int value) { Node node = map.get(key); if (node != null) { node.val = value; moveToHead(node); } else { Node newNode = new Node(key, value); map.put(key, newNode); addToHead(newNode); if (map.size() > capacity) { Node removed = removeTail(); // 删除最久未使用的 map.remove(removed.key); } } } 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; } } ``` **为什么这样写、代价是什么**: - `Node` 里同时保存 `key` 和 `val`,而不是只存 `val`。原因是淘汰尾部节点时,必须通过 `removed.key` 反查并删除 `map` 中的条目——如果 Node 不存 key,就还得遍历 map 找它。 - `moveToHead` 复用 `removeNode + addToHead`,逻辑清晰,但每次 get/put 都要做两次指针改写(常数级,仍是 O(1))。 - 靠哨兵节点规避了判空,代码行数不多,但指针赋值顺序敏感(比如 `addToHead` 里必须先接好 `head.next.prev`,再改 `head.next`),是白板最容易写错的地方。 - 时间复杂度:`get`/`put` 均为 O(1);空间复杂度 O(capacity)。 ### Q:方案二——`LinkedHashMap` 怎么做到"一行搞定"? A:JDK 的 `LinkedHashMap` 本身就是"HashMap + 双向链表",它内置了访问顺序维护和淘汰回调,所以只需继承并重写一个方法: ```java public class LRUCacheSimple extends LinkedHashMap<Integer, Integer> { private final int capacity; public LRUCacheSimple(int capacity) { // accessOrder=true:按访问顺序排序(最近访问的在最后) super(capacity, 0.75f, true); this.capacity = capacity; } public int get(int key) { return super.getOrDefault(key, -1); } public void put(int key, int value) { super.put(key, value); } @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { return size() > capacity; // 超过容量时删除最老的条目 } } ``` **取舍分析**: - 优点是代码量极小、久经生产验证、不易写错;缺点是你无法插入自定义逻辑(比如异步加载、命中率统计、过期时间)。 - 构造器三个参数分别是 `initialCapacity`(初始容量)、`loadFactor`(负载因子,0.75f 是 HashMap 的经典默认值)、`accessOrder`(是否按访问顺序排列)。只有 `accessOrder=true` 才是 LRU 语义,默认的 `false` 是插入顺序。 - 注意 `getOrDefault`:原题约定"查不到返回 -1",所以这里用 `getOrDefault` 包装而不是直接 `get`。 ### Q:`accessOrder` 和 `removeEldestEntry` 背后的原理是什么? A:把 `LinkedHashMap` 拆开看: ```text LinkedHashMap = HashMap + 双向链表 HashMap 存储 key-value,双向链表维护插入顺序或访问顺序 accessOrder=true 时: 每次 get/put 都会将该节点移到链表尾部 链表头部是最久未访问的(LRU 淘汰对象) 链表尾部是最近访问的 removeEldestEntry: 每次 put 后调用,返回 true 则删除链表头部(最老的)节点 ``` 也就是说,`LinkedHashMap` 已经把"移动节点到尾部"这件事做完了,你只需要在 `removeEldestEntry` 里回答"当前是否超容量"。它默认返回 `false`(永远不淘汰),所以必须重写才能得到容量受限的 LRU。 注意一个方向上的差异:手写方案里我把"最近使用"放在 `head` 侧,而 `LinkedHashMap` 把最近访问放在尾部(`tail`)。两种方向都正确,关键是"淘汰端"和"淘汰对象"必须对得上。 ## 三、放进真实场景 ### Q:多线程环境下怎么用这个 LRU 缓存? A:上面的两版实现都不是线程安全的。原文给出三种做法: ```java // 方案 1:Collections.synchronizedMap 包装 Map<Integer, Integer> lruCache = Collections.synchronizedMap( new LRUCacheSimple(100) ); // 方案 2:手写版本加 synchronized public class ThreadSafeLRU { private final LRUCache cache; public ThreadSafeLRU(int capacity) { this.cache = new LRUCache(capacity); } public synchronized int get(int key) { return cache.get(key); } public synchronized void put(int key, int value) { cache.put(key, value); } } // 方案 3:高并发场景用 Caffeine(生产推荐) // Caffeine 实现了 W-TinyLFU 算法,比 LRU 命中率更高 Cache<Integer, Integer> cache = Caffeine.newBuilder() .maximumSize(100) .expireAfterWrite(1, TimeUnit.HOURS) .build(); ``` **取舍分析**: - 方案 1、2 本质都是"一把全局大锁",实现简单但并发度低:所有读写串行化,高并发下会成为瓶颈。 - 方案 2 的 `get` 也加了 `synchronized`,这是必要的——因为 `get` 会修改链表顺序,是有副作用的"写"操作,不能只当读操作看待。 - 方案 3 的 Caffeine 内部采用了细粒度并发控制(分段 + 无锁读等手段,具体实现随版本演进,需结合版本确认),并且用 W-TinyLFU 替代纯 LRU,命中率通常更高,是生产环境的首选。 ### Q:LRU 和 LFU 的区别?哪个更好? A:LRU 淘汰最久未访问的,LFU 淘汰访问频率最低的。两者不是简单的好坏关系: - LFU 更能保留真正的热点数据,但实现复杂,且对新加入的数据不友好(新数据频率低,容易被误淘汰),存在"历史热点赖着不走"的问题。 - LRU 实现简单、对新数据友好,但在"偶发批量扫描"场景下容易被污染(一次性扫描会把真正的热点挤出去)。 - 实际中 Caffeine 使用 W-TinyLFU,结合了两者优点。 ### Q:生产上直接拿手写 LRU 当缓存可以吗? A:要谨慎。手写版通常只解决了"容量淘汰"这一件事,而生产级缓存往往还需要:过期时间(TTL)、异步刷新、统计埋点、并发控制、淘汰通知等。所以: - 单机、简单场景、可控并发:手写版或 `LinkedHashMap` 版够用,代码透明、可定制。 - 高并发、需要 TTL/统计:直接用 Caffeine(本地缓存)或 Redis(分布式缓存)。 - 面试回答时,先给出标准手写实现,再补一句"生产我会用 Caffeine/Redis",能体现工程判断力。 ## 四、总结与自测 ### Q:面试里怎么答这道题? A:建议分四步作答: 1. **先定位**:LRU = 最近最少使用,容量满时淘汰最久未访问的数据,get/put 均要求 O(1)。 2. **给数据结构**:HashMap 存 key→节点做 O(1) 查找,双向链表维护访问顺序做 O(1) 移动与淘汰;用哨兵节点简化边界。 3. **写实现**:给出"双向链表 + HashMap"完整代码,边写边说明 `put` 的三种分支(命中改值、未命中新增、超容量淘汰尾部)。 4. **做延伸**:主动补一句 `LinkedHashMap(accessOrder=true) + removeEldestEntry` 的简版写法,以及线程安全(包装/加锁)与生产选型(Caffeine 的 W-TinyLFU)。这样既展示了编码能力,也展示了知识面。 ### Q:这道题最容易踩的坑有哪些? A: - 用单链表 → 移动中间节点时找不到前驱,达不到 O(1)。 - `Node` 不存 `key` → 淘汰时无法从 map 中删除对应项。 - 忘记在 `get` 时 `moveToHead` → 退化成 FIFO,不是 LRU。 - 淘汰顺序搞反 → 该淘汰"最久未使用"的,却删了"最近使用"的。 - 误以为 `get` 是纯读操作 → 并发场景下给它漏加同步。 - 把 `accessOrder` 写成默认的 `false` → 得到的是插入顺序淘汰(FIFO),不是 LRU。 --- ## 自测 1. 不看代码,说出 LRU 为什么必须用"HashMap + 双向链表",以及每个操作的时间复杂度。 2. 用 `LinkedHashMap` 实现 LRU 时,`accessOrder` 和 `removeEldestEntry` 各自负责什么? 3. 如果把上面的 `LRUCache` 直接放到多线程环境,会出现什么问题?有哪三种解决办法,各自的代价是什么?
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入