HashMap 源码：为什么 JDK 8 要引入红黑树？多线程扩容真的会死循环吗

填满你的记忆

649人浏览 · 2026-01-18 20:55:08

填满你的记忆 · 2026-01-18 20:55:08 发布

如果说 MySQL 是面试的半壁江山，那 HashMap 就是 Java 面试的“入门门槛”。所有的面试官都会问，但90%的人只能答到皮毛。

这一篇，我们要把 HashMap 从 JDK 1.7 到 1.8 的进化，以及 ConcurrentHashMap 的底层并发原理，像剥洋葱一样剥开。

前言：别拿“数组+链表”糊弄面试官

兄弟们，HashMap 是 Java 面试中绝对的必考题。

很多同学以为背一句“HashMap 底层是数组加链表”就能过关。但在 2026 年，这种回答只能让你去外包。

面试官真正想听的是：设计者的权衡（Trade-off）。

为什么要在 1.8 引入红黑树？
为什么加载因子是 0.75 不是 0.5？
多线程下它到底哪儿不安全了？

今天这一篇，咱们把这些“陈年老八股”彻底讲透，让你在面试场上降维打击。

Q1：简单介绍一下 HashMap 的底层数据结构？（JDK 1.7 vs 1.8）

面试官的心理活动

“这是送分题。如果你连 1.7 和 1.8 的区别都说不出来，直接 Pass。我看你能不能点出‘红黑树’这个关键词。”

你的思考路径

先说主体架构（哈希表）。
对比 1.7（纯链表）和 1.8（链表+红黑树）。
解释为什么要变（性能优化）。

✅ 参考回答

HashMap 的底层是哈希表（数组 + 链表/红黑树）。

JDK 1.7：采用 数组 + 链表。
- 当发生哈希冲突时，采用拉链法，新元素直接放在链表头部（头插法）。
JDK 1.8：采用 数组 + 链表 + 红黑树。
- 这里有一个关键的进化：当链表长度超过阈值（默认为 8）且数组长度超过 64 时，链表会自动转化为红黑树。
- 为什么要改？ 因为在极端哈希冲突下，1.7 的链表会变得很长，查询复杂度退化为 O(n)，效率极低。而红黑树查询复杂度是 O(\log n)，能保证即便哈希冲突严重，查询速度依然很快。

可能追问

问：为什么转红黑树的阈值是 8？为什么不一上来就用红黑树？
答：
- 空间换时间：红黑树节点的大小是普通链表节点的 2 倍，空间成本高。
- 概率学：根据泊松分布，在负载因子 0.75 的情况下，链表长度达到 8 的概率极低（亿分之六）。只有在极其倒霉（或者被恶意攻击）的情况下才会用到红黑树，它是用来“兜底”的。

Q2：HashMap 的 `put` 方法具体流程是怎样的？

面试官的心理活动

“这个问题考察你有没有看过源码。别给我背流程图，我要听关键细节：Hash 怎么算的？怎么找位置？什么时候扩容？”

你的思考路径

计算 Hash（扰动函数）。
定位索引（(n-1) & hash）。
判断桶是否为空 -> 只有 1 个节点 -> 是链表 -> 是红黑树。
扩容检查。

✅ 参考回答

整个 put 流程主要分四步：

计算 Hash：

拿到 key 的 hashCode，通过扰动函数（高 16 位与低 16 位异或 h ^ (h >>> 16)）计算出 hash 值。这样做是为了让 Hash 分布更均匀，减少冲突。
定位索引：

通过 (n - 1) & hash 公式计算出在数组中的下标。这实际上就是取模运算，但位运算效率更高（前提是数组长度必须是 2 的幂）。
插入数据：
- 如果该位置没数据，直接放入。
- 如果冲突了（有数据）：
  - 如果是红黑树，调用树的插入逻辑。
  - 如果是链表，遍历链表。如果 key 存在就覆盖；不存在就插到尾部（JDK 1.8 改为尾插法）。
  - 插入后，检查链表长度是否 >= 8，是则转树。
