前言从“单兵作战”到“全局统筹”在前两篇中我们从源码的静态常量出发剖析了 2 的幂次方设计、0.75 的加载因子、8 与 6 的树化防抖动机制并彻底打通了哈希扰动函数、下标计算以及“扩容与树化双重触发机制”的动态链路。然而当 HashMap 真正面临海量数据时它必须经历一次“脱胎换骨”的重生——扩容Resize。在 JDK 8 中扩容机制经历了颠覆性的优化同时随着红黑树的引入元素的删除也带来了“退化回链表”的新课题。更令人深思的是HashMap 在多线程环境下的演进史本身就是一部血泪交织的并发安全史。本篇章将带你深入 JDK 8 扩容的底层算法剖析红黑树的优雅降级并回溯 JDK 7 多线程扩容导致死循环的底层逻辑。第七章扩容Resize——JDK 8 的极致优化艺术当size threshold触发扩容时HashMap 会创建一个长度为原来2 倍的新数组并将旧数组中的所有元素迁移到新数组中。在 JDK 7 中这个过程需要重新计算每一个元素的 Hash 值hash % newCap效率极低。而 JDK 8 利用 2 的幂次方特性实现了一种极其巧妙的**“高低位拆分”**算法。7.1 核心算法hash oldCap 的魔法【定义】在 JDK 8 的扩容迁移中元素在新数组中的位置只有两种可能原位置索引不变。原位置 旧容量oldCap索引下移。【通俗讲解为什么不需要重新计算 Hash】假设旧容量oldCap 16二进制为0001 0000。当我们把容量翻倍到 32 时新的掩码n-1从0000 1111变成了0001 1111。对比发现新掩码仅仅比旧掩码多了一个高位 1。这意味着元素在新数组中的下标变化完全取决于它的 hash 值在“旧容量那一位”上是 0 还是 1如果hash oldCap 0说明这个多出来的高位是 0元素在新数组中的位置保持不变。如果hash oldCap ! 0说明这个多出来的高位是 1元素在新数组中的位置等于原索引 oldCap。通过这种位运算HashMap 彻底抛弃了耗时的重新取模运算只需一次简单的判断就能将旧链表优雅地拆分为两条新链表低位链表和高位链表极大地提升了扩容性能。第八章红黑树的退化——优雅的“降级”机制我们在第一篇中讲过当链表长度达到 8 且数组长度 64 时链表会转化为红黑树。但红黑树并非永远存在它同样有着严格的退出机制。8.1 退化条件UNTREEIFY_THRESHOLD 6【定义】当红黑树中的节点数因为删除操作而减少到6或更少时HashMap 会调用untreeifyBin()方法将红黑树重新转化为普通的单向链表。此外在扩容resize进行高低位拆分时如果拆分后的子树节点数 6也会直接退化为链表。【深度追问为什么退化阈值是 6 而不是 8】这再次印证了我们之前提到的**“防抖动Hysteresis”设计哲学。如果树化和退化的阈值都是 8那么当桶内元素在 7 和 8 之间频繁增删时底层结构就会在“链表”和“红黑树”之间疯狂切换。红黑树的维护左旋、右旋、变色成本极高而链表结构简单、内存开销小。将退化阈值设为 6在 6、7、8 之间形成了一个“缓冲区”**确保了底层数据结构的绝对稳定性避免了无谓的性能损耗。第九章并发安全与死循环——JDK 7 的血泪史与 JDK 8 的救赎HashMap 不是线程安全的这在面试中是常识。但“为什么不安全”以及“不安全会导致什么后果”才是区分初级与高级开发者的分水岭。9.1 JDK 7 的致命缺陷头插法与环形链表【定义】在 JDK 7 中HashMap 在扩容时采用的是**“头插法”将旧链表节点逆序插入新数组。在多线程并发扩容时这会导致链表节点之间的next指针互相指向形成环形链表死循环**。【通俗讲解死循环是怎么产生的】假设桶里有两个节点 A - B。线程 1 和线程 2 同时触发扩容。因为采用头插法线程 1 先把 B 插到新桶再把 A 插到 B 前面变成 B - A。此时如果线程 2 也执行头插它可能会把 A 插到 B 前面导致 A 的 next 指向 BB 的 next 又指向 A。一旦形成A - B - A的环当其他线程执行get()遍历这个桶时就会陷入无限循环导致CPU 使用率飙升到 100%服务彻底瘫痪。9.2 JDK 8 的救赎尾插法与高低位拆分【定义】JDK 8 彻底重构了扩容机制将“头插法”改为了**“尾插法”**并结合了“高低位拆分”算法。【深度追问JDK 8 还会死循环吗】绝对不会。尾插法保证了元素在迁移前后的相对顺序不变从根本上杜绝了环形链表的产生。但是JDK 8 的 HashMap 依然是线程不安全的虽然不会死循环但在多线程并发 put 时依然会出现数据覆盖两个线程同时判断桶为空并写入和size 统计不准非原子性的size操作等严重问题。9.3 终极解决方案ConcurrentHashMap如果业务场景必须在多线程下使用哈希表绝对不要使用 HashMap而应使用ConcurrentHashMap。JDK 8 的 ConcurrentHashMap 放弃了 Segment 分段锁采用了Node数组 链表/红黑树 CAS synchronized的设计。它在保证极高并发安全的同时完美复用了 HashMap 的 2 的幂定位机制和树化机制是生产环境下的唯一正解。结语与后续预告在第三部分的讲解中我们从 JDK 8 扩容的“高低位拆分”算法讲到了红黑树退化的“防抖动”机制最后回溯了 JDK 7 头插法导致的死循环血泪史彻底闭环了 HashMap 的底层运转逻辑。至此我们已经构建了一个极其庞大且严密的 HashMap 知识体系。但在后续的**《HashMap 核心原理全解讲解四》**中我们还将继续向更深处探索Key 的极端场景如果所有的 Key 的 hashCode 都相同HashMap 会退化到什么程度可变对象作为 Key 的灾难为什么在 put 之后修改 Key 的属性会导致数据“凭空消失”高级 API 的陷阱computeIfAbsent为什么在 HashMap 中不是绝对安全的HashMap 与 Hashtable 的底层对比除了线程安全它们在底层实现上还有哪些本质区别