Java集合（三）：HashMap 与 ConcurrentHashMap 原理

导语：本篇是集合面试的重头戏——HashMap 的哈希扰动、扩容与树化原理，以及 ConcurrentHashMap 从分段锁到 CAS + 桶级锁的演进，共 16 题。

一、HashMap 原理与扩容

1. HashMap 在 JDK 1.7 与 1.8 的底层结构有何不同？

答：

• JDK 1.7：数组 + 链表。每个桶是单向链表（Entry），插入冲突节点用头插法。
• JDK 1.8：数组 + 链表 + 红黑树。链表长度 ≥ 8 且数组容量 ≥ 64 时转红黑树（查询从 O(n) 降到 O(log n)）；< 6 时退回链表。插入改为尾插法。

2. HashMap 的 put 流程是怎样的？

答： 简化流程：

1. 若 table 为空，先 resize() 初始化（默认 16）；
2. 计算 hash，定位桶 i = (n-1) & hash；
3. 桶空 → 直接放新节点；
4. 桶非空：
   • key 已存在（hash 相同且 equals 为真）→ 覆盖 value；
   • 节点是红黑树 → 按树方式插入/更新；
   • 否则遍历链表，尾插新节点；若链表长度 ≥ 8 且容量 ≥ 64 → 树化；
5. size++ 超过阈值（容量 × 0.75）→ resize() 扩容。

3. HashMap 的哈希扰动函数 hash() 做了什么？为什么？

答： JDK 1.8：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

把高 16 位与低 16 位异或，让高位也参与后续 (n-1)&hash 的运算（因为 n 较小时只有低位参与），降低哈希碰撞概率。

4. HashMap 的长度为什么是 2 的幂次方？

答： 取模定位用 (n - 1) & hash。当 n 是 2 的幂时，n-1 的二进制为全 1，& 运算等价于 hash % n 但更高效（位运算）。同时，扩容 2 倍后只需判断 hash 的第 log2(n) 位即可决定元素留在原桶还是移到 原桶+oldCap，无需重算哈希，迁移高效。

5. HashMap 的扩容机制（1.8）？为何说 1.8 扩容比 1.7 高效？

答： 默认容量 16，负载因子 0.75，阈值 = 容量 × 0.75（即 12）触发扩容，新容量 = 旧容量 × 2。

为什么负载因子是 0.75？这是时间与空间的折中：因子过小（如 0.5）哈希冲突少、查询快，但数组空闲多、空间浪费且扩容频繁；因子过大（如 1.0）空间利用率高，但哈希冲突剧增、链表/树变长、查询变慢。0.75 在统计上使冲突概率与空间利用率达到较好平衡（且 0.75 × 容量 易计算）。可按需调小以换时间、调大以换空间。

• 1.7：扩容时对每个元素重新计算 hash 并重新散列到新桶（rehash），开销大，且头插法在并发下会形成环形链表导致死循环。
• 1.8：扩容 2 倍，元素新位置只可能是 原位置 或 原位置 + oldCap。通过 (e.hash & oldCap) == 0 判断：为 0 留原桶，非 0 移 原桶+oldCap，无需重算 hash，只需拆分链表/树，效率高且改用尾插法避免了环形链表死循环。

注意：HashMap 1.8 仍非线程安全——尾插法只是消除了"死循环"，但并发 put 仍会数据覆盖、size 不准、可能抛异常，绝不能当线程安全容器用。

6. 链表转红黑树的阈值与条件？

答： 两个条件同时满足才树化：① 链表长度 ≥ 8；② 当前 table 容量 ≥ 64。若容量不足 64，优先选择扩容而非树化。树节点数 ≤ 6 时退化为链表（8 与 6 之间有缓冲，避免频繁切换）。选择 8 是基于泊松分布统计：哈希均匀时链表长度达 8 的概率极低（约千万分之六），树化是极端冲突下的兜底。

7. HashMap 为什么是线程不安全的？多线程有什么后果？

答： 非同步，并发场景问题包括：

• 数据覆盖：多线程同时 put 同一桶且都判断为空，后者覆盖前者；
• size 不准：size++ 非原子；
• 扩容丢失/异常：并发 resize 可能丢数据；
• 迭代 ConcurrentModificationException。
  线程安全替代：Collections.synchronizedMap、ConcurrentHashMap。

