LinkedHashMap与LRU实现

# 16.LinkedHashMap与LRU实现

# 目录介绍

1. 案例引入
2. 架构概览
3. 节点结构剖析
4. 三大钩子函数
5. 插入序模式
6. 访问序模式
7. 手撕 LRU 缓存
8. LRU 算法局限
9. Caffeine 设计思想
10. 综合案例串讲

# 1. 案例引入

# 1.1 一段反常的缓存

某社交 App 的"用户信息缓存"模块，一位资深同事写了这样一段"高效 LRU"：

public class UserCache {
    private static final int CAPACITY = 10000;
    
    private final Map<Long, User> cache = new LinkedHashMap<Long, User>(
        CAPACITY, 0.75f, true     // ★ 第三个参数 true = accessOrder
    ) {
        @Override
        protected boolean removeEldestEntry(Map.Entry<Long, User> eldest) {
            return size() > CAPACITY;
        }
    };
    
    public User get(Long userId) {
        return cache.get(userId);    // 期望：每次访问把节点提到链表尾
    }
    
    public void put(Long userId, User user) {
        cache.put(userId, user);     // 期望：超过 10000 自动驱逐最久未访问
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

代码看起来"完美"——LinkedHashMap 的 LRU 经典写法。但生产环境上线后，QA 跑了 3 天就反馈："列表页偶发显示错乱用户信息"。

排查后发现——多个用户线程同时 get 时，会出现 ConcurrentModificationException、NPE 甚至链表死循环。这位同事坚信"我只是在读，怎么会破坏链表"。

# 1.2 凌晨的内存崩盘

更扎心的事故在两周后——凌晨 2 点，某网关服务突然 OOM 崩盘。dump 显示：LinkedHashMap 实例占用了 12GB 老年代，节点数高达 5000 万。

翻代码发现，开发同学这样用：

// 用 LinkedHashMap 替换 HashMap，"反正性能差不多"
Map<String, Object> sessionAttrs = new LinkedHashMap<>();

1
2

但他没意识到——LinkedHashMap 的每个节点比 HashMap 节点多 16B（before/after 指针）——5000 万节点意味着多吃 800MB；加上链表的 GC 不友好特性（双向遍历让 G1 写屏障频繁触发），最终撑爆老年代。

事故复盘会上，三个灵魂质问让全员沉默：

追问 ①：LinkedHashMap 为什么不是线程安全的？仅仅是没加锁吗？
        get 操作（明明只是读）也会修改链表吗？
追问 ②：accessOrder=true 与 false 的差别仅仅是"遍历顺序"吗？
        底层链表结构有什么不同？
追问 ③：LinkedHashMap 的"双向链表 + Map"双血统，
        相比纯 HashMap 多付出多少内存代价？值得吗？
追问 ④：手撕 LRU 用 LinkedHashMap 和用"HashMap + 自建双向链表"
        到底哪个好？面试官真正想考的是什么？
追问 ⑤：为什么 Caffeine、Guava Cache 都不用 LinkedHashMap 做 LRU？
        LRU 算法本身有什么缺陷？

1
2
3
4
5
6
7
8
9
10

这一切，就是本篇要回答的核心。

# 1.3 我们要回答什么

第 22 篇要把"LinkedHashMap 与缓存淘汰算法"这件事讲透——从节点扩展到访问序、从手撕 LRU 到 Caffeine 的 W-TinyLFU。

带着这个目标，要回答 7 个核心问题：

① LinkedHashMap 节点比 HashMap 节点多哪些字段？多少字节？     → 第3章
② 三大钩子 afterNodeAccess/Insertion/Removal 谁触发什么？      → 第4章
③ accessOrder 模式下，get 操作如何修改链表？为什么不是线程安全？ → 第6章
④ removeEldestEntry 钩子的设计哲学：模板方法模式？             → 第7章
⑤ 手撕 LRU 用 LinkedHashMap vs 手写双向链表，哪个更好？        → 第7章
⑥ LRU 有哪些缺陷？什么是"缓存污染"？                           → 第8章
⑦ Caffeine 的 W-TinyLFU 凭什么击败 LRU？                       → 第9章

1
2
3
4
5
6
7

本篇路线：

节点结构 (第3章) ─── before/after 双指针扩展
    ↓
三大钩子 (第4章)         ←—— HashMap 父类的扩展点设计
    ↓
插入序模式 (第5章)        ←—— 默认行为，replace HashMap
访问序模式 (第6章)        ←—— LRU 的天然契合
    ↓
手撕 LRU (第7章)         ←—— 实战 + 并发改造
LRU 局限 (第8章)         ←—— 缓存污染、LFU、LRU-K
Caffeine (第9章)         ←—— W-TinyLFU 的工业实现
    ↓
综合案例串讲 (第10章)

1
2
3
4
5
6
7
8
9
10
11
12

# 2. 架构概览

# 2.1 双血统的混血儿

LinkedHashMap 的类继承关系——一图道尽设计精髓：

            ┌─────────────────────────────────┐
            │     AbstractMap<K,V>             │
            └────────────┬────────────────────┘
                         │
            ┌────────────▼────────────────────┐
            │     HashMap<K,V>                 │
            │     ─ Node<K,V>[] table          │
            │     ─ put / get / remove         │
            │     ─ resize / treeify           │
            │     ─ afterNodeXXX (空实现钩子)   │  ★ 父类预留扩展点
            └────────────┬────────────────────┘
                         │ extends
            ┌────────────▼────────────────────┐
            │   LinkedHashMap<K,V>             │
            │     ─ Entry<K,V> head/tail       │  ★ 维护双向链表
            │     ─ boolean accessOrder        │
            │     ─ override afterNodeXXX      │  ★ 实现钩子
            └─────────────────────────────────┘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LinkedHashMap = HashMap 的所有能力 + 双向链表的有序性。它的"双血统"体现在两个数据结构同步维护：

Hash 表：保证 O(1) 查找（继承自 HashMap）
双向链表：保证有序遍历（自己的扩展）

# 2.2 为什么这么切

疑惑：为什么不直接做"有序 HashMap"——比如往桶里塞排序逻辑？

论证——三种"有序 Map"实现路径对比：

路径	实现	查询	内存	复杂度
A：桶内排序	每个桶维护 TreeNode	O(log n)	高（红黑树）	复杂
B：全量排序	每次遍历前 sort	O(n log n)	低	简单
C：辅助链表	HashMap + 双向链表	O(1)	中（多 16B/节点）	中等

路径 C（LinkedHashMap 的选择）的优势：

查询仍是 O(1)——hash 表完全保留
链表只串联节点引用——不复制数据
顺序更新是 O(1)——双向链表插入/删除是常数操作

结论：LinkedHashMap 选"辅助链表"是用最少的额外结构（每节点 +16B）换取 O(1) 有序遍历——这是经典的"空间换时间 + 关注点分离"设计。它把"查找快"和"遍历有序"这两个本来冲突的目标，分配给两套独立的数据结构。

# 2.3 三种顺序模式

LinkedHashMap 通过构造参数 accessOrder 切换两种核心模式，加上"无序"共三种语义对比：

HashMap                LinkedHashMap (false)        LinkedHashMap (true)
─ 桶顺序 (rehash 后乱) ─ 插入序 (永不变)           ─ 访问序 (动态变)
─ 不可预测              ─ 配置一次永远不变           ─ 每次 get 都重排
─ 用途：通用            ─ 用途：可预测遍历            ─ 用途：LRU 缓存

1
2
3
4

关键观察：accessOrder = true 时，get 操作会修改链表——这是 §1.1 案例线程不安全的根因。

结论：LinkedHashMap 的"读写边界"被 accessOrder 重新定义——开 access 模式后，"读"和"写"已无明确分界。这条特性后续会引发并发雪崩（§6.3）和事故复盘（§10.1）。

# 3. 节点结构剖析

# 3.1 Entry 字段扩展

LinkedHashMap.Entry 继承自 HashMap.Node，多了两个引用字段：

// HashMap.Node (父类)
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;        // 桶内链表的下一个节点
    // ... 32B/节点（压缩指针）
}

// LinkedHashMap.Entry (子类)
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;   // ★ 全局双向链表的前后节点
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
    // ... 48B/节点（压缩指针）
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

关键观察：

next 是桶内单链表指针（解决 hash 冲突用）
before/after 是全局双向链表指针（维护遍历顺序用）
两套链表完全独立——一个节点同时挂在桶链上和全局链上

桶链与全局链的关系示意：
                    
桶 0:  Entry_A ──next─→ Entry_C ──next─→ NIL
桶 1:  Entry_B ──next─→ NIL
桶 2:  Entry_D ──next─→ NIL

全局链(按插入序 A→B→C→D)：
       head ─→ A ⇄ B ⇄ C ⇄ D ←─ tail
              before/after 指针
              
★ 同一个节点 Entry_A 同时被两套指针串联

1
2
3
4
5
6
7
8
9
10
11

# 3.2 链表头尾指针

LinkedHashMap 自身只多 3 个字段：

public class LinkedHashMap<K,V> extends HashMap<K,V> {
    transient LinkedHashMap.Entry<K,V> head;       // 链表头（最老）
    transient LinkedHashMap.Entry<K,V> tail;       // 链表尾（最新）
    final boolean accessOrder;                      // false=插入序, true=访问序
    // ...
}

1
2
3
4
5
6

链表的语义约定：

head ←─ 最久未访问 / 最早插入        最近访问 / 最新插入 ─→ tail

LRU 场景下：每次 get/put 把节点搬到 tail；驱逐时从 head 删除——这是 LRU 算法的物理实现（§6.3 详述）。

# 3.3 内存代价测算

每节点比 HashMap 多 16B（两个引用 + 对齐）。规模化代价：

节点数        HashMap 内存    LinkedHashMap 内存    溢价
───────────────────────────────────────────────────────
1 万         320 KB           480 KB                +50%
100 万       32 MB            48 MB                 +50%
1 亿         3.2 GB           4.8 GB                +50%

1
2
3
4
5

疑惑：50% 的固定溢价，到底值不值？

论证——三个判断标准：

是否需要有序遍历？需要——LinkedHashMap；不需要——HashMap
链表 GC 友好性：双向链表是"老年代里的指针密集对象"，G1 的 RememberedSet 需要记录大量跨代引用——LinkedHashMap 的 GC 暂停时间通常比 HashMap 长 20%~30%
缓存命中率：双向链表跨节点访问破坏 CPU 缓存预取——遍历性能比 HashMap 差 5%~10%

结论：LinkedHashMap 的 50% 溢价在"有序遍历"或"LRU"场景下值得；但被误用做"无序通用 Map"时，是纯粹的浪费。§1.2 那位同事用 LinkedHashMap 做 sessionAttrs 容器，多吃 800MB 内存——典型的**"用错容器导致的内存税"**。

# 4. 三大钩子函数

# 4.1 父类的钩子设计

打开 HashMap 源码，会发现三个看起来"莫名其妙"的空方法：

// HashMap 中的三个空钩子
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

1
2
3
4

它们在 HashMap 的 put/get/remove 关键位置被调用，但自身实现为空：

// HashMap.putVal (片段)
public V put(K key, V value) {
    // ... 找桶、找链表节点
    if (e != null) {  // 节点已存在
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);          // ★ 钩子 1：访问时回调
        return oldValue;
    }
    // ... 新增节点
    afterNodeInsertion(evict);       // ★ 钩子 2：插入时回调
    return null;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

这是经典的模板方法模式——HashMap 定义算法骨架，把"扩展点"留给子类。LinkedHashMap 重写这三个钩子来维护双向链表。

疑惑：为什么 HashMap 里要预留这种"专为 LinkedHashMap 设计的钩子"？是不是污染父类？

论证——这是 JDK 设计的一个有意权衡：

如果 LinkedHashMap 完全独立，要重写整个 put/get/remove——代码重复严重
如果 LinkedHashMap 完全继承而父类没钩子，就无法在合适时机维护链表
唯一的解：父类预留扩展点 + 子类实现——以"父类多 3 个空方法"的小代价换"子类几乎不重写父类逻辑"的大收益

结论：HashMap 的三个空钩子是面向扩展开放、面向修改关闭（OCP 原则）的实例化。这与第 17 篇 G1 GC 的 SATB 写屏障预留扩展点同源——留扩展点的代价远小于重写整个流程。

# 4.2 afterNodeAccess

触发时机：

get(key) 命中时
put(key, v) 时 key 已存在（更新场景）
replace(key, v) 命中时

LinkedHashMap 的实现（仅在 accessOrder=true 时生效）：

void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {       // ★ 只有访问序模式才动
        LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e;
        LinkedHashMap.Entry<K,V> b = p.before, a = p.after;
        // 1. 把 p 从原位置摘下
        p.after = null;
        if (b == null)  head = a;
        else            b.after = a;
        if (a != null)  a.before = b;
        else            last = b;
        // 2. 把 p 挂到链表尾
        if (last == null)  head = p;
        else { p.before = last; last.after = p; }
        tail = p;
        ++modCount;                                 // ★ 注意：modCount 增加
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

关键观察：

accessOrder=false 时空实现——插入序模式 get 不动链表
accessOrder=true 时 modCount++——这就是为什么 §1.1 多线程 get 会抛 ConcurrentModificationException
修改 6 个指针——p 的 before/after、邻居的 before/after、tail/head——完全不是原子操作，多线程并发会让链表错乱

结论：accessOrder=true 模式下，get 操作本质上是写操作——这就是 §1.1 案例线程不安全的根本原因。这条隐藏特性是 LinkedHashMap 最大的"陷阱"。

# 4.3 afterNodeInsertion

触发时机：每次 put 新增节点后（不是更新）

LinkedHashMap 的实现：

void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);   // 驱逐最老节点
    }
}

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;     // ★ 默认永不驱逐——LinkedHashMap 不会自动 LRU
}

