4.1 集合选型与遍历删元素事故

4.1 集合选型与遍历删元素事故

本节摘要：foreach 里调 remove 抛 ConcurrentModificationException，是 Java 工程师的"成人礼"。本节从一次风控批量清洗事故讲清 fail-fast 的 modCount 机理、三种安全删除写法、ArrayList 与 LinkedList 的复杂度真相、HashMap 从链表到红黑树的演化，最后给一张选型决策图。

事故现场：批量清洗跑到一半崩了

风控的批量清洗任务处理黑名单，几十万条数据跑到第 3 万条抛异常中断：

List<String> blacklist = loadBlacklist();
for (String deviceId : blacklist) {          // foreach 语法糖 = 迭代器
    if (expired(deviceId)) {
        blacklist.remove(deviceId);          // CME 在下一次 hasNext 时爆炸
    }
}
​

ConcurrentModificationException 的堆栈指向 foreach 行，但"罪魁"其实是 remove——异常在下一次迭代检查时才抛，不是在修改当场。单测的样例只有三个元素且恰好是最后一个被删，循环结束前没有"下一次迭代"，于是测过了。数据量上来后必炸。

fail-fast 的机理：modCount

ArrayList 内部维护一个 modCount（结构修改计数）。迭代器创建时记住当时的值 expectedModCount，每次推进迭代都检查两者是否相等；而集合自身的 remove 只增加 modCount，不更新迭代器的期望值，检查一旦失配立即抛 CME。

// ArrayList.Itr 的核心逻辑（简化）
public E next() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    // ... 返回元素
}
​

这个设计叫 fail-fast：宁可快速失败，不让迭代器在无声的 inconsistent 状态上继续跑。要认清两点——其一，CME 是"尽力而为"的守护，规范并不保证准时抛出，绝不能把它当并发安全机制；其二，单线程下的结构修改同样触发，它管的是"迭代期结构不变"这个假设。

更阴的版本是不抛异常但漏删：用普通 for 循环 + 下标删除时，删除使后续元素整体左移，而 i 继续自增，正好跳过下一个元素。连续两个过期条目挨着，第二个就被漏掉——没有异常，数据悄悄不对。第 1 章 1.3 节的 i-- 补丁就是对着这个坑打的，但补丁脆弱（换成迭代器或 removeIf 才是终点）。

三种正解

// 1. 迭代器自己的 remove 会同步 expectedModCount
for (Iterator<String> it = blacklist.iterator(); it.hasNext(); ) {
    if (expired(it.next())) it.remove();
}

// 2. JDK 8+ 一行 最推荐
blacklist.removeIf(this::expired);

// 3. 倒序下标删除 左移不影响已遍历过的前缀
for (int i = blacklist.size() - 1; i >= 0; i--) {
    if (expired(blacklist.get(i))) blacklist.remove(i);
}
​

removeIf 是首选：语义直白、批量移动一次完成（迭代器版每删一个移动一次，O(n²)）。

ArrayList vs LinkedList：教科书与现实的落差

复杂度表上 LinkedList 的"O(1) 插入"很诱人，但现实里几乎总该选 ArrayList，原因有三：CPU 缓存友好（连续内存 vs 每元素一个节点对象，缓存命中率高数倍）；每个节点 40 字节级别的额外指针与对象头开销；所谓 O(1) 插入的前提是你已经持有那个位置的节点——按值定位还是要 O(n) 遍历。LinkedList 的真实适用面窄到几乎只剩"当双向队列用"（头尾 O(1)），而这个场景 ArrayDeque 性能通常更好。选型默认值：ArrayList，需要队列用 ArrayDeque，需要键值对按场景选 Map 实现。

HashMap：从链表到红黑树

JDK 8 起 HashMap 的桶内链表长度到 8 且表长不小于 64 时树化为红黑树，查询从 O(n) 降到 O(log n)——这是对"哈希函数太差或攻击者构造碰撞键"的兜底（第 2 章"全员同桶"的退化场景有了保险）。但树化是兜底不是目标，键的 hashCode 分布良好时几乎不触发。扩容方面，默认容量 16、负载因子 0.75，预估元素量时用 new HashMap<>(expected / 0.75f + 1) 或 JDK 19+ 的 newHashMap(预期量) 一步到位，避免从 16 一路翻倍扩容七八次——每次扩容都要重散列全部元素。

集合选型决策图

Collections 工具与不可变集合

日常三件套：sort/reverse 排序，unmodifiableList 包只读视图，emptyList/singletonList 避免为返回值分配。注意 unmodifiableXxx 是视图不是拷贝——原集合变了视图跟着变，要真快照用 List.copyOf（JDK 10+）。返回集合给别人用时包一层只读，能把"下游误改"这类耦合事故扼杀在类型系统里。

⚠️ 常见坑：把 Arrays.asList 的结果当 ArrayList。它是数组的固定长度视图，add 直接抛 UnsupportedOperationException；而 ArrayList 子类的 remove 又会引发 CME——两个长得很像的类，坑完全不同。

💡 关键直觉：迭代器隐含的契约是"遍历期间结构不变"。所有边遍历边改的代码，都在赌编译器和运气，removeIf 一行收编全部场景。

防坑清单

• 删除元素统一 removeIf，代码评审见迭代中调集合自身 remove 直接打回
• 单测数据要覆盖"连续命中删除条件"的序列，防漏删静默错
• 大小可预估的 HashMap 构造时给容量，免翻倍扩容
• List 默认 ArrayList，队列用 ArrayDeque，LinkedList 不进新代码
• 返回给外部的集合包只读视图或拷贝快照

本节要点回顾

• CME 机理：modCount 与 expectedModCount 失配，延迟到下一次迭代检查抛出
• 静默漏删：下标循环删除的左移跳位，无异常更危险
• 正解：removeIf / 迭代器 remove / 倒序删除，首选 removeIf
• 选型真相：缓存友好压倒复杂度表，ArrayList 与 ArrayDeque 是默认答案
• HashMap：树化是兜底，预分配容量是常规优化

下一节看字符串——最常用的类，也最容易被"随便拼一拼"。