8. 如何线程安全地使用 HashMap？

答： 三种：

1. Collections.synchronizedMap(map)：对整个 map 加锁，读写互斥，并发低；
2. ConcurrentHashMap：分段/CAS + 细粒度锁，高并发首选；
3. 若只读场景，可构造后转 Collections.unmodifiableMap。

9. HashMap 的 get 流程？

答： 计算 hash → 定位桶 → 桶首节点 key 命中直接返回 → 若为红黑树按树查找 → 否则遍历链表用 equals 比对，命中返回值，否则返回 null。时间复杂度 O(1)（平均）/ O(log n)（树）/ O(n)（长链表，极端情况）。

二、ConcurrentHashMap

10. ConcurrentHashMap 和 Hashtable 的区别？

答： 二者都线程安全，但实现方式不同：

• Hashtable：方法级 synchronized，锁整个表，任一时刻仅一个线程能读写，并发极差。
• ConcurrentHashMap：锁粒度更细。JDK 1.7 用分段锁（Segment）；1.8 用 CAS + synchronized 锁定单个桶头节点，并发度大幅提升。
• null 支持：二者 key 都不允许 null（但 Hashtable value 也不允许，ConcurrentHashMap value 也不允许）。

11. ConcurrentHashMap JDK 1.7 的实现原理？

答： 结构为 Segment[] + HashEntry[] 链表。每个 Segment 继承 ReentrantLock，是一个独立的小 HashMap。写操作先定位到 Segment 并加锁该 Segment，不同 Segment 之间可并发。默认 16 个 Segment，理论上支持 16 个线程同时写（操作分布在不同段时）。并发度 concurrencyLevel 初始化后不可变。

12. ConcurrentHashMap JDK 1.8 的实现原理（重点）？

答： 1.8 废弃 Segment，结构与 HashMap 1.8 一致：数组 Node[] + 链表 + 红黑树。线程安全机制：

• 初始化/扩容使用 CAS（如 sizeCtl 控制状态）；
• 写单个桶时，对桶的头节点 synchronized 加锁（只锁当前桶，其他桶仍可并发）；
• 链表转红黑树逻辑同 HashMap。

这样把锁粒度从"段"降到"单个桶"，并发度更高，且读操作大多无锁（volatile 保证可见性）。

// 1.8 put 核心：仅对头节点加 synchronized
synchronized (f) { /* f 为桶的首节点 */ ... }

13. ConcurrentHashMap 1.7 与 1.8 的核心区别总结？

答：

• 1.7：Segment 分段锁（继承 ReentrantLock），结构 Segment[]→HashEntry[]；
• 1.8：取消 Segment，Node 数组 + 链表/红黑树，CAS + synchronized 桶级锁；
• 1.8 并发度更高、内存更省、支持红黑树；size() 也改用更高效的计数（baseCount + CounterCell）。

14. ConcurrentHashMap 为什么 key/value 不允许为 null？

答： 在并发环境下，若允许 null，调用 get(key) 返回 null 时无法区分"key 不存在"还是"key 对应的值为 null"，而并发集合无法用 containsKey 可靠区分（竞态下结果不可信）。为消除歧义，ConcurrentHashMap 直接禁止 null，存 null 抛 NullPointerException。（这是与 HashMap 的关键差异，面试常考。）

15. ConcurrentHashMap 的 size() 是如何高效统计的？

答： 1.8 不用单一全局计数（会成瓶颈），而是用 baseCount 记录基础数量，再用 CounterCell[] 数组分段累加各线程的增量，最终 sumCount() = baseCount + 所有 CounterCell 值。读 size() 是弱一致的大致准确值，高并发下避免加锁。

16. ConcurrentHashMap 是强一致性还是弱一致性？迭代器 fail-fast 还是 fail-safe？

答： ConcurrentHashMap 是弱一致性（最终一致）：put 后不保证其他线程立刻可见，迭代器基于弱一致性（fail-safe 风格），遍历的是某一时刻的快照/弱一致视图，不会抛 ConcurrentModificationException，但可能读不到遍历开始后最新的修改。