1
2
3
4
5
6
7
8
9
10
11

关键观察：默认 removeEldestEntry 返回 false——所以一个未重写的 LinkedHashMap 不是 LRU 缓存，只是"有序的 HashMap"。要做 LRU，必须子类化并重写 removeEldestEntry（§7 详述）。

疑惑：为什么 JDK 不直接给一个"LRUMap"类？

论证：LRU 的"驱逐策略"千差万别——按数量、按大小、按时间、按引用计数……JDK 不能预设。它只提供"最老节点"的访问入口，把"是否驱逐"的决策权留给用户。这是机制与策略分离的经典案例（这条原则会在 §10.3 升华）。

# 4.4 afterNodeRemoval

触发时机：每次 remove 成功后

LinkedHashMap 的实现：

void afterNodeRemoval(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e;
    LinkedHashMap.Entry<K,V> b = p.before, a = p.after;
    p.before = p.after = null;        // 帮 GC（避免悬空引用）
    if (b == null)  head = a;
    else            b.after = a;
    if (a == null)  tail = b;
    else            a.before = b;
}

1
2
3
4
5
6
7
8
9

结论：三个钩子配合，LinkedHashMap 在不重写 HashMap 任何核心方法的前提下，完整接管了"双向链表的同步维护"——这是模板方法模式的教科书级实践。

