# 我是熊猫钓鱼，欢迎大家点赞关注！
![在这里插入图片描述](https://developer.qcloudimg.com/http-save/yehe-11543487/f18ae1045130a7610a786ce49dbc31d9.png)
> **摘要**：LRU 缓存是算法面试里排名第 2 的设计题，但它真正考的不是会不会写双向链表，而是你有没有把缓存放进并发环境里跑过。本文从手写 LRU 的三个考点讲起，重点剖析一个反直觉的结论——`get` 命中时其实在改写 6 处指针，所以必须加写锁而非读锁；随后给出保住读并发的分段方案、TTL 过期策略，以及 LFU 的 O(1) 论证，最后附上完整追问链与对撞测试结果。

**目录**

- [一、这题考的不是会不会写双向链表](#一这题考的不是会不会写双向链表)
- [二、手写部分就这些，下面是真正的面试](#二手写部分就这些下面是真正的面试)
- [三、想保住读并发，只有一条路：把锁拆细](#三想保住读并发只有一条路把锁拆细)
- [四、再追一步：加 TTL](#四再追一步加-ttl)
- [五、最后一问通常是 LFU，而它的 O(1) 有个不显然的论证](#五最后一问通常是-lfu而它的-o1-有个不显然的论证)
- [六、这题的完整追问链](#六这题的完整追问链)


上一篇写完 `无重复字符的最长子串`，我在结尾留了句话：下一道聊 LRU，面试官几乎一定会问「你的 `get` 加了什么锁」，而正确答案是写锁。

我知道这话听着像故弄玄虚——`get` 不是读吗，读不该加读锁吗。

不是故弄玄虚，是我自己踩过。而且这个坑有个很不好的性质：**它不会当场报错**。

先说清楚这题的分量。在我拉的那份面经聚合数据里，LRU 缓存出现 962 次，排全部算法题第 2，是前十名里唯一的设计题。第一名那道字符串题考的是「你会不会想到滑动窗口」，而这道题考的是「你有没有真的把缓存放进过并发环境里跑」。

差别就在这把锁上。

---

## 一、这题考的不是会不会写双向链表

题面谁都背得出：设计一个数据结构，`get` 和 `put` 都是 O(1)，容量满时淘汰最久未使用的键。

要 O(1)，只靠一种结构做不到。哈希表能 O(1) 定位，但不知道谁最旧；链表能维护新旧顺序，但定位要 O(n)。所以标准答案是两个结构合体：

- 哈希表存 `key → 链表节点`，负责一步找到节点
- 双向链表按访问新旧串起所有节点，负责 O(1) 摘除和插入

必须是**双向**链表。因为单链表摘除一个中间节点要先知道它的前驱，而找前驱就得从头遍历，O(1) 的前提当场破掉。这是第一个真正的考点。

第二个考点是哨兵节点。链表头和尾各放一个不存数据的空节点，`addFirst` 和 `remove` 就永远不用判空。没有哨兵，代码里会散落四五个 `if (x != null)`，写错一个就是 NPE。

第三个考点，也是最少人主动说的：**淘汰时机**。

```java
public void put(int key, int value) {
    Node n = map.get(key);
    if (n != null) { n.v = value; moveToHead(n); return; }
    n = new Node(key, value);
    map.put(key, n);
    addFirst(n);
    if (map.size() > cap) {          // 先插入，再判断是否超额
        Node victim = tail.prev;
        map.remove(victim.k);
        remove(victim);
    }
}
```

顺序是先插入、后淘汰，所以容量会瞬时到 `cap + 1`。这个瞬时值是安全的。反过来先淘汰再插入才危险：如果这次 `put` 的 key 已经在表里，你可能刚把它淘汰掉又插回去，等于白丢一次更新。

我见过有人在这一步把 `containsKey` 的分支和淘汰逻辑写反，代码看起来更"严谨"，实际是错的。

---

## 二、手写部分就这些，下面是真正的面试

把上面这段写完，面试官通常点点头，然后问那句要命的话：

> "如果这个缓存是多线程共享的，你怎么加锁？"

十个里有八个会答：`get` 加读锁，`put` 加写锁，用 `ReadWriteLock` 提高读并发。

听起来非常合理。合理到我自己第一次也这么答。

问题是它错了。

![lfig1-what-get-changes.png](https://developer.qcloudimg.com/http-save/yehe-11543487/7913e64412699ce2432b0c9b4dfdd9f8.png)


看图就明白了。一次 `get` 命中，链表要发生一件事：把被访问的节点搬到"最近使用"那一端。

这个搬运动作是两步。先从原位摘除，改写 2 处指针（原前驱的 `next`、原后继的 `prev`）；再挂到头部，改写 4 处（该节点的 `prev` 和 `next`、原首节点的 `prev`、哨兵的 `next`）。

**合计 6 处指针赋值。**

一次纯读操作，写了 6 个字段。

这不是我推演出来的，是跑出来的。下面这段实验可以直接复制运行，用 JDK 自带的 `LinkedHashMap` 验证同一件事：

```java
LinkedHashMap<Integer, Integer> m = new LinkedHashMap<Integer, Integer>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > 3;
    }
};
m.put(1, 10); m.put(2, 20); m.put(3, 30);
System.out.println("put 之后        : " + m.keySet());
m.get(1);
System.out.println("仅 get(1) 之后  : " + m.keySet());
m.get(99);
System.out.println("get(99) 未命中后: " + m.keySet());
```

实际输出：

```
put 1,2,3 后 keySet 顺序      : [1, 2, 3]
仅调用 get(1) 之后 keySet 顺序 : [2, 3, 1]   <== 顺序变了
get(99) 不存在键之后 keySet     : [2, 3, 1]   (未命中不会重排，size=3)
```

全程没有一次 `put`，只调了一个 `get`，`keySet` 的顺序就变了。这就是"读语义、写实现"的直接证据。

这就是 LRU 的本质特征：**读语义，写实现**。你调 `get` 的时候以为自己在读，其实你在改数据结构。

那么给 `get` 加读锁意味着什么？意味着允许 N 个线程同时执行这 6 处指针赋值。两个线程分别把不同节点往头部搬，指针互相覆盖，链表出现环或者断链。

最糟的是它不抛异常。`ConcurrentModificationException` 这类保护在自定义链表里根本不存在，链表结构坏掉之后程序照常运行，只是某些节点再也走不到了。表现出来就是：线上缓存过一阵子凭空少了几个 key，命中率莫名下降，日志里干干净净。

这种 bug 复现一次的成本，远高于你老老实实给 `get` 加写锁的性能损失。

![lfig2-lock-decision.png](https://developer.qcloudimg.com/http-save/yehe-11543487/ffbc0d661fde67d5027c163626224222.png)


一个例外值得知道，因为它能证明你真的理解了而不是背结论：`get` **未命中**时不需要写锁。没找到节点，就没有任何指针需要移动，结构不变。

但工程上我不会为它单独开一条读锁快路径。省下的是一次无竞争的写锁开销，那个开销非常小；换来的是两条代码路径、两倍的推理负担，以及一个随时可能被人改错的分支。

---

## 三、想保住读并发，只有一条路：把锁拆细

答到"必须写锁"只是及格。面试官接下来一定会问：那读并发不就没了？

正确方向不是把写锁换成读锁，而是**降低锁粒度**。最常用的是分段：

```java
public class ConcurrentLRUCache<K, V> {
    private final LinkedHashMap<K, V>[] buckets = new LinkedHashMap[16];
    private final ReadWriteLock[] locks = new ReadWriteLock[16];

    @SuppressWarnings("unchecked")
    public ConcurrentLRUCache(final int capPerSeg) {
        for (int i = 0; i < 16; i++) {
            buckets[i] = new LinkedHashMap<K, V>(16, 0.75f, true) {
                protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                    return size() > capPerSeg;
                }
            };
            locks[i] = new ReentrantReadWriteLock();
        }
    }

    private int idx(Object k) { return (k.hashCode() & 0x7FFFFFFF) & 15; }

    public V get(K k) {
        int i = idx(k);
        locks[i].writeLock().lock();        // 注意，这里是写锁
        try {
            return buckets[i].get(k);
        } finally {
            locks[i].writeLock().unlock();
        }
    }
}
```

这段代码有三个可以讲出来的点。

第一，`LinkedHashMap` 第三个构造参数 `accessOrder=true` 就是"按访问排序"，它替你实现了上面那 6 处指针操作。

第二，方向和我手写的版本是**反的**。我的实现把最近使用放链表头、淘汰尾部；`LinkedHashMap` 是最近使用放尾部、`removeEldestEntry` 收到的是头部那个最久未用的。两种都对，但你得知道自己在说哪一种——不然面试官问"你的淘汰候选在哪一端"，你会答反。

第三，`removeEldestEntry` 只在 `put` 之后被调用，`get` 不触发它。所以容量收缩永远发生在写入路径上，读路径不会意外淘汰数据。

这两点也能一起验证。接着上面的例子，此时 `keys=[2,3,1]`，最久未用的是 2（虽然 1 才是最先插入的）：

```
get(1) 之后，队头是 2，size=3  keys=[2, 3, 1]
put(4) 之后 keys=[3, 1, 4]  → 被淘汰的是 2（不是插入最早的 1），证明按访问序淘汰
再 get(77) 未命中，keys=[3, 1, 4] size=3  → get 不触发淘汰
```

被淘汰的是 2 而不是 1，说明排序依据确实是访问序而非插入序；而一次未命中的 `get` 之后 `size` 纹丝不动，说明淘汰只挂在写入路径上。

分段之后，两个访问不同段的线程互不干扰，读并发回来了，而每一段内部依然是写锁串行——正确性没有让步。

---

## 四、再追一步：加 TTL

这题问到锁还没完，常见的第三问是"缓存要支持过期怎么办"。

过期键什么时候删？答案有两层，正好对应 Redis 的两套策略。

**惰性删除**：读的时候才发现它过期了，顺手删掉返回未命中。实现最简单，代价是如果那个 key 之后再也没被访问过，它就永远占着内存。

**定期删除**：后台线程周期性抽样，扫出过期的删掉。为了不造成长时间停顿，每轮只处理限量样本，而不是全表扫描。

```java
/** 定期删除：每轮限量抽样，避免一次全表扫描造成长停顿 */
private synchronized void evictSome() {
    long now = System.currentTimeMillis();
    int scanned = 0;
    Iterator<Map.Entry<K, Entry<V>>> it = map.entrySet().iterator();
    while (it.hasNext() && scanned++ < 100) {
        if (it.next().getValue().expireAt <= now) it.remove();
    }
}
```

两种一起用。惰性保证热点 key 的过期能立刻生效，定期保证冷 key 不会永久占内存。

这里有个细节很加分：后台那个清理线程要设成守护线程。不设的话，你的缓存会拖住 JVM 不让它退出——单元测试跑完进程不结束，八成是这个原因。

---

## 五、最后一问通常是 LFU，而它的 O(1) 有个不显然的论证

「如果换成 LFU 呢？」

LFU 的难点是：淘汰时要找频次最小的键，而频次是分散的，怎么做到 O(1)？

答案是按频次分桶。每个频次一条双向链表，另用一个 `minFreq` 记住当前最低频次。淘汰时直接去 `minFreq` 那条链表的尾部取节点——尾部就是同频次里最久未使用的，所以 LFU 在平局时退化成了 LRU。

真正需要论证的是这一句：

```java
if (from.size == 0) {
    lists.remove(old);
    if (minFreq == old) minFreq++;     // 只在旧桶被清空时才 +1
}
```

为什么这里可以简单地 `+1` 而不是重新求最小值？

因为频次从 `old` 升到 `old+1`，只有两种情况。如果 `old` 桶里还有其他元素，最小频次没变，`minFreq` 不该动；如果 `old` 桶被清空了，那么比 `old` 小的桶一定非空（否则 `minFreq` 早就不是 `old` 了），要么 `minFreq` 保持不变，要么它正好就是 `old`，此时新最小值必然是 `old+1`——因为被晋升的那个元素刚刚落到那里。

这个论证是 LFU 这道题唯一的智力含量。代码抄得出，理由说不出，面试官一追问就露。

顺带一个真实工程细节：Redis 4.0 的 LFU 是**近似**的。计数器只有 4 bit，最大 255，到顶之后按概率递增；而且每次访问前会按"距上次访问的时间"做对数衰减。为什么必须衰减？因为不衰减的话，一个历史热点键的计数会永远压着新键，缓存彻底僵死。

再补一句：Redis 的 LRU 本身也是近似的，它抽样 `maxmemory-samples` 个键、淘汰其中最久未用的，而不是维护一条精确的全局链表。精确 LRU 在真实系统里太贵了。

---

## 六、这题的完整追问链

![lfig3-followup-chain.png](https://developer.qcloudimg.com/http-save/yehe-11543487/cef9a8578189aba8baa2933a926eda36.png)


| 追问 | 想确认什么 | 一句话答案 |
|---|---|---|
| 为什么必须是双向链表 | 是否理解 O(1) 的前提 | 单链表摘除中间节点要先找前驱，会退化成 O(n) |
| 淘汰和插入谁先做 | 有没有想过覆盖写的边界 | 先插入后淘汰；反了可能误删正在更新的 key |
| `get` 加什么锁 | 是否理解访问序的代价 | 写锁。命中即 6 处指针赋值，是结构修改 |
| 那读并发怎么办 | 会不会只答"加锁" | 不换锁类型，改锁粒度：分段 |
| 过期键什么时候清 | 有没有生产经验 | 惰性 + 定期抽样，两者配合 |
| LFU 怎么保持 O(1) | 能不能自己论证 | 频次分桶 + `minFreq`，清空时才 +1 |

写完还是不太放心，就把正文里的实现拉去做了对撞。做法和上一篇一样：拿一个笨到不可能错的参考实现当基准。

LRU 的参考实现用 `ArrayList` 存访问序，命中就 `remove` 再 `add(0, key)`，淘汰取列表末尾——每一步都是 O(n)，但正确性一眼可见。然后把正文那份 O(1) 的双结构实现丢进去，随机跑 3000 轮、每轮 120 次操作，容量和键空间每轮重新随机。

关键不是比对返回值，而是**每一步都比对内部状态**：从旧到新把两边完整序列化成 `key=value` 串对比。因为返回值对了不代表顺序对了，而 LRU 的全部语义就藏在顺序里。

```
操作数=360000，状态/返回值不一致=0
```

LFU 同样处理，参考实现按 `(freq, seq)` 双关键字线性选淘汰对象，O(1) 版本和它对撞：

```
LFU 操作数=200000，不一致=0
```

顺带把 LeetCode 460 的官方用例也跑了一遍，最后一个细节挺有意思：`put(2)` 之后被淘汰的是 3 而不是 1——因为 1 已经被访问过多次、频次升到 3，而 3 只有 2。频次优先，时间只用来打破平局。

---

**金句**：LRU 的 `get` 是一次伪装成读的写。你给它加什么锁，暴露的是你有没有想过"读取"这件事本身也要付结构代价。

---

下一篇想写排名第 4 的那道：`数组中的第 K 个最大元素`，出现 606 次。它看起来只有一道题，实际上面试官会用它连问三件完全不同的事——堆、快速选择、以及"如果这 10 亿个数在 100 台机器上"。第三问才是这题真正的分界线。



摘要：LRU 缓存是算法面试里排名第 2 的设计题，但它真正考的不是会不会写双向链表，而是你有没有把缓存放进并发环境里跑过。本文从手写 LRU 的三个考点讲起，重点剖析一个反直觉的结论——get 命中时其实在改写 6 处指针，所以必须加写锁而非读锁；随后给出保住读并发的分段方案、TTL 过期策略，以及 LFU 的 O(1) 论证，最后附上完整追问链与对撞测试结果。

面试出现 962 次的 LRU：get 加读锁就错了

程序员

算法

职业发展

编程语言

LRU缓存面试要点：get命中会修改6处指针，需加写锁而非读锁；通过分段锁提升并发；结合TTL惰性与定期删除；LFU采用频次分桶实现O(1)，附完整追问链与对撞测试验证正确性。

数据结构

单元测试

代码解释

Redis

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

面试出现 962 次的 LRU：get 加读锁就错了-腾讯云开发者社区-腾讯云

面试出现 962 次的 LRU：get 加读锁就错了

面试出现 962 次的 LRU：get 加读锁就错了

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