HashMap 源码深度解析:从数组+链表到红黑树-夜雨聆风

HashMap 源码深度解析:从数组+链表到红黑树

点击上方“java大数据修炼之道”, 选择“设为星标”
技术干货发文后 👉 第一时间奉上

前言

HashMap 是 Java 开发中使用频率最高的集合类之一，几乎每个项目都离不开它。但你真的了解它的内部实现吗？为什么它在 JDK 8 之后引入了红黑树？链表什么时候会转化为红黑树？扩容的时机和代价是什么？本文将带你深入 HashMap 的源码，把这些问题一一讲清楚。

一、HashMap 的底层数据结构

HashMap 的核心是一个 Node 数组，每个数组槽位称为一个”桶”（bucket）。Node 是一个内部类，包含四个字段：hash 值、key、value，以及指向下一个节点的 next 引用。这就是链表的基础结构。

在 JDK 8 之前，HashMap 的结构是 数组 + 链表。当多个 key 的 hash 值映射到同一个桶时，这些元素以链表的形式串联在一起，这种现象叫做 哈希冲突。

JDK 8 之后，结构升级为 数组 + 链表 + 红黑树。当某个桶中的链表长度超过阈值（默认为 8），且数组长度大于等于 64 时，链表会转化为红黑树，以提升查询效率。

二、put() 方法的完整流程

理解 HashMap，最重要的入口就是 put() 方法。它的执行流程如下：

计算 hash 值：

HashMap 并不直接使用 key.hashCode()，而是对其进行了一次扰动处理：将 hashCode 的高 16 位与低 16 位做异或运算。这样做的目的是让高位信息也参与到桶的定位中，减少低位相同导致的冲突。

2. 定位桶的位置：

通过 (n – 1) & hash 计算桶的下标，其中 n 是数组长度。由于数组长度始终是 2 的幂次，这个位运算等价于取模，但效率更高。

3. 判断桶是否为空：

如果目标桶为空，直接创建新节点放入。

4. 桶不为空时的处理：

首先判断桶中第一个节点的 key 是否与要插入的 key 相同（先比较 hash，再用 equals 比较），如果相同则直接覆盖 value。如果不同，则判断当前节点是链表节点还是红黑树节点，分别走不同的插入逻辑。

5. 链表插入：

遍历链表，如果找到相同的 key 则覆盖，否则在链表尾部追加新节点。插入后检查链表长度，如果超过 8 则尝试树化。

6. 插入完成后检查扩容：

如果当前元素数量超过阈值（capacity × loadFactor），则触发 resize() 扩容。

三、为什么链表转红黑树的阈值是 8？

这个问题在面试中经常被问到。答案藏在 HashMap 的源码注释里。

HashMap 的设计者假设，在理想情况下，桶中节点的数量服从泊松分布。当负载因子为 0.75 时，桶中节点数量达到 8 的概率约为 0.00000006，是一个极小的概率。也就是说，正常情况下链表几乎不会达到 8 个节点。

之所以选择 8 而不是更小的数字，是因为红黑树虽然查询效率高（O(log n)），但它的节点占用内存是普通链表节点的两倍，而且维护树结构（旋转、变色）也有额外开销。只有在链表足够长时，红黑树的查询优势才能弥补这些代价。

同样，当红黑树节点数量降到 6 时，会退化回链表。阈值 8 和 6 之间留了一个缓冲区，避免在临界值附近频繁地树化和反树化。

四、扩容机制：resize() 的代价与优化

HashMap 的默认初始容量是 16，负载因子是 0.75。当元素数量超过 16 × 0.75 = 12 时，触发扩容，容量翻倍变为 32。

扩容的核心操作是重新分配所有元素。JDK 8 在这里做了一个巧妙的优化：由于容量是 2 的幂次，扩容后每个元素的新桶位置只有两种可能——要么保持原位，要么移动到”原位置 + 旧容量”的位置。

判断依据是：用元素的 hash 值与旧容量做与运算，结果为 0 则留在原位，结果为 1 则移到新位置。这个设计避免了重新计算每个元素的 hash，大幅提升了扩容效率。

扩容是有代价的，它需要遍历整个数组并重新分配所有元素。因此，如果能预估元素数量，建议在创建 HashMap 时指定初始容量，避免多次扩容带来的性能损耗。初始容量的计算公式是：预期元素数量 / 0.75 + 1，然后取大于该值的最小 2 的幂次。

五、线程不安全的根源

HashMap 是线程不安全的，在多线程环境下使用会出现各种问题。

数据丢失：两个线程同时执行 put 操作，如果它们的 key 映射到同一个桶，且桶为空，两个线程都判断桶为空并各自创建节点，最终只有一个节点会被保留，另一个被覆盖，导致数据丢失。

死循环（JDK 7 特有）：JDK 7 的扩容采用头插法，多线程并发扩容时可能形成环形链表，导致 get() 操作陷入死循环，CPU 飙升到 100%。JDK 8 改用尾插法解决了这个问题，但并发下仍然存在数据不一致的风险。

多线程场景下，应使用 ConcurrentHashMap，它通过分段锁（JDK 7）或 CAS + synchronized（JDK 8）实现了线程安全，且性能远优于 Hashtable 的全表锁方案。

六、几个容易忽视的细节

null key 的处理：HashMap 允许 key 为 null，null key 的 hash 值固定为 0，因此它始终存储在数组的第 0 个桶中。

初始容量必须是 2 的幂次：即使你传入的初始容量不是 2 的幂次，HashMap 内部也会自动将其调整为大于该值的最小 2 的幂次。这是为了保证位运算定位桶的正确性。

树化的双重条件：链表转红黑树需要同时满足两个条件——链表长度大于 8，且数组长度大于等于 64。如果数组长度不足 64，即使链表长度超过 8，也只会触发扩容而不是树化。这是因为数组较小时，扩容能更有效地分散冲突。

总结

HashMap 的设计充满了工程智慧：扰动函数减少冲突、位运算提升定位效率、尾插法避免死循环、红黑树应对极端冲突、扩容时的高低位拆分减少重计算开销。每一个细节背后都有明确的设计动机。

理解这些原理，不仅能帮助你在面试中游刃有余，更重要的是能让你在实际开发中做出更合理的选择——比如何时预设容量、为什么不能在多线程中直接用 HashMap、以及遇到性能问题时如何分析根因。

下一篇我们将深入 ConcurrentHashMap，看看它是如何在保证线程安全的同时，把并发性能做到极致的。

end


===往期精彩文章复习回顾===

1.SpringBoot 插件化开发模式，真香啊！
2.一行代码，实现请假审批流程（Java版）
3.血泪教训，8 个线程池最佳实践和坑
4.SpringBoot骚操作：一个注解秒杀所有类型的文件下载！
5.Controller层代码这么写，同事们都模仿起来了





最近整理一份资料《程序员学习手册》，覆盖了 Java技术、面试题精选、操作系统基础知识、计算机基础知识、Linux教程、计算机网络等等。
获取方式：点“ 在看，关注公众号 Java大数据修炼之道 并回复PDF 领取，更多内容陆续奉上。





长按识别下方二维码关注后回复关键字:PDF领取

你想学的java知识这里都有,长按下方图片识别关注我们吧~

如喜欢本文请点击右上角，把文章分享到朋友圈
因公众号更改推送规则，请点“在看”并加“星标”第一时间获取精彩技术分享
点分享
点收藏
点在看