# 5. 插入序模式

# 5.1 链表如何串起

new LinkedHashMap<>() 默认就是插入序模式（accessOrder=false）。每次新增节点都被追加到链表尾：

// LinkedHashMap.newNode (插入新节点时调用)
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<>(hash, key, value, e);
    linkNodeLast(p);                       // ★ 直接挂到尾
    return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)  head = p;
    else { p.before = last; last.after = p; }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

依次 put A、B、C、D 后的链表状态：

head ─→ A ⇄ B ⇄ C ⇄ D ←─ tail
        (插入序固定，永不变)

1
2

# 5.2 遍历顺序保证

LinkedHashMap 重写了 entrySet、keySet、values 的迭代器——全部基于双向链表遍历，不再走 HashMap 的桶遍历：

// LinkedHashIterator (片段)
abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next;
    
    LinkedHashIterator() {
        next = head;            // ★ 从 head 开始
    }
    
    final LinkedHashMap.Entry<K,V> nextNode() {
        LinkedHashMap.Entry<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        next = e.after;          // ★ 沿 after 指针前进
        return e;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

对比 HashMap 的迭代器——HashMap 是按桶下标 0→n-1 顺序遍历，与插入顺序无关；扩容（rehash）后顺序甚至会变。LinkedHashMap 通过完全独立的链表绕开了"桶顺序"。

结论：LinkedHashMap 的"遍历有序"与 hash 表的内部状态完全解耦——即使发生 resize、treeify，链表顺序也不变。这是它能保证"插入顺序永远稳定"的根本。

# 5.3 与 HashMap 对比

维度	HashMap	LinkedHashMap (insert)
put 性能	1.0x	0.95x（多 4 条指针操作）
get 性能	1.0x	1.0x（不动链表）
remove 性能	1.0x	0.95x（多 4 条指针操作）
iterator 性能	1.0x	1.5x（链表对缓存友好的连续访问）
内存	1.0x	1.5x（每节点多 16B）
顺序保证	无	插入序

反直觉的发现：LinkedHashMap 的迭代比 HashMap 快！原因——HashMap 遍历要扫整个 table 数组（含大量空桶），LinkedHashMap 只需沿链表走 n 步。

结论：如果你需要频繁遍历，LinkedHashMap 反而比 HashMap 快——这是它最被低估的优势。

# 6. 访问序模式

# 6.1 accessOrder 开关

要启用访问序，必须用三参构造器：

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;     // ★ true 才启用
}

