前言

Java 集合的选型应服务于访问模式、数据规模、内存约束和并发边界，而不是只比较时间复杂度。本文从 List、Set、Map 到 HashMap 和并发容器，说明底层机制、常见误区以及如何把源码知识落到实际业务代码中。

集合题要回答“为什么这样选”

集合面试不应只背 ArrayList、HashMap 的源码细节。实际需要根据访问模式回答：是否按下标访问、是否大量头尾插入、是否要去重或排序、是否并发、元素规模和内存上限是什么。集合是进程内数据结构，不能替代数据库索引、缓存或跨实例协调。

需求	常见选择	原因与边界
顺序遍历、尾部追加、按下标读取	`ArrayList`	连续数组，随机访问快；中间插入/删除要移动元素
双端队列	`ArrayDeque`	数组环形队列，通常优于旧 `Stack`/`LinkedList`
去重且不要求顺序	`HashSet`	底层通常是 `HashMap` 的 Key 集合
Key 精确查找	`HashMap`	平均 O(1)，依赖正确 `hashCode`/`equals`
按 Key 排序或范围查询	`TreeMap` / `TreeSet`	红黑树，O(log n)，支持 `subMap` 等范围视图
保留插入顺序	`LinkedHashMap`	双向链表维护顺序，可实现 LRU
高并发 Key-Value	`ConcurrentHashMap`	避免全表锁，仍要保证复合业务操作原子性

List、Queue 与 Set

ArrayList 是可扩容数组。读取 get(index) 为 O(1)，尾部追加通常为摊销 O(1)，扩容时会复制数组，因此批量已知规模时应预设容量。遍历时删除元素要使用 Iterator.remove() 或倒序遍历，不能在增强 for 循环中直接 list.remove()，否则通常触发 ConcurrentModificationException。

LinkedList 每个元素多出前后指针对象，CPU 缓存局部性较差。它只有在已持有节点位置时删除有优势，而 Java 日常业务往往先按下标找位置，仍要线性遍历。队列优先选 ArrayDeque；并发阻塞生产消费选 BlockingQueue。

HashSet 不保证顺序。需要稳定展示顺序选择 LinkedHashSet；需要排序或范围选择 TreeSet。将可变对象放入 HashSet/HashMap Key 后，若修改参与 hashCode/equals 的字段，对象可能再也找不回来，因此 Key 应不可变，例如 String、Long 或不可变值对象。

HashMap 的核心链路

HashMap 的数组槽位称为 bucket。插入时通过扰动后的 hash 与 (n - 1) 计算桶下标；桶中先比较 hash，再比较 equals。冲突较少时桶内是链表；JDK 8 中桶节点数量达到阈值且数组容量足够时会树化为红黑树，降低严重碰撞下的查找复杂度。

1
2
3

key -> hashCode -> 扰动 hash -> (table.length - 1) & hash -> bucket
                                              |
                                   Node 链表或 TreeNode 红黑树

机制	要点	生产意义
初始容量	默认 16，容量保持 2 的幂	位运算定位 bucket；预估大批量数据应指定容量
负载因子	默认 0.75	阈值为 capacity * loadFactor，过高冲突增多，过低浪费内存
扩容	容量通常翻倍，节点重新分布	会分配新数组并迁移，业务高峰大量扩容可能造成延迟尖刺
JDK 8 迁移	节点要么留在原索引，要么移动到 `oldIndex + oldCap`	因为新增的高位 bit 决定位置，不必重新完整计算 hash
树化	默认链长至少 8 且表容量至少 64	小表优先扩容，避免因偶然冲突过早树化

equals 与 hashCode 必须满足：两个对象 equals 为 true，则 hashCode 必须相同。相同 hash 不要求 equals 为 true。重写一个必须同时重写另一个；持久化实体不要只用可能为空、后续会改变的数据库 ID 参与哈希。

ConcurrentHashMap 与并发边界

JDK 8 的 ConcurrentHashMap 以数组桶为基础，读操作大多无锁，写入通过 CAS 和桶粒度同步协作；扩容期间多个线程可协助迁移。它不允许 null Key/Value，因为并发场景下无法区分“Key 不存在”和“Value 为 null”。

1 2	// 原子地为一个 Key 初始化值，避免 get-then-put 竞态。 counterMap.computeIfAbsent(userId, ignored -> new LongAdder()).increment();

但 ConcurrentHashMap 只保证其单个方法或 compute 系列的原子性。下面的“先查再改”不是原子操作：

1
2
3

if (!map.containsKey(orderId)) {
    map.put(orderId, value);
}

跨 Map、数据库、缓存的业务幂等必须依赖唯一约束、条件更新、事务或可靠消息，不能只依赖 JVM 内 Map。Collections.synchronizedMap 是全局锁包装，简单场景可用，但高并发下通常不如 ConcurrentHashMap；迭代时仍需要按其文档要求自行同步。

fail-fast、弱一致与不可变

大多数普通集合的迭代器是 fail-fast：遍历期间发现结构性修改会尽力抛 ConcurrentModificationException。这是错误检测，不是并发安全保证，不能依赖它实现控制流程。

ConcurrentHashMap 的迭代器是弱一致的：遍历可与更新并发，不抛 fail-fast，但可能看见部分新数据或旧数据。CopyOnWriteArrayList 每次写复制底层数组，读迭代无锁且稳定，适合“读多写极少”的监听器列表；写多时复制成本和内存峰值很高。

List.of()、Set.of()、Map.of() 返回不可变集合，适合配置、常量和跨层传递的只读结果。Collections.unmodifiableList(list) 只是只读视图，原始 list 被修改后视图仍会变化；二者不要混淆。

生产选型与排查

内存集合的主要风险不是某个方法慢，而是无上限增长。例如用 HashMap 存所有在线用户、所有幂等记录、所有导出任务，实例重启即丢失，流量上涨又会 OOM。此类数据应明确 TTL、最大容量和淘汰策略，必要时放 Redis、数据库或专用缓存。

排查集合引起的内存问题时，使用 Heap Dump 查看 dominator tree，确认是 HashMap$Node[]、ArrayList.elementData 还是业务 Value 持有大对象；再追踪 Key 是否无界、是否没有删除、是否缓存了完整响应/实体图。不能只通过增大堆规避。

高频面试题

问题	回答要点
HashMap 为什么容量是 2 的幂？	可用 `(n - 1) & hash` 快速且较均匀定位桶，扩容时节点迁移也更高效。
HashMap 链表为什么会树化？	防御大量 hash 冲突导致的线性查找；小表先扩容，容量足够才树化。
HashMap 线程安全吗？	不安全，并发写可能产生数据丢失或结构问题；使用 ConcurrentHashMap 或外部同步。
ArrayList 和 LinkedList 怎么选？	大多数随机访问/遍历/尾插选 ArrayList；队列选 ArrayDeque，不因“链表插入快”盲选 LinkedList。
ConcurrentHashMap 能保证库存扣减吗？	不能跨进程且不能覆盖数据库事务；它只适合进程内并发数据结构。