从 HashMap 到 ConcurrentHashMap：不只背数组、链表和红黑树

HashMap 是 Java 面试的高频入口，因为一个问题可以同时考察数据结构、位运算、对象契约和并发。

一次 put 发生了什么

在 JDK 8 中，HashMap 的核心结构可以概括为“数组 + 链表 + 红黑树”。写入键值对时，会先根据 key 计算 hash，再使用数组长度定位桶。如果桶为空就直接写入；如果发生冲突，则比较 key，并在链表或红黑树中继续查找。

数组长度通常保持为 2 的幂，使下面的位运算可以代替取模：

index = (length - 1) & hash;

这不仅计算快，也有利于扩容后元素重新分布。

为什么需要扩容

桶中冲突越来越多时，查询会逐渐退化。HashMap 使用容量和负载因子控制扩容时机，默认负载因子 0.75 是空间与冲突概率之间的折中。

扩容不是免费的：它会分配新数组并迁移节点。因此，如果能够预估数据规模，初始化时给出合理容量，可以减少运行中的扩容成本。

为什么线程不安全

问题不只是“它没有加锁”。多个线程同时写入时，可能出现覆盖、丢失更新，以及扩容期间状态不一致。即使每个线程写入不同的 key，也可能竞争相同桶或共同修改结构。

只读场景并不等于绝对安全：前提是 Map 已经安全发布，之后不再发生写入。

ConcurrentHashMap 做了什么

JDK 8 的 ConcurrentHashMap 通过 CAS、桶级 synchronized 和并发协作扩容降低锁粒度。它避免对整个 Map 使用一把大锁，使不同桶上的操作可以并发执行。

但“线程安全容器”不代表组合操作自动安全：

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

检查和写入仍是两个步骤。应使用 putIfAbsent、computeIfAbsent 等原子 API 表达意图。

我的记忆方式

回答 HashMap 时按四层展开：它是什么、为什么快、如何处理冲突、并发下会怎样。这样既能覆盖基础问题，也能自然进入容量规划、缓存和线程安全等真实工程场景。