1
2
3
4

注意：accessOrder 是 final 字段，构造后不可修改——LinkedHashMap 在创建时就锁定了模式。

# 6.2 节点搬移源码

回看 §4.2 的 afterNodeAccess——访问序模式下，每次 get 把节点从原位置摘下，挂到 tail：

get(B) 前：
head ─→ A ⇄ B ⇄ C ⇄ D ←─ tail

get(B) 后：
head ─→ A ⇄ C ⇄ D ⇄ B ←─ tail
              ↑↑↑↑↑↑↑↑
              B 被搬到尾

1
2
3
4
5
6
7

6 个指针的修改步骤：

1. p.before.after = p.after        (A.after = C)
2. p.after.before = p.before       (C.before = A)
3. tail.after = p                  (D.after = B)
4. p.before = tail                 (B.before = D)
5. p.after = null                  (B.after = null)
6. tail = p                        (tail = B)

1
2
3
4
5
6

疑惑：6 步指针操作，并发场景会出什么问题？

论证——两个线程同时 get 不同节点：

线程 1: get(B)                        线程 2: get(C)
  step 1: B.before.after = B.after      step 1: C.before.after = C.after
  step 2: B.after.before = B.before     step 2: C.after.before = C.before
                                        ⚠ 此时 B 还未完全脱链，
                                          C.before 可能指向半摘链状态的 B
  ...
  
