集合框架深度实践：契约、HashMap 核心机制、遍历一致性与并发选择

新手先看 · 一屏速览

• List 保序可重复；Set 去重；Map 做键值映射（键相等由 equals/hashCode 决定）
• HashMap：装载因子默认 0.75；桶上冲突链超过阈值后树化（红黑树）
• 迭代是弱一致并带 fail-fast；并发下使用并发集合，避免用锁封装普通集合

1. 接口体系与等价合同（Contract）

• List：顺序与索引；ArrayList（动态数组，随机访问 O(1)） vs LinkedList（链表，随机访问 O(n)）
• Set：去重；HashSet 基于 HashMap，TreeSet 基于红黑树（需 Comparator/Comparable）
• Map：键等价由 equals/hashCode 合同决定；LinkedHashMap 维护插入/访问顺序；TreeMap 有序（O(logN)）
• equals/hashCode 合同要点：相等对象哈希必须相等；字段应保持不可变以保证键稳定

工程建议：

• 作为 Map 的键，优先使用不可变对象；为 equals/hashCode 使用重要字段并保持对称/传递/一致

2. HashMap 工作原理

• 哈希扰动（hash spread）→ 定位桶（table）→ 冲突以链表/树存储
• 装载因子（默认 0.75）控制扩容阈值；当单桶链表长度超过阈值（默认 8）且容量足够时树化
• 树化结构为红黑树，极端冲突时退化风险可控；小规模时链表更轻量

深入：

• 容量恒为 2 的幂，定位桶可用位与（(n - 1) & hash）加速
• 扩容再分配：节点要么留在原位，要么移动到 index + oldCap（高位优化）
• computeIfAbsent 可能导致函数重复执行或递归调用时死锁，注意复杂函数副作用

3. 遍历与 fail-fast

for (Iterator<Map.Entry<K,V>> it = map.entrySet().iterator(); it.hasNext();) {
  var e = it.next();
  // it.remove(); // 合法
  // map.remove(e.getKey()); // 可能触发 ConcurrentModificationException
}

• 迭代器持有 expectedModCount；结构被非迭代器修改触发 ConcurrentModificationException（快速失败）
• 并发场景：使用并发集合（CHM/CopyOnWrite...）或在遍历前构造快照（如 List.copyOf）

4. 不可变与只读视图

• List.copyOf/Set.copyOf/Map.copyOf（JDK 10+）创建真正不可变副本
• Collections.unmodifiableXXX 创建只读视图：底层集合若泄漏，仍可能被修改

5. 并发集合与选择

最近建一些几十个工作内推群，各大城市都有，群里目前已经收集了很多内推岗位，大厂、中厂、小厂、外包都有。 欢迎HR、开发、测试、运维和产品加入。

扫描下方微信，备注：网站+所在城市，即可拉你进工作内推群。

• ConcurrentHashMap：桶级 CAS/锁，Java 8+ 用树化与节点级别同步，遍历弱一致
• CopyOnWriteArrayList：读多写少；写时复制开销随规模增大；迭代无锁且强一致快照
• ConcurrentSkipListMap：基于跳表，有序且并发友好；适合需要排序视图的并发场景

6. 基准与工程策略

• 读写比例决定选型：读多写少用 COW/快照；高并发写使用 CHM，避免全局锁
• 避免依赖 HashMap/HashSet 遍历顺序（无序语义）；需要顺序选 LinkedHashMap/TreeMap
• JMH 基准校准：测量不同规模、命中/冲突分布下的 put/get/remove；关注 GC 与装箱

7. 实战清单与反模式

• 清单：Map 键使用不可变对象；equals/hashCode 合同完整；对外暴露不可变视图
• 清单：迭代中修改使用迭代器方法；并发使用并发集合；明确顺序需求
• 反模式：在迭代中结构性修改底层集合；依赖 HashMap 顺序；在并发场景用 HashMap + 外层锁粗暴包裹

8. 练习

1. 实现 LRU（基于 LinkedHashMap 的 accessOrder = true + removeEldestEntry）
2. 用 JMH 比较 ArrayList vs LinkedList 在“随机访问/尾插/头插/中间插入/迭代删除”的性能
3. 为某业务键设计 equals/hashCode，并生成冲突分布报告，优化散列策略