02.10.1 LRU 与 LFU 缓存设计
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.10 设计类与手写题
覆盖范围
- 哈希表 + 双向链表的 LRU 完整 O(1) 实现
- LFU 频次桶与最小频率维护
- 并发安全的 LRU 改造思路
- Redis 近似 LRU 采样策略与精确 LRU 的对照
- 缓存淘汰策略选型与缓存穿透/雪崩/击穿
高频题速览
| 编号 | 题目 | 难度 | 频率 |
|---|---|---|---|
| 02.10.1-001 | 手写 LRU 缓存(哈希 + 双向链表) | 基础 | ★★★★★ |
| 02.10.1-002 | LFU 缓存 O(1) 实现(频次桶) | 高级 | ★★★★★ |
| 02.10.1-003 | LRU 如何改造为线程安全版本 | 进阶 | ★★★★ |
| 02.10.1-004 | Redis 近似 LRU 与精确 LRU 的差异 | 进阶 | ★★★★ |
| 02.10.1-005 | FIFO / LRU / LFU / ARC 怎么选 | 进阶 | ★★★★ |
| 02.10.1-006 | LFU 中最小频率为什么不会错删 | 高级 | ★★★ |
| 02.10.1-007 | 缓存穿透、雪崩、击穿与淘汰策略的关系 | 基础 | ★★★★★ |
| 02.10.1-008 | LRU 热点数据抖动问题如何缓解 | 高级 | ★★★ |
02.10.1-001 手写 LRU 缓存(哈希 + 双向链表)
频率 ★★★★★ | 难度 基础
一句话结论
哈希表存 key 到节点的映射,双向链表按访问时间排最近(头)到最久(尾);get 命中把节点移到头,put 命中更新移头、未命中插头并在超容量时删尾,两处同步;均摊 O(1)。
概念解释
- 节点必须同时存 key 和 value,淘汰尾节点时要拿 key 去哈希表删映射。
- 用哑头哑尾消除空指针判断,所有插入删除都按中间节点处理。
- 哈希负责 O(1) 按键定位,链表负责 O(1) 维护访问顺序,二者互补。
原理流程
- 初始化:
head.next = tail,tail.prev = head,map = {}。 - get:map 命中则 remove 节点 + addToHead,返回 value;未命中返回 -1。
- put:map 命中则更新 value + moveToHead;未命中新建节点 addToHead 并 map.put;随后若 size > cap,删
tail.prev并 map.remove。
代码 / 示例
class LRUCache {
static class Node {
int key, val; Node prev, next;
Node(int k, int v) { key = k; val = v; }
}
private final int cap;
private final Map<Integer, Node> map = new HashMap<>();
private final Node head = new Node(0, 0), tail = new Node(0, 0);
LRUCache(int cap) {
this.cap = cap;
head.next = tail; tail.prev = head;
}
public int get(int key) {
Node n = map.get(key);
if (n == null) return -1;
moveToHead(n);
return n.val;
}
public void put(int key, int value) {
Node n = map.get(key);
if (n != null) { n.val = value; moveToHead(n); return; }
Node fresh = new Node(key, value);
map.put(key, fresh); addToHead(fresh);
if (map.size() > cap) {
Node old = tail.prev;
remove(old);
map.remove(old.key);
}
}
private void addToHead(Node n) {
n.prev = head; n.next = head.next;
head.next.prev = n; head.next = n;
}
private void remove(Node n) {
n.prev.next = n.next; n.next.prev = n.prev;
}
private void moveToHead(Node n) { remove(n); addToHead(n); }
}
常见误区
- 误区:节点只存 val;正解:淘汰时要拿 key 删哈希,节点必须存 key。
- 误区:put 同键会插入第二个节点;正解:先查 map,命中走更新分支,不新增节点。
- 误区:淘汰时只删链表不删哈希;正解:两处同步删除,否则内存泄漏。
追问 / 延伸
- Q:为什么不用单链表? A:单链表删已知节点需遍历找前驱,O(n)。
- Q:容量为 0 怎么处理? A:题目一般保证 cap >= 1;若 cap=0,put 后立即淘汰。
02.10.1-002 LFU 缓存 O(1) 实现(频次桶)
频率 ★★★★★ | 难度 高级
一句话结论
维护三张表:key -> Node、freq -> 双向链表(同频率节点,按时间排)、minFreq;每次访问把节点从旧频率桶摘除、挂到 freq+1 桶,淘汰时从 minFreq 桶尾摘;所有操作 O(1)。
概念解释
- 每个节点记录 key、value、freq。
- 频率桶用双向链表,桶内按时间排序(新插头、旧留尾),同频率内再按 LRU 淘汰。
minFreq维护当前最小频率;新增节点 freq=1 时重置 minFreq=1;某桶删空时若它是 minFreq 则 minFreq++。
原理流程
- get:查 key,节点 freq++;从旧桶摘除(空桶且是 minFreq 则 minFreq++),挂到新 freq 桶头。
- put 命中:同 get,但额外更新 value。
- put 未命中:新建节点 freq=1,挂到 freq=1 桶头,minFreq=1;超容量时删 minFreq 桶尾,同步删 key 表。
代码 / 示例
class LFUCache {
static class Node {
int key, val, freq = 1; Node prev, next;
Node(int k, int v) { key = k; val = v; }
}
private final int cap;
private int minFreq;
private final Map<Integer, Node> keyMap = new HashMap<>();
private final Map<Integer, LinkedHashSet<Node>> freqMap = new HashMap<>();
LFUCache(int cap) { this.cap = cap; }
public int get(int key) {
Node n = keyMap.get(key);
if (n == null) return -1;
bump(n);
return n.val;
}
public void put(int key, int value) {
if (cap == 0) return;
Node n = keyMap.get(key);
if (n != null) { n.val = value; bump(n); return; }
if (keyMap.size() == cap) {
LinkedHashSet<Node> minSet = freqMap.get(minFreq);
Node victim = minSet.iterator().next(); // 桶尾最久
minSet.remove(victim);
keyMap.remove(victim.key);
}
Node fresh = new Node(key, value);
keyMap.put(key, fresh);
freqMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(fresh);
minFreq = 1;
}
private void bump(Node n) {
int f = n.freq;
LinkedHashSet<Node> old = freqMap.get(f);
old.remove(n);
if (old.isEmpty() && f == minFreq) minFreq = f + 1;
n.freq++;
freqMap.computeIfAbsent(n.freq, k -> new LinkedHashSet<>()).add(n);
}
}
常见误区
- 误区:用一个 PriorityQueue 按 freq 排;正解:每次访问 freq 变化都要堆调整,O(log n),不满足 O(1)。
- 误区:minFreq 删空时忘记 ++;正解:旧桶空且是 minFreq 时要推进 minFreq,否则下次淘汰找不到桶。
- 误区:桶内用普通 HashSet;正解:需要保留插入顺序(同频率按 LRU),用 LinkedHashSet。
追问 / 延伸
- Q:minFreq 会不会永远停在 1? A:只要 freq=1 桶被删空且有新节点 freq=2,minFreq 就推进。
- Q:空间复杂度? A:O(cap),节点与桶都是容量级别。
02.10.1-003 LRU 如何改造为线程安全版本
频率 ★★★★ | 难度 进阶
一句话结论
朴素版用一把 ReentrantLock 包住 get/put 即可线程安全但并发度低;进阶用 ConcurrentHashMap 存节点 + 分段锁或读写锁维护链表;生产环境直接用 Caffeine 或 LinkedHashMap 的同步包装。
概念解释
- 粒度:全局锁简单但 get 也串行;读写锁让读并发,但 get 命中要移头(写操作),不能纯读。
Collections.synchronizedMap(new LinkedHashMap(...))是最简单的同步包装,但所有方法同一把锁。- Caffeine 基于 W-TinyLFU 思想,结合了 LRU 与 LFU,且有高并发实现,生产环境首选。
原理流程
- 全局锁版:所有公开方法
synchronized或lock.lock()。 - ConcurrentHashMap 版:map 线程安全,但链表操作仍需锁;可用
ConcurrentLinkedDeque但失去 O(1) 摘除已知节点能力。 - 分段锁版:按 key 哈希分片,每片一把锁,降低争用。
代码 / 示例
class ThreadSafeLRU {
private final Object lock = new Object();
private final Map<Integer, Integer> map = new java.util.LinkedHashMap<>(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > cap;
}
};
private final int cap;
ThreadSafeLRU(int cap) { this.cap = cap; }
public int get(int k) { synchronized (lock) { Integer v = map.get(k); return v == null ? -1 : v; } }
public void put(int k, int v) { synchronized (lock) { map.put(k, v); } }
}
常见误区
- 误区:ConcurrentHashMap 就能让 LRU 线程安全;正解:map 线程安全不代表链表顺序操作线程安全,get/put 中的链表修改仍需同步。
- 误区:读写锁适合 LRU;正解:get 命中会 moveToHead(写链表),读也升级为写,读写锁收益有限。
追问 / 延伸
- Q:Caffeine 为什么快? A:基于 W-TinyLFU 命中率高,且用 CAS + 缓冲队列减少锁竞争,具体实现细节以官方文档为准。
- Q:分布式 LRU 怎么做? A:本地缓存 + 远程缓存(Redis)二级,本地 LRU 限容,远程集中存储。
02.10.1-004 Redis 近似 LRU 与精确 LRU 的差异
频率 ★★★★ | 难度 进阶
一句话结论
Redis 为了节省内存不维护真实双向链表,而是每个对象带一个 24 位时钟,淘汰时随机采样 N 个 key 淘汰最久的;样本越大越接近精确 LRU,默认样本数可配置。
概念解释
- 精确 LRU 需要双向链表,每个 key 额外存 prev/next 指针,内存开销大。
- 近似 LRU:每个对象记录
lru字段(时间戳秒级或毫秒级截断),淘汰时从候选集里挑 lru 最小的。 - Redis 默认
maxmemory-samples=5,即每次随机抽 5 个淘汰 1 个;样本越大越精确但 CPU 越高。
原理流程
- 访问 key 时更新对象 lru 字段为当前时间。
- 内存超限时,按淘汰策略(allkeys-lru / volatile-lru)随机采样 N 个 key。
- 在采样集合中挑 lru 最小的淘汰,重复直到低于阈值。
代码 / 示例
精确 LRU:每次淘汰 O(1) 删尾,需双向链表
近似 LRU:采样 N 个,O(N) 挑最久,无链表开销
N=5 :CPU 低,命中率比精确 LRU 略低
N=100 :接近精确 LRU,CPU 更高
常见误区
- 误区:Redis LRU 是精确 LRU;正解:是随机采样的近似 LRU,样本越大越准。
- 误区:采样越少越好;正解:样本少会导致冷数据长期滞留,命中率下降。
追问 / 延伸
- Q:Redis 还有哪些淘汰策略? A:noeviction、allkeys-lru、volatile-lru、allkeys-lfu、volatile-lfu、allkeys-random、volatile-ttl 等,具体以 Redis 版本为准。
- Q:LFU 模式怎么实现? A:对象 lru 字段拆成计数与时间衰减,具体以 Redis 官方实现为准。
02.10.1-005 FIFO / LRU / LFU / ARC 怎么选
频率 ★★★★ | 难度 进阶
一句话结论
FIFO 最简单但忽略访问频率;LRU 按时间淘汰,适合热点局部性明显的场景;LFU 按频率淘汰,适合长期热点但怕冷数据残留;ARC 自适应两者,在 LRU/LFU 间动态平衡分区。
概念解释
- FIFO:先进先出,不区分访问频率,实现最简单(队列即可)。
- LRU:最近最少使用,抗批量访问抖动能力一般。
- LFU:最不经常使用,频率计数,热点数据长期留存,但历史高频数据会污染。
- ARC:自适应替换缓存,维护 L1(近期)和 L2(频繁)两个分区,动态调整大小。
原理流程
- 访问模式均匀随机:四者命中率差不多,选 FIFO。
- 访问有时间局部性(最近访问的还会访问):LRU 最优。
- 访问有频率局部性(热点长期访问):LFU 最优。
- 访问模式在两种间切换不确定:ARC 自适应。
代码 / 图示
策略 时间开销 频率开销 内存开销 抗抖动
FIFO O(1) 不看 O(n) 差
LRU O(1) 不看 O(n) 中
LFU O(1) 维护 O(n) 好但冷数据滞留
ARC O(1) 维护 O(2n) 自适应
常见误区
- 误区:LFU 一定比 LRU 好;正解:LFU 对突发批量访问不敏感(频率增长慢),但冷数据一旦被高频访问过就长期滞留。
- 误区:ARC 就是 LRU+LFU;正解:ARC 是自适应分区,不是简单叠加。
追问 / 延伸
- Q:Java 里用什么? A:LinkedHashMap 可实现 LRU;Caffeine 用 W-TinyLFU,命中率接近 ARC。
- Q:缓存容量很大选什么? A:容量大时 LRU 通常够用,容量小且访问模式不均时考虑 LFU/ARC。
02.10.1-006 LFU 中最小频率为什么不会错删
频率 ★★★ | 难度 高级
一句话结论
minFreq 只在两个时机变化:新插入节点(freq=1)时设为 1;某频率桶删空且该桶等于 minFreq 时推进到 f+1;由于所有被访问节点 freq 都递增,minFreq 永远指向当前最久未被访问的频率。
概念解释
- 新节点 freq=1,所以 minFreq 一定 <= 1 时重置为 1。
- bump 节点时,旧桶非空则 minFreq 不变;旧桶空且是 minFreq 才推进。
- 淘汰只从 minFreq 桶尾摘,因为同频率内桶尾是最久未访问的。
原理流程
- 假设 minFreq=2,此时没有任何 freq=1 的节点存在。
- 访问某 freq=2 节点,它 bump 到 freq=3,若 freq=2 桶变空,则 minFreq=3。
- 新插入节点 freq=1,minFreq 立即重置为 1。
代码 / 图示
节点 freq 变化:1 -> 2 -> 3 -> ...
minFreq 始终是当前存在的最小 freq
新插入:minFreq = 1
旧桶删空且是 minFreq:minFreq++
常见误区
- 误区:每次 bump 都重新扫描所有桶找 min;正解:增量维护 minFreq,O(1)。
- 误区:淘汰时从全局 freq 最小且时间最久摘;正解:同频率桶内本身按时间排,桶尾即最久。
追问 / 延伸
- Q:minFreq 会不会超过实际最大 freq? A:不会,因为只有某桶删空才推进,且推进到 f+1 时该桶必然存在(刚 bump 过来的节点)。
- Q:频率计数需要衰减吗? A:基础 LFU 不衰减,长期运行会导致历史高频数据污染;生产版有衰减机制。
02.10.1-007 缓存穿透、雪崩、击穿与淘汰策略的关系
频率 ★★★★★ | 难度 基础
一句话结论
穿透是查不存在的 key(缓存层拦不住,打到 DB);雪崩是大量 key 同时过期(DB 瞬时压力);击穿是单个热点 key 过期瞬间大量请求打到 DB;淘汰策略本身不解决这三个问题,但过期时间设计和空值缓存可缓解。
概念解释
- 缓存穿透:key 不存在,每次都查 DB,需布隆过滤器或缓存空值。
- 缓存雪崩:大量 key 同时 TTL 到期,需过期时间加随机抖动。
- 缓存击穿:热点 key 到期,需互斥锁或逻辑过期。
- 淘汰策略(LRU/LFU)解决的是容量满时淘汰谁,不解决过期问题。
原理流程
- 穿透:在缓存前加布隆过滤器,不存在的 key 直接拒绝。
- 雪崩:TTL 加随机偏移(如 base ± 30s),避免同时失效。
- 击穿:热点 key 用互斥锁重建,或逻辑过期(异步更新)。
代码 / 图示
穿透:布隆过滤器 + 缓存空值(短 TTL)
雪崩:TTL 加随机抖动
击穿:互斥锁 setnx + 热点 key 不过期
淘汰:容量满时 LRU/LFU 选谁出
常见误区
- 误区:用 LRU 就能防穿透;正解:LRU 只在容量满时淘汰,不存在的 key 根本不会被缓存(或被缓存为空值)。
- 误区:淘汰策略和过期策略是一回事;正解:淘汰是容量触发,过期是 TTL 触发,两者独立。
追问 / 延伸
- Q:空值缓存 TTL 设多长? A:一般 30s~5min,太短频繁回源,太长影响真实数据更新。
- Q:布隆过滤器误判率? A:误判率随位数组大小和哈希函数数变化,不存在误判为存在,存在不会误判为不存在。
02.10.1-008 LRU 热点数据抖动问题如何缓解
频率 ★★★ | 难度 高级
一句话结论
LRU 对突发批量访问敏感:一次批量扫描会把热点挤到尾部;缓解方案是 LRU-K(记录最近 K 次访问)、2Q(双队列)、或直接换 LFU/W-TinyLFU。
概念解释
- LRU-K:记录每个 key 最近 K 次访问时间,只有当 K 次访问都发生在近期才认为是热点。
- 2Q:用两个队列,新进 key 先进 A1(FIFO),二次访问才进 Am(LRU),过滤一次性访问。
- W-TinyLFU:用频率计数器 + 窗口段,新数据先进窗口,达到频率门槛才进主缓存。
原理流程
- 批量扫描一次性访问大量 key,LRU 把它们都放头部,真热点被挤到尾部淘汰。
- LRU-2 只看最近 2 次访问间隔,一次性访问不进入主 LRU。
- W-TinyLFU 用 Count-Min Sketch 估计频率,频率高的才进主缓存。
代码 / 图示
问题:批量冷数据访问 -> 真热点被挤出去
LRU-2:最近2次访问都近 -> 热点
2Q:先 FIFO,二次访问才进 LRU
W-TinyLFU:频率计数 + 窗口
常见误区
- 误区:LRU 抗抖动;正解:LRU 只看最近一次,批量冷访问会污染。
- 误区:增大容量就能解决;正解:容量再大,批量扫描也会占满缓冲区。
追问 / 延伸
- Q:Java 生产用什么? A:Caffeine 的 W-TinyLFU,命中率在大多数场景优于传统 LRU。
- Q:LRU-K 的 K 怎么选? A:K=2 是常见选择,K 越大对短期突发越不敏感但反应越慢。
待整理清单
- [ ] Caffeine W-TinyLFU 详细实现原理
- [ ] 分布式缓存一致性哈希与 LRU 结合
- [ ] LFU 频率衰减机制