Java 集合原理:ArrayList、CopyOnWriteArrayList 与 HashMap
选择集合不能只记住 API。底层数据结构决定了扩容成本、访问复杂度、并发行为和内存占用。
ArrayList:动态数组
ArrayList 使用连续数组保存元素,因此按下标访问是常数时间。尾部追加在容量足够时也很快;在中间插入或删除则需要移动后续元素。
为什么指定初始容量
数组容量不足时,需要创建更大的数组并复制旧元素。已知大致元素数量时,设置初始容量可以减少复制和短生命周期数组。
常见 HotSpot/JDK 实现中,扩容会以旧容量加上一半作为候选新容量,然后再确保能够容纳本次新增元素。这里的 1.5 倍是实现策略,不是 List 接口契约,代码不应依赖具体倍数。
线程安全边界
ArrayList 不保证并发修改安全。多个线程同时 add 可能覆盖位置或在扩容期间观察到不一致状态。
解决方案取决于访问模式:
- 外部锁保护一组复合操作;
- 使用同步包装集合;
- 使用适合场景的并发集合;
- 避免在线程之间共享可变列表。
“单次读取没有报错”并不表示并发读写安全。
CopyOnWriteArrayList:写时复制
CopyOnWriteArrayList 的写操作在锁保护下复制底层数组,在新数组上修改,然后发布新引用。读取通常不需要获取写锁,可以稳定遍历某个数组快照。
它适合:
- 读取远多于写入;
- 集合规模不大;
- 允许迭代器看到稍旧快照;
- 写延迟和复制成本可接受。
它不适合高频写入或超大集合,因为每次写入都可能复制整个数组。它的迭代器是快照视图,不应被误解为实时一致视图。
HashMap:桶数组与冲突结构
HashMap 通过 Key 的哈希值定位桶。理想情况下查找接近常数时间,但不同 Key 可能落到同一个桶,因此必须处理冲突。
现代 JDK 的常见实现使用:
- 桶数组;
- 桶内链表;
- 冲突较严重且数组容量足够时使用红黑树。
查找大致经历:
- 计算并扰动哈希值;
- 根据数组长度定位桶;
- 比较桶首节点;
- 沿链表或树继续查找;
- 使用哈希和
equals判断 Key 相等。
为什么数组长度通常是 2 的幂
当长度为 2 的幂时,可以用位运算定位桶:
index = (length - 1) & hash;扩容为两倍后,节点要么留在原位置,要么移动固定偏移,重新分配可以利用原哈希的一个新增高位。
负载因子
负载因子决定容量使用到什么程度时扩容。默认值是在冲突概率和空间占用之间的通用折中,不意味着任何数据分布下都最优。
若 Key 的哈希分布很差,即使容量很大也会产生严重冲突。正确实现 hashCode 与 equals 比盲目调整容量更重要。
树化不是只看链表长度
常见实现会在桶内节点达到阈值且整个数组容量足够时树化;容量太小时优先扩容。这样可以避免在整体元素很少、只是数组过小的情况下过早引入树结构。
这些阈值属于具体实现细节,业务逻辑不应依赖它们。
可变 Key 是常见陷阱
如果 Key 参与 hashCode 或 equals 的字段在放入 Map 后被修改,再用修改后的对象查询可能找不到原条目。
因此适合作为 Key 的对象通常应当:
- 值语义清晰;
- 相等性实现一致;
- 放入 Map 后保持不可变。
HashMap 也不是并发集合
多个线程并发修改 HashMap 没有安全保证。需要并发访问时,应根据复合操作选择 ConcurrentHashMap 或外部同步。
即使使用并发 Map,“先检查不存在,再写入”仍可能有竞态,应该使用 putIfAbsent、computeIfAbsent 等原子复合操作。
选择集合的简单判断
| 场景 | 更合适的起点 |
|---|---|
| 按下标读取、尾部追加 | ArrayList |
| 读极多、写极少、允许快照 | CopyOnWriteArrayList |
| Key 到 Value 映射、单线程或外部同步 | HashMap |
| 多线程共享映射 | ConcurrentHashMap |
集合选择没有脱离访问模式的标准答案。先明确读写比例、数据规模、一致性和并发边界,再决定实现。