# 第 29 章 集合框架原理 > 集合是面试唯一"必出"的 Java 题目：哈希扰动、扩容拆分、树化阈值每个细节都能被追问。 ## 学习目标 读完本章，你应当能够： 1. 按有序性、去重、并发安全、随机访问四个维度推导容器选型并说出代价； 2. 逐位推导 `HashMap` 的 `hash` 扰动、`(n-1) & hash` 取模、`tableSizeFor`、`hash & oldCap` 拆分，说明每一步"不这么做会怎样"； 3. 说出负载因子 `0.75`、树化 `8`、退化 `6`、最小树化容量 `64` 四个数字各自的来源； 4. 解释 `ConcurrentHashMap` 从 `Segment` 到 `CAS + synchronized` 的演进动因，说明 `get` 为何无锁安全；写出 `LinkedHashMap` 的 LRU 实现并判断 `CopyOnWriteArrayList` 的适用边界； 5. 定位 `TimSort` 的 "Comparison method violates its general contract" 并说明成因。 ### 前置知识检查 | 你需要知道 | 在哪一节补齐 | |---|---| | `equals`/`hashCode` 契约与不可变键 | 见第 28 章 28.2 节 | | `synchronized` 锁的是对象头 Mark Word、`volatile` 提供可见性 | 见第 30 章 30.3 节 | | CAS 指令与 `Unsafe.compareAndSwapInt` | 见第 30 章 30.2 节 | | 树高与平衡的直观概念 | 本章 29.7.1 给出红黑树五条性质 | ## 29.1 集合框架的两条线 `java.util` 分两条互不重叠的线：`Collection` 存单个元素，`Map` 存键值对。`Map` 不继承 `Collection`，因为按键查找的 `remove`、`contains` 语义无法与单元素容器统一。 ```text Collection ├── List 有序、可重复、有下标 │ ├── ArrayList 数组 / LinkedList 双向链表（同时实现 Deque） │ ├── Vector 全方法 synchronized（历史遗留）/ CopyOnWriteArrayList 写时复制 ├── Set 不重复：HashSet（内部是一个 HashMap，value 是同一哨兵对象） │ LinkedHashSet（LinkedHashMap，保留插入顺序）/ TreeSet（内部是 TreeMap） └── Queue / Deque：ArrayDeque 循环数组（栈与队列首选）/ PriorityQueue 二叉堆，非 FIFO Map ├── HashMap：LinkedHashMap（额外双向链表维护顺序）/ ConcurrentHashMap（并发安全） ├── Hashtable 全方法 synchronized（历史遗留） ├── TreeMap 红黑树，按 key 排序 / WeakHashMap 键为弱引用（见第 32 章 32.4 节） ``` 选容器时按四个问题依次问下来，顺序不能颠倒 —— 前一个答案会否决后面的选项： | 问题 | 是 | 否 | |---|---|---| | 需要按键查找吗 | `Map` 线；要排序则 `TreeMap`，要并发则 `ConcurrentHashMap` | `Collection` 线，继续 | | 需要去重吗 | `Set` 线；要保留插入顺序则 `LinkedHashSet` | `List` 线，继续 | | 需要并发安全吗 | 读多写极少用 `CopyOnWriteArrayList`；否则在锁内整体替换引用 | 继续 | | 需要按索引随机访问吗 | `ArrayList` | 只在两端增删用 `ArrayDeque`；必须实现 `List` 才用 `LinkedList` | > [!IMPORTANT] > `Collections.synchronizedList` 的包装器只保证单个方法原子，遍历时必须在外部 `synchronized (list)`，否则照样抛 `ConcurrentModificationException` —— 包装器不提供迭代器同步是既定设计。 ## 29.2 ArrayList：扩容、快速失败与视图陷阱 ### 29.2.1 扩容机制 存储是 `transient Object[] elementData`，`size` 是逻辑长度、`elementData.length` 是容量，两者不等；无参构造先指向共享空数组，第一次 `add` 才分配 `DEFAULT_CAPACITY = 10`。扩容走 `grow`，新容量是 `oldCapacity + (oldCapacity >> 1)`，即约 `1.5` 倍（10 变 15，15 变 22）：`2` 倍最多浪费一半已分配空间，`1.2` 倍则把复制常量系数推高，`1.5` 是折中。 ```text n 次追加触发的复制总元素数（每次扩容复制一次全量） 复制总量 = n/1.5 + n/1.5² + n/1.5³ + … < n / (1.5 − 1) = 2n ⟹ 单次 add 摊还 O(1) ``` 但**单次扩容仍是 `O(n)`**：`Arrays.copyOf` 新建数组并整体复制，容量 1000 万时一次扩容要搬运约 1500 万个引用（压缩指针下每个引用 4 字节即约 120 MB），耗时进入十毫秒级。所以已知要放 `n` 个元素时用 `new ArrayList<>(n)`，把 `O(log n)` 次扩容降为 0 次，代价是最多多占 `n/2` 个槽位。 > [!TIP] > `clear` 只把元素置 `null`、`size` 归零，**不缩容**，所以集合复用前用 `ensureCapacity` 预设容量可以避免下一轮扩容。 ### 29.2.2 `modCount` 与快速失败 `AbstractList` 有 `protected transient int modCount`，每次结构性修改（`add`、`remove`、`clear`）自增；迭代器 `Itr` 创建时把它记进 `expectedModCount`，`next()` 与 `remove()` 开头都调用 `checkForComodification()`，一旦发现两者不等就抛 `ConcurrentModificationException`。 `for-each` 会被编译成 `Iterator` 循环，所以"为什么 `for-each` 里不能 `remove`"的准确答案是：`ArrayList.remove(Object)` 只自增 `modCount`，不同步迭代器的 `expectedModCount`，下一次 `next()` 必然抛异常。而 `Iterator.remove()` 删除后把两者重新对齐，还要修游标： ```java public void remove() { if (lastRet < 0) { throw new IllegalStateException(); } checkForComodification(); ArrayList.this.remove(lastRet); cursor = lastRet; // 删除后游标回退一格，否则会跳过被删元素的后继 lastRet = -1; // 同一位置不允许连删两次，否则会删错元素 expectedModCount = modCount; // 与 modCount 重新对齐，这是它不抛异常的根因 } ``` `removeIf` 更安全：内部用位图与游标批量删除、最后统一压缩数组，复杂度 `O(n)` 而不是逐个 `remove` 的 `O(n²)`。 > [!CAUTION] > `ConcurrentModificationException` 的名字有误导性，**它和并发无关**。单线程里 `for (String s : list) { if (cond) list.remove(s); }` 必然触发。面试问"这个异常怎么产生"如果答"多线程同时修改"就是踩坑，正确说法是"迭代器检测到 `modCount` 与自己持有的 `expectedModCount` 不一致"。 ### 29.2.3 `subList` 的视图语义 `subList` 返回内部类 `SubList`，它不是新集合，而是持有 `parent` 引用的**视图**：`get` 做 `parent.get(offset + index)`，`set` 直接写回原数组，`remove` 会把 `parent.modCount` 一起自增。后果是：`set` 双向穿透；对子列表做结构性修改会同步修改原列表；拿到子列表后又改了原列表的结构，再操作子列表就抛 `ConcurrentModificationException`。要独立副本必须显式写 `new ArrayList<>(list.subList(0, 10))`。 ## 29.3 LinkedList 的真实性能画像 "插入删除 `O(1)`"在实践里几乎从不成立，有四个独立可追问的原因： | 代价来源 | 具体数字 | 后果 | |---|---|---| | 寻址是 `O(n)` | 折半优化后定位第 `k` 个节点平均仍要走 `n/4` 个节点 | `O(1)` 只对"已持有节点引用的迭代器"成立，按下标插入是 `O(n)` | | 缓存不友好 | 节点 = 对象头 12 字节 + 3 个引用（压缩指针下 4 字节 × 3）+ 填充 4 字节 = 32 字节 | 节点在堆上随机分布，一次主存访问约 100 ns 且几乎每次都缺 L1 | | 内存放大 | 存 1 个 4 字节引用要花 32 字节节点 = 8 倍；只算"对象头 + 两个指针"的必要开销也是 4 倍量级 | 同样数据量下占用远高于 `ArrayList` | | 每次 `add` 一次对象分配 | 每插入一个元素分配一个 `Node` | 分配压力大，还多一次可达性分析与回收成本 | 实际取舍：只在两端增删时用 `ArrayDeque`（它不实现 `List`，没有索引访问），需要频繁中间插入时先追问"能否改成头尾操作"，不能则考虑 `ArrayList` 批量重建或 `LinkedHashMap` 按键定位；栈与队列一律用 `ArrayDeque`，不要用 `Stack`（继承 `Vector`、方法全 `synchronized`，且迭代顺序是反的）。`ArrayDeque` 容量是 `2` 的幂，头尾操作都 `O(1)`： ```text ArrayDeque 循环数组（容量 8，head=6，tail=2） index: 0 1 2 3 4 5 6 7 [ ] [ ] [ c] [ d] [ ] [ ] [ a] [ b] ↑ tail=2 ↑ head=6 头插：head = (head - 1) & (length - 1) → 5；尾插：tail = (tail + 1) & (length - 1) → 3 ``` > [!WARNING] > 常见错误回答是"`LinkedList` 增删快所以更适合频繁插入"。在节点随机分布、缓存层级主导性能的现代 CPU 上，批量构建 100 万元素的 `ArrayList` 往往比 `LinkedList` 快数倍，遍历快一个数量级。正确回答要先追问插入位置、是否已持有节点引用。 ## 29.4 HashMap：完整实现 ### 29.4.1 数据结构 JDK 8 起是"数组 + 链表 + 红黑树"，`Node` 有 `hash`、`key`、`value`、`next` 四个字段，`hash` 缓存扰动后的值以避免每次比较重算。 ```text HashMap 结构（table.length = 16，阈值 = 16 × 0.75 = 12），index = (16 − 1) & hash table 0 │null│ 1 │ ●──┼──► Node(hash,k1,v1) ──► Node(hash,k2,v2) ──► null ← 链表 2 │null│ 3 │ ●──┼──► TreeNode ──► TreeNode ─┬─► TreeNode ──► null ← 红黑树 └─► TreeNode ──► TreeNode ──► null 4 │ ●──┼──► Node ──► null 桶 1 与桶 17 索引相同，差值恰为 16 = oldCap ``` ### 29.4.2 扰动函数与索引计算 ```java // HashMap 的哈希扰动：把 32 位哈希的高 16 位异或到低 16 位。容量小时索引只用低几位， // 不做扰动则高位信息被整体丢弃，高位不同而低位相同的键会全部挤进同一个桶 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ``` 索引取 `hash` 的低 `log₂(n)` 位 —— 容量 16 只用低 4 位，容量 32 只用低 5 位，高位再随机也参与不进索引，所以 `h ^ (h >>> 16)` 用一条移位加一条异或把高位的熵混进低位；JDK 7 用更长的扰动序列，JDK 8 简化为一次，因为实测收益已不明显。 `key == null` 返回 `0` 而不是抛异常，所以 `HashMap` 允许一个 `null` 键，它永远落在桶 0；`ConcurrentHashMap` 不允许 `null`，因为并发下无法区分"值为 `null`"与"键不存在"。 索引是 `(n - 1) & hash`：因为 `n = 2^k`，`n - 1` 的二进制是低位连续 `k` 个 `1`（16 − 1 = `0b1111`），按位与的结果恰好是 `hash mod 2^k`，即 `hash mod n`。这要求 `n` 必须是 `2` 的幂：若 `n = 15`，`n - 1 = 0b1110`，结果最后一位恒为 `0`，桶 1、3、5… 永远取不到。位与只要 1 个周期，`%` 要几十个周期。`tableSizeFor` 把任意初始容量向上取整到 `2` 的幂： ```java static final int tableSizeFor(int cap) { int n = cap - 1; // 减一：让 cap 本身是 2 的幂时不被抬高一倍（16 → 32） n |= n >>> 1; // 以下五步把最高位 1 之后的每一位都填成 1； n |= n >>> 2; // 移位长 1、2、4、8、16 恰好覆盖 32 位， n |= n >>> 4; // 指令数固定为 5 条，与 cap 大小无关 n |= n >>> 8; n |= n >>> 16; // 此时 n 是"低位全 1 且不超过原最高位"的数，加一即得 2 的幂 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } ``` 例：`cap = 17` → `n = 16 = 0b10000` → 填满得 `0b11111 = 31` → 返回 `32`；`MAXIMUM_CAPACITY = 1 << 30` 是 `int` 正数范围内最大的 `2` 的幂。 ### 29.4.3 四个数字的来源 **负载因子 `0.75`** 是时间与空间的折中：越小冲突越少但越浪费内存、扩容越频繁；越大越省内存但链表越长。类注释给出的论证基于泊松分布（Poisson distribution）：哈希均匀时一个桶的元素个数服从参数 `λ = 0.5` 的泊松分布，概率依次是桶内 0 个 `0.60653066`、1 个 `0.30326533`、2 个 `0.07581633`、4 个 `0.00157952`、6 个 `0.00001316`、7 个 `0.00000094`、8 个 `6 × 10⁻⁸`。 **树化阈值 `TREEIFY_THRESHOLD = 8`**：理想哈希下链表长度到 8 的概率只有 `6 × 10⁻⁸` 量级（约千万分之六），这意味着"正常情况下永不树化"。一旦真树化，说明要么哈希被人为构造（哈希碰撞攻击，恶意制造大量同 `hashCode` 的键把查询退化成 `O(n)`），要么 `hashCode` 实现极差，此时红黑树的 `O(log n)` 是兜底。这不是"从概率反解出最优阈值"，而是概率论证被用作选定 8 的合理性依据。 **退化阈值 `UNTREEIFY_THRESHOLD = 6`**：树退化成链表要求元素数 `≤ 6` 而不是 `≤ 8`。若两阈值相等，一个桶在 7~8 个元素之间反复增删就会在链表与树之间来回转换，每次都要重建节点并频繁触发扩容路径；`6` 与 `8` 之间留出一个元素的缓冲带（判定是"`≤ 6` 才退化"，所以 7 个元素时既不树化也不退化），避免抖动。 **最小树化容量 `MIN_TREEIFY_CAPACITY = 64`**：`treeifyBin` 先检查 `table.length`，不足 64 就优先扩容而不树化。桶内元素多往往是因为容量小、索引位不够，扩容后元素会分散，常常自动解决；同时 `TreeNode` 比 `Node` 多 `parent`、`left`、`right`、`prev`、`red` 五个字段，容量小时树化得不偿失。 > [!IMPORTANT] > 四个数字连起来记：`0.75` 是负载因子的折中，`8` 是"理想哈希下几乎不可能达到"的树化线，`6` 是防抖动的退化线，`64` 是"先扩容再考虑树化"的门槛。面试官常连续追问这四个数字，只答数字、说不出动因会被判为背诵。 ### 29.4.4 `put` 的完整流程 ```text put(key, value) → putVal(hash(key), key, value, false, true) 1. table 为 null 或 length == 0 ──► resize() 分配初始容量（懒初始化） 2. i = (n-1) & hash；table[i] == null ──► 直接 new Node 放入，跳到第 6 步 3. p = table[i]，若 p.hash == hash 且 key 相等 ──► onlyIfAbsent 为 false 或旧值为 null 时覆盖 value，跳到第 6 步 4. p instanceof TreeNode ──► putTreeVal 走红黑树插入/更新 5. 否则遍历链表（binCount 从 0 计）：命中同 hash 同 key 的节点则覆盖 value； 走到尾部则尾插新节点；插入后链长达 8 则 treeifyBin(table, hash) 6. ++modCount；++size > threshold ──► resize()；最后触发 afterNodeAccess / afterNodeInsertion（LinkedHashMap 的钩子，见 29.7.3） ``` 第 4 个参数 `onlyIfAbsent` 的语义是"键已存在且值非 `null` 时是否放弃覆盖"：`put` 传 `false`，`putIfAbsent` 传 `true`，`computeIfAbsent`、`merge` 也复用这条路径。JDK 8 把链表插入从头插改成尾插不只是语义自然：头插在并发扩容时会把链表顺序反转，两个线程同时扩容可能构造出环形链表，导致后续 `get` 死循环、CPU 100%。尾插消除了这个特定场景，但 **`HashMap` 依然不是线程安全的**，并发 `put` 仍会丢数据、`size` 计数出错。 ### 29.4.5 `resize`：容量为何总是 `2` 的幂，以及拆分技巧 容量被强制为 `2` 的幂，有两个不可替代的原因：一是索引计算 `(n-1) & hash` 等价于 `hash % n` **仅当** `n` 是 `2` 的幂；二是 `2` 倍扩容后新容量仍是 `2` 的幂，元素的**新索引只有两种可能** —— 原索引，或原索引 + `oldCap`。第二条是关键：设 `oldCap = 2^k`、`newCap = 2^(k+1)`，旧索引取低 `k` 位，新索引取低 `k+1` 位，多出来的那一位正是 `hash` 的第 `k` 位，其值恰好等于 `hash & oldCap`： ```text 以 oldCap = 16（0b10000）、newCap = 32 为例 hash = 0b…0001_0101 = 21：oldCap-1 = 15 = 0b1111 → 旧索引 0101 = 5 newCap-1 = 31 = 0b11111 → 新索引 10101 = 21；判断 21 & 16 ≠ 0 ⟹ 新索引 = 5 + 16 结论：hash & oldCap == 0 → 挂低位链 loHead/loTail，位置仍是 j hash & oldCap != 0 → 挂高位链 hiHead/hiTail，位置是 j + oldCap ``` 因此 JDK 8 的 `resize` 不对每个节点重算 `hash % newCap`（那是 `O(n)` 次取模），而是把旧桶链表**拆成两条**：低位链保持相对顺序挂 `newTab[j]`，高位链挂 `newTab[j + oldCap]`，每个节点只做一次位与。树节点同理用 `TreeNode.split` 拆两条，某条长度 `≤ 6` 就退化成链表，否则重新树化；`TreeNode` 比 `Node` 多出 `parent`、`left`、`right`、`prev`、`red` 五个字段，其中 `prev` 是为了树化与退化时能沿链表顺序遍历。一次扩容要翻倍容量与阈值并遍历整个旧数组，时间是 `O(n + 容量)`，所以已知要放 `n` 个元素时用 `new HashMap<>((int)(n / 0.75) + 1)`：除以 `0.75` 是因为阈值 = 容量 × 0.75、容量必须 `≥ n / 0.75`，`+1` 是让 `tableSizeFor` 向上取整后仍有富余。 > [!WARNING] > 若 `equals` 相同且 `hashCode` 全相同，JDK 8 之后查询仍是 `O(log n)`；但 JDK 7 及以前是纯链表，构造 `n` 个同哈希键可把一次 `get` 打成长达数秒的 `O(n)` 扫描 —— 这就是哈希碰撞攻击（hash collision DoS）。面试追问"树化阈值的意义"时，从攻击场景切入比从概率切入更能加分。 ## 29.5 ConcurrentHashMap：从分段锁到 `CAS + synchronized` ### 29.5.1 JDK 7 的分段锁 JDK 7 是"`Segment` 数组 + 每段一个 `HashEntry` 数组"。`Segment` 继承 `ReentrantLock` 并实现 `Serializable`，本质是**小号 `HashMap` 且自带一把锁**，并发度等于段数，默认 `16`。写操作先由 `hash` 高位定位段，再 `lock()`，然后在段内做与 `HashMap` 相同的操作。两个固有问题：**并发度静态写死**，8 核够用而 128 核直接成瓶颈，段数越多每段的数组越小、越碎片化；**内存开销大**，每多一段就多一个 `HashEntry` 数组加一个 `ReentrantLock` 及其 AQS 队列。因此 JDK 8 放弃分段锁，改为锁桶头节点，把锁粒度压到一个桶。 ### 29.5.2 JDK 8 的 `CAS + synchronized` `putVal` 主干是一个自旋循环，按桶的当前状态分四种情况： ```text putVal 循环体 1. table 未初始化 ──► initTable()：用 sizeCtl 的 CAS 抢占，成功者建表， 失败者 yield 重试（保证只分配一次；初始化期间 sizeCtl 为负值表示进行中） 2. i = (n-1) & hash，桶空（tabAt 返回 null） ──► casTabAt(tab, i, null, new Node(...))；成功即完成，全程无锁； 失败说明别的线程抢先放入，重新循环 3. f.hash == MOVED（−1，即 f 是 ForwardingNode） ──► helpTransfer(tab, f) 协助扩容，然后重新循环 4. 桶已有节点 ──► synchronized (f) { ← 只锁这一个桶的头节点 if (tabAt(tab, i) == f) { ← 双重检查：锁内可能已被别人改过 f.hash >= 0 ──► 遍历链表，命中则按 onlyIfAbsent 覆盖， 否则尾插并统计 binCount f instanceof TreeBin ──► putTreeVal 走红黑树 } } 链长达 8 ──► treeifyBin（同样受 MIN_TREEIFY_CAPACITY = 64 约束） 5. addCount(1L, binCount)：更新 size；超阈值则触发 transfer 扩容 ``` **为什么是 `CAS` 加 `synchronized` 而不是纯 `CAS`**：桶空时 `CAS` 是零锁最快路径，覆盖大部分"新键插入"场景；桶非空时链表/树插入是对多个字段的复合修改（读尾节点、改 `next`，或旋转调整树），难以用单条 `CAS` 表达。而 `synchronized` 在 JDK 6 之后有偏向锁与轻量级锁优化（见第 30 章 30.3 节），无竞争时开销与 `CAS` 同数量级（约 20 ns），所以"非空桶加锁"不会成为热点。 **`size` 的 `baseCount + CounterCell` 分散计数**：精确计数要求所有线程对同一个 `volatile long` 做 `CAS`，竞争剧烈。JDK 8 借用 `LongAdder` 思路：先 `CAS` 更新 `baseCount`，失败则给当前线程分配一个 `CounterCell`，之后只改自己那个格子，`sumCount()` 最后求和。不同线程写不同缓存行，避免伪共享导致的缓存行反复失效（见第 2 章 2.7 节）：`size() = baseCount + Σ CounterCell[i].value`，例如 `baseCount = 3`、两个线程各自的格子是 `1` 与 `2`、第三个格子 `0`，则 `size = 6`；`cellsBusy` 只是 `cells` 数组初始化/扩容用的自旋标志。代价是 `size()` **不是原子的精确值**：`sumCount` 遍历时其他线程可能还在写，返回值只是某一瞬间的近似，是弱一致，只适合监控统计。 **`transfer` 的协助扩容与 `ForwardingNode`**：扩容时建好 `newTab`，每个槽位用 `CAS` 放入 `ForwardingNode`（`hash = MOVED = −1`，持有 `nextTable` 引用），表示"该桶已迁移完，去新表找"；搬运粒度是一个桶（按 `stride` 划分区间，最小步长 `16`），正在搬运的槽位用 `synchronized` 锁住原桶头节点。任何线程 `put` 时遇到 `ForwardingNode` 就调用 `helpTransfer` 加入扩容：先给 `sizeCtl` 的协助者标记加一，再分摊区间搬运，于是**扩容的总工作由所有正在写的线程共同完成**，不会出现"一个线程扩容、其余全部阻塞"的长停顿。 **`get` 为什么可以不加锁**：`Node` 的 `val` 与 `next` 都是 `volatile`，桶数组本身也是 `transient volatile Node[] table`；`tabAt` 用 `Unsafe.getObjectVolatile` 读，保证看到最新发布的元素，沿 `next` 继续走也是 `volatile` 读，链表中的节点其字段初始化已完成（`volatile` 写对 `volatile` 读建立 happens-before，见第 30 章 30.1 节）。代价是 **`get` 返回弱一致结果** —— 可能读到旧值，也可能在扩容中途被 `ForwardingNode` 指引到新表，换来的是完全无阻塞的读路径。 > [!NOTE] > `ConcurrentHashMap` 不允许 `null` 键与 `null` 值（`putVal` 开头判空即抛 `NullPointerException`），与 `HashMap` 相反。原因是并发下 `get` 返回 `null` 无法区分"键不存在"与"键存在但值为 `null`"，靠 `containsKey` 二次确认又存在竞态。 ## 29.6 CopyOnWriteArrayList 的适用边界 写时复制（copy-on-write, COW）在这里是"复制整个数组 + 修改副本 + 用 `volatile` 写换掉引用"，所有写操作在独占锁内完成，读直接读那个引用： ```java public boolean add(E e) { final ReentrantLock lock = this.lock; lock.lock(); // 写必须互斥，否则两个线程的副本会互相覆盖、丢失更新 try { Object[] elements = getArray(); int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len + 1); // 复制整个数组，O(n) newElements[len] = e; setArray(newElements); // volatile 写：保证新数组对后续读线程立即可见 return true; } finally { lock.unlock(); } } ``` 读路径完全无锁（`get`、`size`、`contains` 直接读 `array` 引用，语义链条是 `volatile` 写 → `volatile` 读，见第 30 章 30.2 节）。适用范围由此唯一确定：**读远多于写，且能容忍写时的 `O(n)` 复制与短暂内存翻倍**，典型是配置项、监听器、白名单这类几乎只读、偶尔全量替换的数据。它的迭代器是**弱一致（weakly consistent）**的：创建时捕获当时的数组引用，之后即使增删也继续遍历旧快照，因此**永不抛 `ConcurrentModificationException`，也看不到迭代期间的新增元素**。 | 维度 | `Vector` / `synchronizedList` | `CopyOnWriteArrayList` | |---|---|---| | 读操作 | 加锁，读读互斥 | 无锁，只读 `volatile` 引用 | | 写操作 | 加锁，原地修改，摊还 `O(1)` | 加锁 + 复制整个数组，`O(n)` | | 迭代器 | 需外部同步，否则抛 `CME` | 快照式弱一致，永不抛 | | 内存 | 一份数组 | 写时短暂两份数组 | | 适用 | 读写均衡 | 读多写极少且数据量不大 | > [!CAUTION] > `CopyOnWriteArrayList` 的 `add` 是 `O(n)`：10 万元素的列表每写一次要复制约 10 万个引用（约 400 KB 内存搬运），写入每秒数百次就会让 CPU 与 GC 压力爆掉，还远不如一把 `ReentrantReadWriteLock`。面试里说"要线程安全的 List 就用 `CopyOnWriteArrayList`"是典型踩坑回答。 ## 29.7 TreeMap、红黑树与 LinkedHashMap 的 LRU ### 29.7.1 红黑树的五条性质与调整 | 编号 | 性质 | 作用 | |---|---|---| | 1 | 每个节点是红色或黑色 | 提供额外状态位 | | 2 | 根节点是黑色；每个叶子节点（`null`）是黑色 | 统一黑高定义，避免边界特判 | | 3 | 红节点的两个子节点都是黑色（不存在连续两个红节点） | 限制最长路径中红节点不能连排 | | 4 | 任一节点到其所有叶子的路径上黑节点数相同（黑高相等） | 限制最短路径长度 | 由性质 4 与 5 可推：最长路径（红黑交替）最多是最短路径（全黑）的 2 倍，树高被限制在 `2 × log₂(n+1)`，所有操作 `O(log n)`；与 AVL 树（严格平衡、旋转更多）相比，这是"放宽平衡换取更少的调整次数"。插入的调整规则（新节点先染红）：父黑则无需调整；父红时若叔叔为红就变色并把祖父当新节点继续向上处理，叔叔为黑或不存在则旋转（`LL` 右旋、`RR` 左旋、`LR` 先左后右、`RL` 先右后左）并重新染色。删除更复杂，因为它可能破坏性质 5：删红节点不影响黑高，删黑节点要在兄弟一侧"借"一个黑节点，借不到就继续向上递归。 ### 29.7.2 `TreeMap` 的比较依据 `TreeMap` 完全按 `compareTo`（`Comparable`）或 `compare`（`Comparator`）定位节点，**不调用 `hashCode` 与 `equals`**：红黑树靠"左右子树的大小关系"导航，而 `hashCode` 的数值大小与排序顺序毫无关系。后果是：`compare` 返回 `0` 即视为同一个键，即使 `equals` 返回 `false`，所以按"年龄"排序去重时两个年龄相同但姓名不同的人会被当作同一个键、后者覆盖前者（这是与 `HashMap` 语义差异的最大陷阱）；键必须可比较，否则抛 `ClassCastException`；`TreeMap` 允许 `null` 键**仅当**自定义 `Comparator` 能处理 `null`。每次操作调用 `O(log n)` 次比较，换取有序与范围查询（`subMap`/`headMap`/`tailMap`/`firstKey`），注意 `subMap` 同样是**视图**，与 29.2.3 的 `subList` 陷阱同源。 ### 29.7.3 `LinkedHashMap` 的 `accessOrder` 与 LRU `LinkedHashMap` 把 `Node` 换成 `Entry`（多出 `before`/`after` 两个引用），维护一条贯穿所有条目的双向链表。构造器第三个参数 `accessOrder` 决定链表顺序：`false`（默认）按**插入顺序**，只在新节点插入时追加到尾部；`true` 按**访问顺序**，每次 `get`/`getOrDefault`/`compute` 命中都把该节点移到尾部。真正的 LRU 靠两个钩子：`afterNodeAccess` 在 `accessOrder` 为 `true` 时把被访问节点移到尾部，`afterNodeInsertion` 在插入后询问 `removeEldestEntry` 是否删除链表头（最久未使用）的节点。于是固定容量的 LRU 缓存只需： ```java public class LruCache extends LinkedHashMap { private final int maxSize; public LruCache(int maxSize) { // 容量按 maxSize/0.75+1 预设，避免装入过程反复 resize； // accessOrder=true 才是 LRU 的前提，否则退化为 FIFO super((int) (maxSize / 0.75f) + 1, 0.75f, true); this.maxSize = maxSize; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { // 返回 true 时父类会 remove 掉链表头节点，即最久未被访问的那个 return size() > maxSize; } } ``` 三点要说清：它**不是线程安全的**，父类没有任何同步；被淘汰的条目若被外部引用持有，内存仍不释放；`LinkedHashMap` 的迭代顺序由这条链表决定，所以 `LinkedHashSet` 能同时满足"去重 + 保留顺序"，且插入查询都是 `O(1)`，比 `TreeSet` 的 `O(log n)` 便宜。 ## 29.8 排序：`Arrays.sort` 与 `Collections.sort` 同名方法在 JDK 里对应四套算法，分界线是"排基本类型还是对象"： | 方法 | 算法 | 稳定性 | 原因 | |---|---|---|---| | `Arrays.sort(int[]/long[]/…)` | 双轴快速排序（dual-pivot quicksort） | 不保证 | 基本类型没有身份，相等元素谁前谁后都无所谓 | | `Arrays.sort(Object[])` | `TimSort`（归并 + 二分插入） | 稳定 | 对象按字段排序时，相等元素的原有次序有语义 | | `Collections.sort(List)` | 内部转数组走 `Arrays.sort(Object[])` | 稳定 | 同上 | | `Arrays.parallelSort` | 按长度分流：小数组退化为串行算法，大数组用 `ForkJoinPool` 分治归并 | 稳定（对象） | 只有足够大且多核才有收益 | `TimSort` 的核心是利用"现实数据往往部分有序"：先把数组切成若干**运行段（run）**，最短长度 `32`（`MIN_MERGE`），不足则用二分插入排序补足，再按 `runLen` 栈的平衡规则归并相邻 run，避免像朴素归并那样对几乎有序的输入做无谓工作；最好情况 `O(n)`，最坏 `O(n log n)`，且稳定。 **"Comparison method violates its general contract"** 的成因：`TimSort` 的归并优化依赖比较器是**全序**，要满足自反性与反对称性（`compare(a,b)` 与 `compare(b,a)` 符号相反）、**传递性**（`a < b` 且 `b < c` 蕴含 `a < c`）、以及 `compare(a,b) == 0` 是等价关系。最典型的违反来自"差值为负返回 −1、为正返回 1"： ```java // 错误写法：整数溢出后符号翻转，传递性直接崩掉 list.sort((a, b) -> a.getScore() - b.getScore()); ``` 当 `a.getScore()` 是 `Integer.MAX_VALUE`、`b.getScore()` 为负数时差值溢出为负，比较结果与真实大小相反；正确写法是 `Integer.compare(a.getScore(), b.getScore())` 或 `Comparator.comparingInt`。定位只有三条路：先改成安全写法排查；再用 `-Djava.util.Arrays.useLegacyMergeSort=true` 验证是否与排序实现相关（旧归并排序不检测契约，会静默给出错误顺序，只能验证、不能修复）；最后包一层断言型 `Comparator`，缓存近期比较结果，一旦发现 `a < b`、`b < c` 却 `a >= c` 就打印这个三元组 —— 该异常本身不带下标或元素信息，只能这样缩小范围。`parallelSort` 的适用条件：长度足够大（实现里小于 `1 << 13 = 8192` 的元素数会退回串行）、机器多核、且比较器满足契约 —— 否则异常会在 `ForkJoinPool` 工作线程里抛出，堆栈出现 `ForkJoinTask` 相关帧，比串行版更难定位。 ## 29.9 fail-fast 与 fail-safe | 维度 | fail-fast | fail-safe（弱一致） | |---|---|---| | 代表实现 | `HashMap`/`ArrayList`/`TreeMap` 的迭代器 | `CopyOnWriteArrayList`、`ConcurrentHashMap` 的迭代器 | | 检测机制 | `modCount` 与 `expectedModCount` 比对 | 无检测，在快照或当前结构上遍历 | | 触发行为 | 立即抛 `ConcurrentModificationException` | 不抛异常，可能看到旧数据或部分新数据 | | 内存开销 | 无额外开销 | 快照实现需复制整个集合 | | 用途 | 尽早暴露"修改方式不对"的程序错误 | 允许并发环境下安全遍历 | **为什么 `fail-fast` 只是"尽力而为"（best-effort）**：`modCount` 是普通 `int`，**不是 `volatile`**，因此线程 A 的迭代器读 `modCount` 时可能读到线程 B 修改前的旧值（没有 happens-before 保证，见第 30 章 30.1 节）而检测不到修改；反过来，单线程里通过集合自身方法修改则一定能检出 —— 这才是它的主要价值。JLS 与 Javadoc 都明确它不保证一定检出，只用于发现 bug。 > [!IMPORTANT] > 正确表述是：`fail-fast` 是"发现程序错误的尽力而为的检测机制"，不是"并发保护机制"。要并发安全必须换并发容器或自己加锁，不能指望 `ConcurrentModificationException` 兜底。 ## 本章小结 | 关键结论 | 一句话表述 | 常见错误 | |---|---|---| | `ArrayList` 扩容 | 约 `1.5` 倍，`Arrays.copyOf` 整体复制，单次 `O(n)`、摊还 `O(1)` | 说成 `2` 倍；以为 `clear` 会缩容 | | 快速失败 | 迭代器比对 `modCount` 与自己持有的 `expectedModCount` | 把 `CME` 解释成"多线程并发导致" | | `Iterator.remove` | 删除后把 `expectedModCount` 重新对齐并回退游标 | 只说"用迭代器删就安全"，说不出为什么安全 | | `LinkedList` | 理论 `O(1)` 插入，实际因寻址 `O(n)`、节点 32 字节、缓存不友好而少用 | 背"增删快所以用它"，不问插入位置 | | `HashMap` 索引 | `(n-1) & hash` 等价取模的前提是容量为 `2` 的幂 | 认为只是"写法优化"，说不出前提 | | `0.75` / `8` / `6` / `64` | 折中、概率 `6 × 10⁻⁸`、防抖动缓冲、先扩容后树化 | 只背数字，说不出动因 | | 扩容拆分 | `hash & oldCap` 决定留原位还是迁到 `j + oldCap` | 答"要对每个 key 重算 `hash % newCap`" | | `ConcurrentHashMap` `get` | `val`/`next` 是 `volatile`，读无锁、弱一致 | 说"`get` 也加了 `synchronized`" | | `CopyOnWriteArrayList` | 写时复制整数组，只适合读多写极少 | 一律推荐它做"线程安全 List" | | `TreeMap` | 用 `compare` 导航，返回 `0` 即同键 | 说 `TreeMap` 也用 `hashCode` 去重 | | `TimSort` 异常 | 比较器不满足传递性，常因减法溢出 | 以为异常来自"数据有重复元素" | ## 自测题 **Q1**（推导）容量为 `16` 的 `HashMap` 中某 key 扰动后哈希的低 8 位是 `0b1010_1101`。写出扩容前后的桶索引，判断该节点是否迁移。若容量改成 `15`，`(n-1) & hash` 还等价于取模吗？
答案与解析 `oldCap = 16`，`oldCap - 1 = 15 = 0b1111`，取低 4 位 `1101 = 13`，旧索引 `13`。扩容后 `newCap = 32`，`newCap - 1 = 31 = 0b11111`，新索引 `11101 = 29 = 13 + 16`，说明迁到 `j + oldCap`。用拆分公式验证：`hash & oldCap` 即 `hash & 16`，第 5 位（从 0 计）为 `1`，所以 `≠ 0` 迁高位链，落点 `13 + 16 = 29`，一致。若容量为 `15`，`n - 1 = 14 = 0b1110`，结果最后一位恒为 `0`，桶 1、3、5、7… 永远无法命中，索引不再是 `hash % 15` —— 这正是"容量必须是 `2` 的幂"的根因。错在哪：把新索引答成"`13` 或者重新 `hash % 32` 得到的任意值"。面试官会追问"为什么不需要重新计算哈希"以及"容量不是 `2` 的幂会怎样"，后者才是区分度所在。
**Q2**（判断）`for (String s : list) { if ("b".equals(s)) list.remove(s); }`，其中 `list = new ArrayList<>(List.of("a", "b", "c"))`。这段代码在单线程下一定抛 `ConcurrentModificationException` 吗？
答案与解析 `for-each` 被编译为 `Iterator` 循环，`list.remove(s)` 走 `ArrayList.remove(Object)`，它令 `modCount++`，而迭代器的 `expectedModCount` 仍是创建时的值；`"b"` 是中间元素，删除后循环还会再次调用 `next()`，`next()` 里的 `checkForComodification` 发现不一致即抛。 但若 `"b"` 是**最后一个**元素，删除后 `hasNext()` 返回 `false`，循环结束不再调用 `next()`，于是**不会抛** —— 这是最容易被追问的边界：`fail-fast` 不是"删了必抛"，而是"删了之后还继续迭代才可能抛"。改成 `while (it.hasNext()) { if (...) it.remove(); }` 是安全的，因为 `Itr.remove` 最后执行 `expectedModCount = modCount`；而"最后一个元素不抛"恰好说明检测是尽力而为的。
**Q3**（计算）向一个未预设容量的 `HashMap` 连续 `put` 100 万个互不相同的键，容量会经历哪些值、约多少次 `resize`？若改为 `new HashMap<>(1333334)`，第一次建表分配多大容量，全程会 `resize` 几次？
答案与解析 容量按 `2` 的幂递增，由阈值 `容量 × 0.75` 触发：`16 → 32 → … → 1048576 → 2097152`，从 `16` 到 `2097152` 共 17 次 `resize`；最终容量 `2097152` 的阈值是 `1572864 > 1000000`，装得下。次数是 `O(log n)`，但每次代价 `O(容量)`，累积仍是 `O(n)` 量级的搬运。`new HashMap<>(1333334)` 时 `tableSizeFor` 向上取整：`1333334` 介于 `2^20 = 1048576` 与 `2^21 = 2097152` 之间，得到 `2097152`，阈值 `1572864` 足以容纳 100 万键，所以**一次 `resize` 都不会发生**。错在哪：以为 `new HashMap<>(1000000)` 就够 —— 容量虽被抬到 `1048576`，但阈值是 `786432 < 1000000`，中途仍会扩容到 `2097152`；面试官会追问"预设容量的公式为什么要除以负载因子再 `+1`"。
**Q4**（设计）某服务要缓存 10 万条配置，读 QPS 约 5 万，写操作平均每分钟 1 次且为整批替换。给出容器选型与理由；若写入频率升到每秒 100 次，选型如何变化？
答案与解析 按 29.1 四问筛选：需要按键查找（`Map` 线）→ 并发安全是刚需 → 无需按 key 排序，答案是 `ConcurrentHashMap`。理由：读路径无锁（`val`/`next` 是 `volatile`），`get` 是 `O(1)` 且不阻塞；写虽少，但 `addCount` 与可能的扩容都有协助机制，不产生长停顿。如果"整批替换"成立，更优方案是"不可变 `Map` + `volatile` 引用"：构造新 `HashMap` 后一次性发布，读路径只有一个 `volatile` 读，完全无锁无竞争，代价是每次替换重建整表。 若写入升到每秒 100 次：`ConcurrentHashMap` 仍可用（写只锁单桶），但要预设容量（`容量 ≥ 预期元素数 / 0.75 + 1`）消除扩容；若是每秒 100 次全量替换，重建 10 万条的成本已不可忽略，必须回到 `ConcurrentHashMap` 或加锁重建。**绝不能用 `CopyOnWriteArrayList`/`CopyOnWriteArraySet`**：每次写复制 10 万条，每秒 100 次就是每秒 1000 万条引用的搬运。错在哪：答 `Collections.synchronizedMap`（读也加锁，5 万 QPS 下成瓶颈）；答 `Hashtable`（全方法 `synchronized`，更差）；答 `CopyOnWriteArraySet` 而被追问写入频率后无法自圆其说。
**Q5**（定位）线上偶发 `IllegalArgumentException: Comparison method violates its general contract!`，堆栈含 `TimSort.mergeLo`。给出定位步骤，并说明为什么它只在大数据量时偶发。
答案与解析 成因是比较器不满足传递性，最常见是 `(a, b) -> a.getX() - b.getX()` 的整数溢出，其次是"多字段比较漏了某条分支"或"比较时读了会变化的外部状态（当前时间、`HashMap` 遍历顺序）"。错在哪：答"数据里有重复元素"是错的，重复元素本身合法（只要比较器对相等返回 `0` 且一致传递）；答"要加 `synchronized`"也不对。 定位步骤：先检查所有比较器是否用了减法或浮点差值，统一改为 `Integer.compare`/`Long.compare`/`Comparator.comparingInt`/`Double.compare`；再缩小数据集二分出最小可复现子集；再包一层断言型 `Comparator`，缓存近期比较结果，发现 `a < b`、`b < c` 而 `a >= c` 就打印这三个元素；最后用 `-Djava.util.Arrays.useLegacyMergeSort=true` 验证是否与排序实现相关（旧归并排序不检测契约、会静默产出错误顺序，只能验证、不能修复）。 为什么大数据量才偶发：`TimSort` 会检测输入中的升序/降序 run 并据此选择归并路径。数据量小时走二分插入排序分支，不依赖传递性假设；只有进入 `mergeLo`/`mergeHi` 归并阶段（需要多个 run）才会因非全序而算出越界下标并抛异常。`MIN_MERGE = 32` 意味着长度小于 32 时根本不会走这条路径，这也解释了为什么单元测试里用小数组测不出来。
## 面试高频问题与陷阱 | 面试问法 | 考查角度 | 陷阱 / 加分点 | 对应本章小节 | |---|---|---|---| | `HashMap` 的 `hash` 方法为什么要做 `h ^ (h >>> 16)`，不做行不行？ | 扰动函数与索引位宽的关系 | 答"为了防止哈希冲突"太笼统；要点明"容量是 `2` 的幂时索引只取低位，不扰动则高位信息全丢" | 29.4.2 | | `HashMap` 的容量为什么必须是 `2` 的幂？给你一个不是 `2` 的幂的容量会怎样？ | `(n-1) & hash` 与取模的等价前提 | 只说"位运算快"不完整；必须指出非 `2` 的幂会让部分桶永远取不到（容量 15 时 `n-1 = 0b1110`，奇数桶全废） | 29.4.2、29.4.5 | | 负载因子为什么是 `0.75`，改成 `0.5` 或 `1` 会怎样？ | 时间空间折中与泊松分布 | 答"官方就这么定的"必被追问；要说出理想哈希下桶内达 8 个元素的概率约 `6 × 10⁻⁸`，以及改小则扩容频繁、改大则链表变长 | 29.4.3 | | 树化阈值为什么是 `8` 而不是 `6` 或 `10`？退化阈值为什么是 `6` 而不是 `8`？ | 两个阈值的动因与防抖动 | 只背数字会被追问到崩；要说出"8 是理想哈希下几乎不可能达到的线，6 与 8 之间的缓冲避免反复转换" | 29.4.3 | | `HashMap` 扩容时元素位置要重新计算吗？ | `hash & oldCap` 拆分原理 | 答"必须重算 `hash % newCap`"是错的；正确是"一次位与即可判断留原位还是迁到 `j + oldCap`，因为新容量仍是 `2` 的幂" | 29.4.5 | | 为什么在 `for-each` 里 `list.remove()` 会抛异常，而 `Iterator.remove()` 不会？ | `modCount` 与 `expectedModCount` 的对齐 | 答成"并发问题"直接踩坑；要说出 `Itr.remove` 最后执行 `expectedModCount = modCount`，并知道删最后一个元素时不抛 | 29.2.2 | | `ConcurrentHashMap` 在 JDK 8 为什么放弃分段锁？ | 锁粒度与并发度的演进 | 答"分段锁性能差"太浅；要说出"并发度被段数写死、每段都要额外分配 `HashEntry` 数组与锁对象、内存开销大" | 29.5.1、29.5.2 | | `ConcurrentHashMap` 的 `get` 为什么可以不加锁？ | `volatile` 字段与弱一致读 | 答"用了 `CAS`"是错的（`get` 不做 `CAS`）；要点出 `val`/`next` 是 `volatile`、`tabAt` 用 `getObjectVolatile`，代价是弱一致 | 29.5.2 | | `CopyOnWriteArrayList` 适合什么场景？它的迭代器为什么不抛 `ConcurrentModificationException`？ | 写时复制的成本与弱一致迭代器 | 答"线程安全的 List 就用它"是典型踩坑；必须说出写是 `O(n)` 复制、内存短暂翻倍、迭代器基于快照永不抛也看不到新元素 | 29.6 | | `TreeMap` 能用 `hashCode` 去重吗？两个 `compareTo` 返回 `0` 但 `equals` 为 `false` 的对象会怎样？ | 比较器语义与 `Map` 契约 | 答"和 `HashMap` 一样用 `hashCode`"错；正确是"靠 `compare` 导航，返回 `0` 即视为同一个键，后者覆盖前者" | 29.7.2 | | 怎么用 `LinkedHashMap` 实现 LRU？`accessOrder` 是什么作用？ | 钩子方法与 LRU 淘汰 | 只写继承与构造器不够；要说清 `afterNodeAccess` 移到尾部、`afterNodeInsertion` 里 `removeEldestEntry` 返回 `true` 才删表头 | 29.7.3 | | 为什么 `Arrays.sort(Object[])` 用 `TimSort` 而 `Arrays.sort(int[])` 用双轴快排？ | 稳定性需求与基本类型语义 | 答"因为快排更快"不完整；要说"基本类型没有身份，稳定性无意义；对象数组按字段排序时相等元素的原有次序有语义" | 29.8 | | `Comparison method violates its general contract` 是怎么产生的？怎么定位？ | 比较器传递性与归并优化的依赖 | 答"数据有重复元素"是错的；要说出传递性被违反（常见是减法溢出），以及用断言型比较器打印违规三元组 | 29.8 | | `fail-fast` 的 `ConcurrentModificationException` 在并发下一定能被发现吗？ | `modCount` 非 `volatile` 与尽力而为语义 | 答"能，它会抛异常保护数据"错；正确是"`modCount` 不是 `volatile`，没有 happens-before 保证，规范也只承诺尽力而为" | 29.9 | ## 延伸阅读 - Oracle《Java SE API 文档》`java.util.HashMap`、`ConcurrentHashMap`、`ArrayList`、`LinkedHashMap`、`Arrays` 各节，特别是 `HashMap` 类注释中泊松分布概率表的原文。 - Oracle《Java Platform, Standard Edition 8 文档》集合框架（Collections Framework）概览与 "Concurrent Collections" 一节。 - OpenJDK 源码 `java.base/java/util/` 下 `HashMap.java`、`ConcurrentHashMap.java`、`ArrayList.java`、`LinkedHashMap.java`、`TreeMap.java`、`TimSort.java`。 - OpenJDK 源码 `java.base/java/util/Arrays.java` 与 `DualPivotQuicksort` 的双轴快速排序实现。 - Joshua Bloch《Effective Java》第 3 版第 11 条（遵守 `equals`/`hashCode` 契约）与第 3 章关于集合、`Comparator` 的条目。 - 第 28 章 28.2 节（`equals`/`hashCode` 契约）、第 30 章 30.1~30.3 节（happens-before、`volatile`、`synchronized`）、第 32 章 32.4 节（弱引用与 `WeakHashMap`）。 --- > 作者: [破戒僧](https://onlyblacktea.cn) > URL: https://onlyblacktea.cn/book/backend/ch29/