扩容：

插入完成后，如果当前 size > 阈值（Capacity * 0.75），则触发 resize() 进行扩容，容量翻倍。

可能追问

问：为什么加载因子（Load Factor）默认为 0.75？
答：这是空间和时间的折中。
- 如果是 1.0：空间利用率高，但哈希冲突概率大，查询慢。
- 如果是 0.5：哈希冲突少，查询快，但浪费一半空间（频繁扩容）。
- 0.75 是官方测试出的平衡点。

Q3：HashMap 是线程安全的吗？为什么？（死循环问题）

面试官的心理活动

“这是经典考题。1.7 的死循环必须得会讲。1.8 虽然修了死循环，但依然不安全，你要知道为什么。”

你的思考路径

直接下结论：不安全。
分情况讨论：
- 1.7：并发扩容导致死循环。
- 1.8：数据覆盖（丢数据）。

✅ 参考回答

HashMap 绝对不是线程安全的。

JDK 1.7 的死循环问题：
- 原因在于 扩容（resize） 时的 头插法。
- 多线程环境下，当两个线程同时触发扩容，在移动链表节点时，可能会改变节点的引用顺序，导致链表成环（A->B 变成 B->A->B）。一旦成环，下次 get 操作进入这个链表就会陷入死循环，把 CPU 打满。
JDK 1.8 的数据丢失问题：
- 1.8 改用了 尾插法，虽然解决了链表成环的死循环问题，但依然不安全。
- 原因：如果有两个线程同时进行 put 操作，且计算出的索引位置相同。线程 A 判断该位置为空，正准备插入时被挂起；线程 B 此时插进去了；等线程 A 恢复执行，它不知道该位置已经有数据了，直接写入，就会把线程 B 的数据覆盖（丢失）。

可能追问

问：那在多线程下要用什么？
答：ConcurrentHashMap（推荐）或者 Collections.synchronizedMap（性能差，不推荐）。

Q4：ConcurrentHashMap 是怎么保证线程安全的？（1.7 vs 1.8）

面试官的心理活动

“HashMap 不安全，那方案来了。ConcurrentHashMap 是高并发下的神。你要能对比出 1.7 的分段锁和 1.8 的 CAS+Synchronized，说明你真的懂并发。”

你的思考路径

1.7：Segment 分段锁（锁一大段）。
1.8：CAS + Synchronized（锁一个节点）。
为什么 1.8 要放弃分段锁？（锁粒度更细，并发度更高）。

参考回答

ConcurrentHashMap 在两个版本中实现原理差异巨大：

JDK 1.7：分段锁（Segment）

结构：由一个 Segment 数组组成，每个 Segment 里面装着一个小的 HashMap（HashEntry 数组）。
锁机制：Segment 继承自 ReentrantLock。当要操作数据时，只锁住当前数据所在的那个 Segment，其他 Segment 不受影响。
并发度：默认 16。也就是说最多支持 16 个线程同时写。

JDK 1.8：CAS + Synchronized（节点锁）

结构：抛弃了 Segment，直接用 Node 数组 + 链表/红黑树（和 HashMap 1.8 结构一样）。
锁机制：
- CAS：如果当前位置（桶下标）没有数据，用 CAS 乐观锁尝试插入，不需要加锁。
- Synchronized：如果当前位置有数据（发生冲突），就用 synchronized 锁住链表头节点（或树根）。
优势：锁的粒度细到了每一个桶（Bucket）。只要 Hash 不冲突，几千个线程同时写都没事，并发性能比 1.7 大幅提升。

可能追问

问：为什么 1.8 用 synchronized 而不用 ReentrantLock？
答：
1. 节省内存：ReentrantLock 是一个对象，创建它需要内存开销。而 synchronized 是 JVM 原生支持的。
2. 性能优化：JDK 6 以后，JVM 对 synchronized 做了大量优化（偏向锁、轻量级锁、锁粗化），在低竞争下性能已经非常好了。