第 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” 并说明成因。

前置知识检查

29.1 集合框架的两条线

java.util 分两条互不重叠的线：Collection 存单个元素，Map 存键值对。Map 不继承 Collection，因为按键查找的 remove、contains 语义无法与单元素容器统一。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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 节）

选容器时按四个问题依次问下来，顺序不能颠倒 —— 前一个答案会否决后面的选项：

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 是折中。

1
2
3

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 个槽位。

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() 删除后把两者重新对齐，还要修游标：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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²)。

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)“在实践里几乎从不成立，有四个独立可追问的原因：

实际取舍：只在两端增删时用 ArrayDeque（它不实现 List，没有索引访问），需要频繁中间插入时先追问"能否改成头尾操作”，不能则考虑 ArrayList 批量重建或 LinkedHashMap 按键定位；栈与队列一律用 ArrayDeque，不要用 Stack（继承 Vector、方法全 synchronized，且迭代顺序是反的）。ArrayDeque 容量是 2 的幂，头尾操作都 O(1)：

1
2
3
4
5

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

29.4 HashMap：完整实现

29.4.1 数据结构

JDK 8 起是"数组 + 链表 + 红黑树"，Node 有 hash、key、value、next 四个字段，hash 缓存扰动后的值以避免每次比较重算。

1
2
3
4
5
6
7

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 扰动函数与索引计算

1
2
3
4
5
6

// 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 的幂：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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 五个字段，容量小时树化得不偿失。

29.4.4 put 的完整流程

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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：

1
2
3
4
5

以 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 向上取整后仍有富余。

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 主干是一个自旋循环，按桶的当前状态分四种情况：

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

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<K,V>[] table；tabAt 用 Unsafe.getObjectVolatile 读，保证看到最新发布的元素，沿 next 继续走也是 volatile 读，链表中的节点其字段初始化已完成（volatile 写对 volatile 读建立 happens-before，见第 30 章 30.1 节）。代价是 get 返回弱一致结果 —— 可能读到旧值，也可能在扩容中途被 ForwardingNode 指引到新表，换来的是完全无阻塞的读路径。

29.6 CopyOnWriteArrayList 的适用边界

写时复制（copy-on-write, COW）在这里是"复制整个数组 + 修改副本 + 用 volatile 写换掉引用"，所有写操作在独占锁内完成，读直接读那个引用：

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

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，也看不到迭代期间的新增元素。

29.7 TreeMap、红黑树与 LinkedHashMap 的 LRU

29.7.1 红黑树的五条性质与调整

由性质 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 缓存只需：

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

public class LruCache<K, V> extends LinkedHashMap<K, V> {
    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<K, V> eldest) {
        // 返回 true 时父类会 remove 掉链表头节点，即最久未被访问的那个
        return size() > maxSize;
    }
}

三点要说清：它不是线程安全的，父类没有任何同步；被淘汰的条目若被外部引用持有，内存仍不释放；LinkedHashMap 的迭代顺序由这条链表决定，所以 LinkedHashSet 能同时满足"去重 + 保留顺序"，且插入查询都是 O(1)，比 TreeSet 的 O(log n) 便宜。

29.8 排序：Arrays.sort 与 Collections.sort

同名方法在 JDK 里对应四套算法，分界线是"排基本类型还是对象"：

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"：

1
2

// 错误写法：整数溢出后符号翻转，传递性直接崩掉
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 只是"尽力而为"（best-effort）：modCount 是普通 int，不是 volatile，因此线程 A 的迭代器读 modCount 时可能读到线程 B 修改前的旧值（没有 happens-before 保证，见第 30 章 30.1 节）而检测不到修改；反过来，单线程里通过集合自身方法修改则一定能检出 —— 这才是它的主要价值。JLS 与 Javadoc 都明确它不保证一定检出，只用于发现 bug。

本章小结

自测题

Q1（推导）容量为 16 的 HashMap 中某 key 扰动后哈希的低 8 位是 0b1010_1101。写出扩容前后的桶索引，判断该节点是否迁移。若容量改成 15，(n-1) & hash 还等价于取模吗？

Q2（判断）for (String s : list) { if ("b".equals(s)) list.remove(s); }，其中 list = new ArrayList<>(List.of("a", "b", "c"))。这段代码在单线程下一定抛 ConcurrentModificationException 吗？

Q3（计算）向一个未预设容量的 HashMap 连续 put 100 万个互不相同的键，容量会经历哪些值、约多少次 resize？若改为 new HashMap<>(1333334)，第一次建表分配多大容量，全程会 resize 几次？

Q4（设计）某服务要缓存 10 万条配置，读 QPS 约 5 万，写操作平均每分钟 1 次且为整批替换。给出容器选型与理由；若写入频率升到每秒 100 次，选型如何变化？

Q5（定位）线上偶发 IllegalArgumentException: Comparison method violates its general contract!，堆栈含 TimSort.mergeLo。给出定位步骤，并说明为什么它只在大数据量时偶发。

面试高频问题与陷阱

延伸阅读

• 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）。