最终结果：链表指针错乱——可能成环（双向链表死循环）
       或断链（节点丢失）
       或指向已 GC 的节点（NPE）

1
2
3
4
5
6
7
8
9
10

结论：accessOrder=true 模式下的 get 是多步非原子操作——必须用 Collections.synchronizedMap 或外部锁保护。§1.1 案例的本质就是把"读"当成"读"，但其实它是"写"。

# 6.3 LRU 的天然契合

链表头尾正好对应 LRU 的两个语义：

head ←──────────────── 最久未访问 = LRU 驱逐目标
                       
tail ←──────────────── 最近访问 = 热点数据

1
2
3

LRU 算法的两个核心操作：

访问（put/get）：搬到 tail——afterNodeAccess 自动完成
驱逐：删 head——afterNodeInsertion 调用 removeEldestEntry 决定

结论：LinkedHashMap 的双向链表 + accessOrder + removeEldestEntry，三者组合就是 LRU 的天然实现——这是 LinkedHashMap 设计的"杀手级用例"。下一章我们手撕 LRU。

# 7. 手撕 LRU 缓存

# 7.1 三步搭建框架

用 LinkedHashMap 实现 LRU 缓存只需 3 步：

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);    // ★ 步骤 1：开启 accessOrder
        this.capacity = capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;        // ★ 步骤 2：定义驱逐条件
    }
    
    // ★ 步骤 3：直接用即可，put/get 自动维护 LRU 顺序
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3 行核心代码——这是 LinkedHashMap 真正的高光时刻。

# 7.2 removeEldestEntry

疑惑：为什么 removeEldestEntry 要返回 boolean，而不是直接驱逐？

论证——boolean 返回值给了用户完整的策略控制：

// 策略 1：按数量驱逐（最常见）
return size() > capacity;

// 策略 2：按总大小驱逐
return totalBytes > maxBytes;

// 策略 3：按时间驱逐（驱逐 30 分钟未访问的）
return eldest.getValue().lastAccessTime < System.currentTimeMillis() - 30*60*1000;

// 策略 4：永不驱逐（默认）
return false;

// 策略 5：组合策略
return size() > capacity || (eldest.getValue().expireTime < now);

1
2
3
4
5
6
7
8
9
10
11
12
13
14

结论：removeEldestEntry 是策略模式的钩子——把"决策"交给用户，"执行"留在框架。这与 §4.3 的"机制与策略分离"完美呼应。

# 7.3 完整可运行代码

带统计的生产级 LRU 实现：

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.atomic.LongAdder;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    private final LongAdder hitCount  = new LongAdder();
    private final LongAdder missCount = new LongAdder();
    private final LongAdder evictCount = new LongAdder();
    
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    
    @Override
    public V get(Object key) {
        V v = super.get(key);
        if (v != null)  hitCount.increment();
        else            missCount.increment();
        return v;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        boolean shouldEvict = size() > capacity;
        if (shouldEvict)  evictCount.increment();
        return shouldEvict;
    }
    
    public double hitRate() {
        long h = hitCount.sum(), m = missCount.sum();
        return h + m == 0 ? 0.0 : (double) h / (h + m);
    }
    
    public long evictedCount() { return evictCount.sum(); }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

使用示例：

LRUCache<Long, User> cache = new LRUCache<>(1000);
cache.put(1L, new User("Alice"));
cache.get(1L);                          // hit
System.out.println(cache.hitRate());    // 命中率统计

1
2
3
4

注意：这个实现仍然不是线程安全的——下一节解决。

# 7.4 并发安全改造

回到 §1.1 的事故——多线程 get 导致链表错乱。三种修复方案：

方案 A：粗粒度锁（最简单）：

Map<Long, User> cache = Collections.synchronizedMap(new LRUCache<>(1000));

代价：所有读写串行化——千线程下吞吐崩塌。

方案 B：读写锁：

private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();

public V get(K key) {
    lock.writeLock().lock();             // ★ 读也要写锁——因为 accessOrder 模式下 get 改链表
    try { return cache.get(key); }
    finally { lock.writeLock().unlock(); }
}

1
2
3
4
5
6
7

反直觉的点：accessOrder 模式下读锁不够用，必须用写锁——这是 LinkedHashMap LRU 的硬伤。

方案 C：直接换 ConcurrentLinkedHashMap 或 Caffeine：

