一、 引言：数据结构中的“常青树”

在 Java 开发中，HashMap 与 ConcurrentHashMap 是使用频率极高的核心结构。开发者常常面临着一个核心矛盾：极致的读写性能 vs. 严苛的线程安全。本文将从底层构建原理、扩容机制、并发实现细节等维度，全面深度拆解这两大核心字典类。

---

二、 HashMap：单线程下的高性能王者

HashMap 追求单线程环境下的极致查询与插入性能。它经历了 JDK 1.7 到 JDK 1.8 的底层重构。

1. 核心底层结构演进

• JDK 1.7：数组 + 链表（拉链法）
  采用哈希表原生拉链法解决哈希冲突。发生碰撞的元素挂在同一槽位的链表下。
• JDK 1.8 引入红黑树：数组 + 链表 + 红黑树
  为了解决极端哈希冲突下，链表过长导致查询时间复杂度从 O(1) 退化为 O(n) 的问题，JDK 1.8 规定：当链表长度 > 8 且数组容量 >= 64 时，链表转化为红黑树，将最坏情况下的时间复杂度严控在 O(log n)。

2. 深入理解哈希路由机制与扰动函数

计算 key 应放在数组哪个位置的首要步骤是计算哈希值。JDK 1.8 源码中的扰动函数 (h = key.hashCode()) ^ (h >>> 16) 极其精妙：

• 痛点：由于数组初始容量通常较小（如 16），在执行位运算 (n-1) & hash 时，只有低位参与运算。低位相同但高位不同的 Hash 极易引发频繁碰撞。
• 破局：将原本的 32 位 Hash 值无符号右移 16 位后，再与原值进行异或运算。此操作将高 16 位的特征混合进低 16 位，即使只截取低位，也包含了对象全方位的特征，使得分布极度均匀。

3. HashMap 的 put 核心流程 (JDK 1.8)

1. 计算 Hash：运用扰动函数加工得到最终 hash 值。
2. 初始化：若哈希表 table 为空，执行 resize() 初始化。
3. 计算下标：执行 i = (n - 1) & hash 得到槽位。
4. 无冲突直连：若槽位为空，直接构建 Node 填入。
5. 处理冲突：
   • 若 Key 完全相同，直接覆盖。
   • 若节点为 TreeNode，转入红黑树插入逻辑。
   • 若为普通链表，采用尾插法遍历追加。若追加后长度达到 8，触发树化校验 treeifyBin()。
6. 扩容检测：最后判断 size 是否超过扩容阈值 threshold，若超越则 resize()。

4. 扩容极致优化与死循环的终结

• 头插法 vs 尾插法：
  JDK 1.7 扩容使用头插法，在多线程并发扩容时极其容易造成链表元素的指针反转，形成环形链表。一旦触发 get 遍历，直接导致 CPU 100%。JDK 1.8 彻底改用尾插法，保障了扩容后节点相对顺序不变，消灭了死循环。
• 高低位指针平移 (JDK 1.8 优化)：
  由于扩容固定为旧容量的 2 倍。迁移数据时，无需每次重新进行 Hash 取模运算。只需判断原节点 hash 值中参与新下标计算的那个高位是 0 还是 1（即 hash & oldCap）：
  • 若为 0，节点继续留在原索引位置。
  • 若为 1，节点迁移至原索引 + 旧数组容量的新位置。

---

三、 ConcurrentHashMap：并发环境的守护神

多线程下 HashMap 会出现数据覆盖，ConcurrentHashMap 为此而生。

1. JDK 1.7：分段锁 (Segment)

将数组划分为多个 Segment（本质是可重入锁 ReentrantLock），每个 Segment 掌管一部分哈希桶。

2. JDK 1.8：CAS + synchronized

彻底废弃 Segment，底层架构与 HashMap 1.8 保持一致（数组+链表+红黑树）。并发控制改由 CAS 乐观锁 + synchronized 悲观锁 实现：

• 极速无锁插入：当对应哈希槽位为空时，利用 Unsafe 类的 CAS 操作进行无锁化插入。
• 极限粒度加锁：产生哈希碰撞时，利用 synchronized 直接锁定该哈希桶的头节点 (Node)。只要不操作同一槽位，完全无竞争。
• 协同扩容 (Help Transfer)：扩容时如遇其他线程做 put，若侦测到槽位标有 ForwardingNode (-1)，其他线程不会阻塞，而是加入共同协助原线程转移数组元素，transferIndex（初始值是旧数组的长度 $n$）从后给线程分区域，体现极致的压榨 CPU。

---

