Java集合--HashMap底层原理可视化，秒懂扩容、链化、树化

文章内容较长，带着疑问慢慢读。
文章对应的视频连接：https://www.bilibili.com/video/BV1wM3KzaE3d/

哈希冲突问题如何高效解决？

1. 什么是冲突？

准确的说是解决哈希值映射冲突，而非解决哈希冲突。
哈希冲突指的是不同的key计算出来的哈希值相同而产生的冲突。
但这里是，不同的哈希值映射到相同的数组槽位置，而产生的存储位置冲突。
哈希表把 key 计算出哈希值后映射成整数 index，放到固定长度的数组槽（bucket）里。
当两个不同的 key 经过哈希函数后映射到相同的槽位，就发生了冲突。例如：

1. hash("abc") & (tableSize - 1) == 3  
2. hash("xyz") & (tableSize - 1) == 3  

复制代码

这两个不同的key 计算出来的哈希值不同，但都会被放到索引 3 的桶里。
关于这个问题可查阅上一篇文章：HashMap如何快速定位数据存储在内存地址的位置？。

但很多人都会将其称为哈希冲突，为了“达成共识”，后面都会把映射冲突和哈希冲突都称为哈希冲突。
2. 如何解决哈希冲突？

主要有 两大类方法：
开放寻址法（Open Addressing）

所有元素都直接存放在哈希表数组里，没有链表。
一旦发生冲突，就在数组里按一定探测规则继续找下一个空槽位。
常见策略：
方法原理线性探测（Linear Probing）下一个槽位是 (index + 1) % tableSize二次探测（Quadratic Probing）距离按平方增加，如 (index + i^2) % tableSize双重哈希（Double Hashing）用另一个哈希函数求探测步长特点：适合占用率低时（负载因子 < 0.7）；一旦负载高就容易产生聚集，效率下降。
链地址法（Separate Chaining）

每个槽位维护一个 桶（链表或红黑树）；冲突的元素插入到该槽位的桶结构里。
HashMap 就是这样做的：

• 早期 JDK：每个桶是一个链表
  
• JDK 8+：当链表长度超过阈值 8，同时桶的大小>=64时，自动转成红黑树，提升查找效率
  

特点：实现简单，扩容后负载高也不怕冲突太多；空间换时间（每个桶需要额外引用）；适合高负载且需要稳定性能的场景。
HashMap的数据结构：数组+链表/红黑树

3. 怎么提升效率？

好的哈希函数：HashMap 会对 hashCode 做扰动（高位参与低位），保证桶索引分布更均匀。
链地址法：每个槽位维护一个 桶；冲突的元素插入到该槽位的桶结构里。
优秀桶结构：链表长度有阈值（8）控制，确保不会退化成O(n)；自平衡二叉查找树--红黑树，确保查找效率为 O(log n)。并且有负载阈值触发动态扩容，不会让红黑树无限扩大。
动态扩容：当负载因子（元素数量 / 桶数量）超过阈值（默认 0.75），就会扩容（桶数量 * 2），扩容会重新计算所有元素的桶索引，让冲突的元素再次分散开来，从而减少冲突。
HashMap高效归纳为：好哈希函数 + 链地址法 + 优秀桶结构 + 动态扩容四件套组合，保证冲突多时依然高效。
4. 扩容

扩容，扩的都是数组的容量。
有三种情况会触发扩容

• 初次插入数据时的扩容，不管是否构造函数指定大小创建HashMap都是插入才扩容；
  
• 数组（桶）小于64，并且单链表 >8 时的扩容
  
• 默认情况，使用容量 > 存储容量的loadFactor倍（存储容量的75%）
  

比如，大于阈值的扩容过程
触发条件满足：size > threshold = newCap × loadFactor

计算新容量：newCap = oldCap >> 1;    n |= n >>> 2;    n |= n >>> 4;    n |= n >>> 8;    n |= n >>> 16;    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}[/code]该方法是后续高效处理 key 的重要基础。
首次插入元素图示：

每次扩容都会：
<blockquote>
重新计算新容量：newCap = oldCap  TREEIFY_THRESHOLD（8）整个表容量 ≥ MIN_TREEIFY_CAPACITY（64）
</ol>如果条件符合，将该桶的链表转换为红黑树，节点类型由链表节点 Node 被替换为 TreeNode，查找、插入、删除最坏 O(log n)。若容量 < 64，则优先扩容而非树化。
触发链表树化的主要源码：

1. if (table[index] == null) {
2. table[index] = newNode(hash, key, value, null);
3. } else {
4. // 已有节点，遍历链表找相同 key 或添加到尾部
5. }

复制代码

触发链表树化的条件if (binCount >= TREEIFY_THRESHOLD - 1) ，binCount=7的时候就会触发树化，因为binCount是p.next的次数，并且binCount从0开始的，也就是说循环了8次，在这里别搞混了。
还有一点就是，链表是插入第9个节点时才进行的树化，可看源码，是先插入节点后进行判断的；故此树化前的链表长度已变成9了，所以链表树化前的链表长度为9。
链表树化分两步

通过treeifyBin(tab,hash)方法完成链表树化操作。主要分为两步：

• 先将链表的Node节点，转化成TreeNode节点，关键源码：TreeNode p = replacementTreeNode(e, null)；
  
• 再进行真正树化，关键源码：hd.treeify(tab)。
  

通过案例感受下：
将单个链表插入第9个节点，使其超过单链表长度阈值，此时数组大小为64，条件满足触发链表树化，可视化过程如图：

红黑树节点插入、染色、平衡的过程，不在这里展开，可单独学习红黑树数据结构。如果想要看HashMap红黑树数据结构的可视化视频的，可以在评论区留言，我抽时间把源代码完全还原出来。
红黑树插入、删除和树化完成都会调用这个方法moveRootToFront(tab, root)，因为这些操作都有可能导致根节点发生变化，该方法的作用是确保数组（桶）始终指向红黑树的根节点。
8. 第四次扩容（树化后扩容）

然后插入满75%的容量，触发第四次扩容。扩容规则如下：

1.只有一个节点的链表直接计算位置插入;
2.如果是红黑树，按照hash&64==0？分低位、高位拆分成两个链表，\n判断双链表的长度，节点数6时，正常树化"，再插入；
3.不止一个节点的链表，按照hash&64==0？分低位、高位拆分成两个链表，再插入

链表的调整前面已经讲过，重点关注红黑树在扩容期间如何操作的。
扩容期间，如果数组（桶）指向的是红黑树节点，那么就会调用split方法完成处理。
处理过程分为三步：
<ol>使用红黑树的双链结构TreeNode的next节点进行遍历；
根据(hash & bit) == 0 拆分成低位和高位两条TreeNode节点的双链结构；

判断低位和高位双链表长度是否