// Caffeine 的等价实现
Cache<Long, User> cache = Caffeine.newBuilder()
    .maximumSize(1000)
    .build();

1
2
3
4

Caffeine 内部用了完全不同的算法（W-TinyLFU + 异步驱逐），无锁高并发——这就引出了 §9 的内容。

结论：LinkedHashMap 做高并发 LRU 是"功能可行但性能不可用"。生产环境中永远应该选 Caffeine——LinkedHashMap 的价值在于"教学和原型"，不在于"扛流量"。

# 8. LRU 算法局限

# 8.1 缓存污染问题

LRU 的致命缺陷——缓存污染：

场景：电商首页，热门商品 100 个，被高频访问
      凌晨爬虫扫描 1 万个冷门商品
      
LRU 行为：
  T0: 缓存 = {热门 100 个}    命中率 99%
  T1: 爬虫扫描开始，1 万个冷门商品依次访问
  T2: 冷门商品挤掉所有热门商品
  T3: 缓存 = {冷门 1000 个}    命中率 1%
  T4: 早高峰流量来袭——缓存全 miss，DB 被打挂

1
2
3
4
5
6
7
8
9

根本原因：LRU 假设"最近访问的就是最热的"——但冷数据的一次性访问会冲掉真正的热数据。这种现象在搜索引擎、推荐系统、CDN 边缘节点都极常见。

# 8.2 LFU 的尝试

LFU（Least Frequently Used） 试图修正——按"访问频次"而非"访问时间"驱逐：

LRU：驱逐"最久未访问"
LFU：驱逐"访问次数最少"

1
2

LFU 在 §1.1 场景中的表现：

热门商品被访问数千次——计数器很大
冷门商品被访问 1 次——计数器很小
驱逐时优先淘汰冷门商品——热数据保留 ✓

但 LFU 也有缺陷：

LFU 的两大硬伤：

频次老化：上周很热的商品频次累积到 100 万，本周虽然没人访问，但永远驱逐不掉
元数据成本：每个节点要维护频次计数器，用最小堆/双向链表组织——比 LRU 多吃 30% 内存

# 8.3 LRU-K 与 2Q

工业界两种折中方案：

LRU-K：要求"被访问 K 次以上"才进入主缓存：

访问历史队列 (FIFO)        主缓存 (LRU)
[只访问过 1 次的 key]  ──→  [访问过 ≥ K 次的 key]
                        K=2 是最常见配置 (LRU-2)

1
2
3

爬虫的一次性访问会停留在"历史队列"，不污染主缓存。

2Q (Two Queues)：LRU-K 的优化版，用两个队列：

A1in (FIFO 短队列):    新数据进入
A1out (Ghost 队列):    A1in 满时被踢出的 key（仅记 key 不存数据）
Am (LRU 主队列):       从 A1out "重新被访问"才进入

1
2
3

结论：LRU-K 和 2Q 都是用"访问历史"过滤一次性数据——这是 Caffeine 算法的思想雏形。但它们仍然不够好——没有考虑"频次衰减"和"全局准入"——这才是 W-TinyLFU 的突破点。

# 9. Caffeine 设计思想

# 9.1 W-TinyLFU 算法

Caffeine 是当代 Java 缓存的事实标准（Spring Cache 默认实现）。其核心算法 W-TinyLFU = Window LRU + TinyLFU：

┌─────────────────────────────────────────────────────────┐
│           入口 (Window LRU - 占总容量 1%)                │
│           新数据先进这里，给"短期热度"机会                 │
└────────────────────┬────────────────────────────────────┘
                     │ Window 满时，候选驱逐
                     ↓
┌─────────────────────────────────────────────────────────┐
│        TinyLFU Filter (准入控制器)                       │
│        新候选 vs 主缓存待驱逐者，按"频次"决斗             │
│        频次高的胜出进入主缓存                             │
└────────────────────┬────────────────────────────────────┘
                     │
                     ↓
┌─────────────────────────────────────────────────────────┐
│        Main Cache (SLRU - 占总容量 99%)                  │
│        分为 Probation (20%) + Protected (80%)            │
│        命中升级到 Protected，再命中保持                    │
└─────────────────────────────────────────────────────────┘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

关键设计：

Window 给新数据 1% 的"试用期"——避免一击即驱逐
TinyLFU 用频次"决斗"——挡住爬虫的一次性数据
Main Cache 分两层——刚进入是"留校察看"，再次命中升级"保护区"

# 9.2 Count-Min Sketch

TinyLFU 的频次统计用 Count-Min Sketch ——一种概率数据结构：

传统计数：每个 key 一个计数器       N 个 key 占 N × 4B
CM Sketch：4 行哈希表 + min 操作    1 万个 key 仅占 16 KB（恒定）