四、 面试真题直击

1. 为什么 HashMap 的容量（Capacity）必须是 2 的 n 次幂？

答：为了极致的位运算性能与完美的哈希散列。
在计算元素该落入哪个数组下标时，原本的逻辑是取模：hash % n。但 CPU 做除法取模的指令周期非常长。如果将容量 n 限制为 2 的幂次方（如 16），那么 n - 1 的二进制必然是全 1 的形态。此时，取模运算 hash % n 可以完美等价替换为按位与运算 hash & (n - 1)。这不仅将路由计算性能提升了近十倍，还能确保 Hash 值的低位特征被完整保留。

2. 从数据结构角度，这种“数组+链表+红黑树”设计的好处是什么？

答：这是一种极限的性能折中艺术：

1. 数组的极速：通过 Hash 值映射为下标，发挥了数组内存连续、寻址最快的优点。
2. 链表的轻量：在哈希冲突较少时，单向链表的插入代价极小，节点内存开销也比树节点小得多。
3. 红黑树的兜底：如果在极端情况下全落在一个槽位，链表的 $O(n)$ 查询会拖垮系统。红黑树强行将最坏情况的时间复杂度收敛在 $O(\log n)$，作为性能的绝对护城河。

3. 既然要优化长链表，为什么选择红黑树，而非普通二叉平衡树（AVL）？

答：AVL 树是严格的平衡二叉树，查询速度最快，但代价是每次插入或删除节点时，为了维持绝对平衡，需要进行极其频繁的左旋/右旋操作。红黑树是一种弱平衡二叉树，它牺牲了一点点查询效率，但换来了在插入、删除时的极大性能提升（最多只需 3 次旋转即可恢复平衡）。对于 HashMap 这种读写都很高频的场景，红黑树是综合性能的最佳选择。

4. ConcurrentHashMap 1.8 到底通过什么方式保证线程安全？

答：它抛弃了粗粒度的 Segment 分段锁，改用了 CAS 乐观锁 + synchronized 悲观锁：

1. 无锁插入：当定位到的哈希槽为空时，直接使用底层的 Unsafe.compareAndSwapObject 进行无锁化插入。
2. 微观加锁：当槽位已经有元素（发生碰撞）时，直接使用 synchronized 关键字锁定该槽位的头节点。只要并发插入不落在同一个槽位，锁就毫无竞争。

5. Volatile 关键字在 ConcurrentHashMap 中具体起什么作用？

答：volatile 扮演了“内存可见性”的核心角色，全程支撑其 get 方法的无锁化读取：

1. 修饰 Node 的元素：Node 结构中的 val（值）和 next（指针）都被声明为 volatile。保证任何线程修改了该节点的值，其他进行 get 的线程都能瞬间从主内存中看到最新状态。
2. 修饰 Table 数组：内部的数据主体 Node<K,V>[] table 也是被 volatile 修饰的。目的是保证在发生扩容操作指向新数组时，能够立即对其他线程可见。读取数组元素时则配合使用的是 Unsafe.getObjectVolatile 底层方法。

6. 为什么 ConcurrentHashMap 严禁 Key/Value 为 Null？

答：为杜绝并发下的二义性 (Ambiguity)。在多线程中，若 get(key) 返回 null，无法确切判别是 key 不存在，还是 key 的值被显式赋为了 null。此时若用 containsKey 补测，期间状态很可能被其他线程修改，进而带来严重漏洞。因此果断一刀切禁止 null。

7.CAS的“ABA"问题

答：版本号机制。Java 提供了 AtomicStampedReference，每次修改版本号 +1。如1A->1B->2A发现不同

---

五、 特性对比总结

特征维度	HashMap (JDK 1.8)	ConcurrentHashMap (JDK 1.8)
线程安全	❌ (单线程极致性能)	✅ (高并发安全)
并发护城河	无锁	CAS + synchronized 锁头节点
扩容逻辑	高低位平移单线程搬运	多线程协同 Help Transfer 搬运
Null 支持	允许 Key 和 Value 为 Null	❌ 严禁出现 Null

---

六、 避坑建议

1. 复合操作的陷阱：ConcurrentHashMap 的单个方法是原子的，但手写的复合操作 if (!map.containsKey(k)) map.put(k, v) 会因竞态条件击穿防线，强烈建议使用原生的 computeIfAbsent() 保证复合原子性。
2. 容量预估前置：扩容及树化成本高昂，在高并发环境中，初始化时精准声明 new ConcurrentHashMap<>(initialCapacity)，是从根本上抹平性能抖动的最佳实践。

---