写入 key:
  for i in 0..3:
    table[i][hash_i(key) % m] += 1

查询 key 频次:
  return min(table[i][hash_i(key) % m]) for i in 0..3

1
2
3
4
5
6
7
8
9

疑惑：这不是"近似计数"吗？怎么保证准确？

论证：CM Sketch 用 4 个独立哈希函数 + 取最小值，多个 key 的"哈希碰撞累加"会被取 min 抵消大部分——准确率 95%+。

频次老化：每隔 N 次写入，全表整体 /= 2 ——上周热数据的频次会被指数衰减——彻底解决了 §8.2 LFU 的"老数据霸占"问题。

结论：CM Sketch 用 16 KB 的固定空间表达千万级 key 的频次——用概率换空间。这与第 4 篇 BloomFilter 同源——工程上可接受的误差换巨大资源节省。

# 9.3 异步驱逐机制

Caffeine 真正的并发杀手锏——所有"维护操作"异步化：

get(key) 同步路径：
  1. 哈希查找 → 拿到 value
  2. 把"访问事件"写入 ringbuffer (无锁 CAS)
  3. 返回
  
异步消费线程 (Drain):
  4. 批量从 ringbuffer 读出事件
  5. 加锁更新 LRU 链表 + 频次表
  6. 触发驱逐

1
2
3
4
5
6
7
8
9

对比 LinkedHashMap 的"同步搬移链表"——Caffeine 的 get 几乎不持有锁，吞吐量提升 10~50 倍。

核心思想：把"维护工作"从关键路径移开——这与 §17 篇 G1 GC 的"并发标记"、§9 篇 LongAdder 的"分段 + 异步合并"是同一套哲学：关键路径只做必须做的事，其余全部异步。

结论：Caffeine 之所以击败 LinkedHashMap-LRU，不是算法更聪明，是工程更聪明——W-TinyLFU 提供了准确度，异步驱逐提供了吞吐量。两者缺一不可。

# 10. 综合案例串讲

# 10.1 缓存崩盘真相

回到第 1 章的两起事故，逐条揭晓：

① LinkedHashMap 为什么不是线程安全的？get 也会修改链表吗：accessOrder=true 模式下，get 调用 afterNodeAccess——修改 6 个指针把节点搬到 tail（§4.2）。这本质是写操作，多线程并发会导致链表错乱、断链甚至成环。§1.1 案例的根因就是把"读 API"误认为"读操作"。

② accessOrder=true 与 false 的差别：底层链表结构相同（before/after 双指针），差别在 afterNodeAccess 的实现——insertion 模式下空实现（get 不动链表），access 模式下做 6 步指针搬移。这一个 boolean 字段决定了 LinkedHashMap 是"有序 Map"还是"LRU 容器"。

③ 双血统的内存代价：每节点多 16B（before/after 指针 + 对齐），50% 固定溢价（§3.3）。在"需要有序遍历"场景值得；在"通用 Map"场景是浪费。§1.2 那位同事用 LinkedHashMap 做无序 sessionAttrs，5000 万节点多吃 800MB——这就是"用错容器导致的内存税"。

④ 手撕 LRU 用 LinkedHashMap vs 自建链表：面试官真正考的是模板方法模式的理解——LinkedHashMap 的 3 大钩子是经典的"父类骨架 + 子类策略"。手写双向链表写得再好也只是"重复造轮子"，用 LinkedHashMap 才能展示对 JDK 设计哲学的理解（§7.1）。但生产环境永远不要用 LinkedHashMap 做 LRU 缓存——并发性能太差。

⑤ 为什么 Caffeine 不用 LinkedHashMap：LinkedHashMap-LRU 有三个硬伤——并发性能差（必须用写锁）、缓存污染（一次性访问冲掉热数据）、无频次概念（无法识别真正的热点）。Caffeine 用 W-TinyLFU 解决污染、Count-Min Sketch 解决频次存储、异步驱逐解决并发——三层组合拳全面碾压（§9）。

§1.1 凌晨链表错乱事故复盘：开发同学用 LinkedHashMap + accessOrder=true，但没意识到 get 不是只读——多线程并发 get 导致链表成环——下次 LRU 驱逐遍历到环时进入死循环——CPU 飙到 100%——服务雪崩。修复方案：改用 Caffeine，3 行代码搞定，吞吐量提升 30 倍。

# 10.2 一次 get 的链表搬移

把 lruCache.get(userId) 这行的完整链路串起来——回扣本册前 21 篇：

T 0     get(userId) 调用
        [13篇] invokevirtual LinkedHashMap.get
        
T+5ns   先查 hash 表
        [04篇] hash & (n-1) 定位桶
        [20篇] 桶内单链表/红黑树查找节点
        
T+10ns  找到节点 e
        
T+15ns  调用 afterNodeAccess(e)
        [§4.2] accessOrder 检查
        if (accessOrder && tail != e):
        
T+20ns  6 步指针搬移
        ① 从原位置摘下 (改 4 个指针)
        ② 挂到 tail (改 2 个指针)
        ③ modCount++
        
        [16篇] G1 SATB 写屏障：
              before/after 跨代引用频繁触发 RememberedSet
              ★ LinkedHashMap GC 比 HashMap 慢 20%~30% 的根因
        
T+30ns  返回 value
        
并发视角：
        [20篇] 单线程 OK，多线程必崩
        必须 synchronizedMap 包装或换 Caffeine
        
JIT 视角：
        [14篇] get 是热点方法，C2 编译
        但 6 步指针操作分支多、依赖深，
        难以被向量化或循环展开优化
        
对比 HashMap.get：
        HashMap.get 没有 afterNodeAccess 调用
        T+15ns 直接返回——快 50%
        ★ LinkedHashMap-access 模式 get 比 HashMap.get 慢 50%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

这条时间线串起本篇的关键概念——一行普通的 get 背后，是模板方法钩子触发链表搬移、写屏障、并发陷阱的连锁反应。

# 10.3 设计哲学回扣

跳出技术细节，提炼三条贯穿 LinkedHashMap 与缓存设计的工程哲学：

机制与策略分离：LinkedHashMap 提供"双向链表 + 钩子"的机制，把"是否驱逐、按什么驱逐"的策略留给用户（removeEldestEntry）。这条原则在 §17 G1 的"垃圾回收策略可插拔"、§7 类加载器的双亲委派、§9 LongAdder 的"分段 + 合并策略"都有体现。框架定义机制，用户决策策略——开闭原则的精髓。
关键路径只做必须做的事：Caffeine 的核心突破不是算法更聪明，而是把维护工作异步化。LinkedHashMap-LRU 失败的根因——get 路径上做了 6 步指针搬移。这条原则与 §17 G1 并发标记、§9 LongAdder 异步求和、§14 JIT 后台编译一脉相承——关键路径越短越好，其余尽可能异步。
抽象的"读"未必真是读：LinkedHashMap-access 让我们重新理解"读 API"——一个看起来无副作用的 get，可能在底层修改 6 个指针、增加 modCount、触发驱逐。永远不要假设 API 名字代表行为——读源码、读文档、读注释。这条教训贯穿 Java 整个生态——String.intern() 改字符串池、Integer.valueOf() 命中缓存、HashMap.get() 在 access 模式下是写……真相在源码里，不在方法名里。

# 10.4 缓存选型速查表

最后一张表——任何缓存场景 5 秒决策：

业务诉求	推荐	不推荐	理由
单线程 LRU 原型	`LinkedHashMap + accessOrder`	自写双向链表	代码量最少
高并发 LRU/LFU	`Caffeine`	LinkedHashMap	性能差 30 倍以上
分布式缓存	`Redis`	本地 Map	跨节点共享
多级缓存	`Caffeine + Redis`	单一层	减少网络往返
持久化缓存	`Ehcache + 磁盘`	仅内存	重启不丢失
有序遍历 Map	`LinkedHashMap`	TreeMap	O(1) vs O(log n)
配置/枚举 Map	`EnumMap` / `ImmutableMap`	LinkedHashMap	内存更紧凑
Spring Bean 容器	`LinkedHashMap`（已是默认）	替换	保证启动顺序
HTTP 响应头	`LinkedHashMap`	HashMap	RFC 要求保序
JSON 序列化 Map	`LinkedHashMap`	HashMap	保证字段顺序

LinkedHashMap 心法三条：

1. 单线程有序遍历——LinkedHashMap 默认模式
2. 高并发缓存——永远选 Caffeine，永远不要选 LinkedHashMap
3. accessOrder=true 模式下，get 是写操作——必须加锁或换 Caffeine

1
2
3

至此第 22 篇完成——我们用 1.5 万字把 LinkedHashMap 双血统设计、三大钩子、insertOrder/accessOrder、手撕 LRU、Caffeine W-TinyLFU 讲透。卷二容器篇还有最后两篇——队列与栈。下一篇我们顺着"为什么 ArrayBlockingQueue 用一把锁、LinkedBlockingQueue 用两把锁"这条线，进入 第 23 篇：阻塞队列与生产者消费者——把 ArrayBlockingQueue 单锁双 Condition、LinkedBlockingQueue 双锁分离、SynchronousQueue 的"零容量握手"、PriorityBlockingQueue 的堆扩容一次讲透。

上次更新: 2026/06/10, 11:13:41

← TreeMap与红黑树原理 Java数字类型原理→