JDK8 HashMap扩容机制：尾插法如何保持链表顺序并规避环形链表

1. 从一个反直觉的现象说起为什么JDK8的HashMap扩容后链表顺序反而正了很多人第一次接触HashMap扩容机制时都会有一个想当然的判断既然JDK8把链表插入方式从头插法改成了尾插法那扩容之后元素的相对顺序应该跟原来一样吧实际上恰恰相反——JDK7用头插法扩容后链表顺序会反转JDK8用尾插法扩容后链表顺序反而保持不变。这个结论乍一看很绕但只要你把扩容时拆链表的那段代码逐行读一遍就会发现它其实是一个非常精巧的设计。我在带新人的时候经常拿这个点做切入点因为它同时牵扯到三件事哈希桶的索引计算逻辑、链表在扩容时的拆分策略、以及多线程场景下头插法为什么会形成环形链表。把这三件事串起来讲清楚JDK8扩容的核心基本就吃透了。这篇内容适合已经用过HashMap、但对其内部扩容机制只有模糊印象的开发者。如果你能看懂put和get的大致流程但对resize()里那段loHead/loTail/hiHead/hiTail的代码一直没搞明白那这篇就是写给你的。我会从索引计算讲起把扩容拆链表的每一步都拆开再对比JDK7的头插法问题最后给出几个实际开发中能用上的结论。2. 扩容的起点table长度、阈值与索引计算这三者的联动关系2.1 为什么容量必须是2的幂HashMap的底层是一个NodeK,V[] table数组这个数组的长度capacity有一个硬性约束必须是2的整数次幂。很多人知道这个结论但说不清为什么。原因藏在索引计算的那行代码里// JDK8中计算桶索引的核心逻辑 if ((p tab[i (n - 1) hash]) null) tab[i] newNode(hash, key, value, null);索引不是用hash % n算的而是用(n - 1) hash。这两者在n是2的幂时结果完全等价但位运算比取模快得多。举个具体例子假设n 16那么n - 1 15二进制是0000 1111。任何hash值与它做与运算结果只会落在0~15这个范围内正好对应数组的16个下标。如果n不是2的幂比如n 15那么n - 1 14二进制是0000 1110。你会发现最低位永远是0也就是说下标1、3、5、7...这些位置永远用不到一半的桶被浪费了而且哈希分布会严重不均。所以容量为2的幂不是随便定的它是(n-1) hash这个位运算能正确工作的前提。注意这也是为什么你在new HashMap(17)时实际容量会被调整成32而不是17。构造方法里调用了tableSizeFor它会把传入的容量向上取整到最近的2的幂。2.2 负载因子0.75是怎么来的阈值threshold的计算公式是capacity * loadFactor。默认负载因子是0.75这个数字也不是拍脑袋定的。它是在空间利用率和哈希冲突概率之间做的折中。如果负载因子太高比如1.0数组几乎被填满才扩容空间省了但哈希冲突会急剧增加链表变长查询退化成O(n)。如果负载因子太低比如0.5冲突少了但一半空间空着内存浪费严重而且扩容更频繁。0.75对应的是泊松分布下冲突概率的一个较优解。官方注释里提到在理想哈希下一个桶中元素个数达到8的概率约为千万分之六这也是后面链表转红黑树阈值定为8的依据之一。2.3 扩容触发的两个时机扩容不是只在put的时候发生具体有两个触发点初始化时第一次put元素时如果table还是null会调用resize()完成初始化此时容量设为默认的16阈值设为12。元素数量超过阈值时每次put成功后如果size threshold就会触发扩容容量翻倍。这里有个容易忽略的细节扩容是先插入再判断。也就是说第13个元素插入后默认容量16、阈值12size变成13超过12才会触发扩容到32。所以扩容后阈值变成24下一次扩容要等到第25个元素。3. 拆链表那段代码loHead/loTail与hiHead/hiTail到底在干什么3.1 扩容时元素的新位置只有两种可能这是理解整个扩容机制的关键前提。假设旧容量是oldCap新容量是newCap oldCap 1翻倍。对于旧数组中某个桶里的元素它的hash值记为h那么旧索引h (oldCap - 1)新索引h (newCap - 1)因为newCap是oldCap的两倍newCap - 1相比oldCap - 1只是最高位多了一个1。所以新索引要么等于旧索引要么等于旧索引 oldCap。没有第三种可能。举个例子oldCap 16oldCap - 1 0000 1111newCap 32newCap - 1 0001 1111。多出来的那一位是第5位从0开始数。所以判断元素去哪个新桶只需要看hash值的第5位是0还是1第5位是0新索引 旧索引第5位是1新索引 旧索引 16这个判断在代码里就是(e.hash oldCap) 0。注意这里是 oldCap而不是 (oldCap - 1)因为oldCap本身正好就是那个多出来的位的值16 0001 0000。3.2 四个指针的分工JDK8的扩容代码用了一组很巧妙的指针来拆分链表NodeK,V loHead null, loTail null; // 低位链留在原索引 NodeK,V hiHead null, hiTail null; // 高位链移到 原索引oldCap NodeK,V next; do { next e.next; if ((e.hash oldCap) 0) { if (loTail null) loHead e; else loTail.next e; loTail e; } else { if (hiTail null) hiHead e; else hiTail.next e; hiTail e; } } while ((e next) ! null); if (loTail ! null) { loTail.next null; newTab[j] loHead; } if (hiTail ! null) { hiTail.next null; newTab[j oldCap] hiHead; }这段代码做的事情可以拆成四步遍历旧链表对每个节点判断(e.hash oldCap)。低位链把判断为0的节点用loHead/loTail串起来。高位链把判断为1的节点用hiHead/hiTail串起来。挂到新数组低位链放到newTab[j]高位链放到newTab[j oldCap]。3.3 尾插法为什么能保持顺序现在回答开头那个反直觉的问题。关键在于loTail.next e; loTail e;这两行的顺序。假设旧链表是A - B - C且三个节点都满足(hash oldCap) 0都留在低位。遍历过程是处理AloTail为null所以loHead A然后loTail A。此时低位链A。处理BloTail不为null执行loTail.next B即A.next B然后loTail B。此时低位链A - B。处理C执行loTail.next C即B.next C然后loTail C。此时低位链A - B - C。看到没有新节点总是被追加到尾部所以最终链表的顺序和原链表完全一致。这就是尾插法保持顺序的本质。对比JDK7的头插法它是newNode.next oldHead; newHead newNode;每来一个节点都插到头部遍历完顺序自然就反了。JDK7扩容后A - B - C会变成C - B - A。提示尾插法保持顺序这个特性在JDK8里其实没有特别强的业务意义因为HashMap本身就不保证顺序。它真正的价值在于避免了头插法在多线程扩容时形成环形链表的问题。4. 头插法的环形链表JDK7那个经典的多线程事故4.1 环形链表是怎么形成的JDK7的头插法扩容代码大致是这样的// JDK7 transfer 方法片段简化 void transfer(Entry[] newTable) { for (EntryK,V e : table) { while (e ! null) { EntryK,V next e.next; int i indexFor(e.hash, newTable.length); e.next newTable[i]; // 头插 newTable[i] e; e next; } } }单线程下这段代码没问题。但多线程同时扩容时两个线程操作同一个链表就可能出现节点互相指向的情况形成环。一旦形成环后续任何get操作只要落到这个桶上就会陷入死循环CPU直接飙到100%。这个问题的根因是头插法会修改已有节点的next指针而多线程下这个修改没有同步保护。线程A读到e和e.next之后被挂起线程B完成了扩容并改变了链表结构线程A恢复后继续按旧引用操作指针就乱了。4.2 JDK8的尾插法为什么能规避JDK8的尾插法在扩容时虽然也修改next指针但它的操作模式不同它是把节点按原顺序重新串成两条新链最后一次性挂到新数组上。整个过程对旧链表的遍历是只读的除了最后断开尾节点不会在遍历中途把节点插到某个已有节点前面。不过要说清楚JDK8的HashMap依然不是线程安全的。尾插法只是消除了扩容形成环形链表这个特定问题但多线程同时put仍然可能导致数据丢失、size计数错误等问题。真正需要并发场景还是得用ConcurrentHashMap。注意网上有些说法称JDK8的HashMap解决了线程安全问题这是错的。它只是把最严重的死循环问题规避了其他并发问题依然存在。4.3 一个可以复现的对比实验思路如果你想直观感受两者的差异可以写一个简单的压测开多个线程往同一个HashMap里疯狂put同时触发扩容。在JDK7下跑有一定概率观察到CPU打满、线程卡死在JDK8下跑通常不会死循环但你会发现最终size小于实际put的次数说明有数据丢失。这个实验能帮你把线程不安全从一句口号变成亲眼所见的现象。5. 红黑树转换与扩容的配合树化阈值和退化阈值5.1 链表什么时候变成红黑树JDK8引入红黑树是为了解决极端情况下链表过长导致查询退化的问题。转换的触发条件是链表长度达到TREEIFY_THRESHOLD默认8同时table容量达到MIN_TREEIFY_CAPACITY默认64如果链表到了8但容量还不到64HashMap不会树化而是优先扩容。因为容量小的时候冲突多往往是因为桶太少扩容比树化更划算。5.2 扩容时红黑树怎么拆扩容时如果遇到红黑树节点处理逻辑和链表类似也是按(e.hash oldCap)拆成低位和高位两棵树。拆完之后会判断每棵树的节点数如果节点数 UNTREEIFY_THRESHOLD默认6就把树退化成链表。否则保持红黑树结构。这个6和8之间的差值不是随意的它留了一个缓冲区间避免在7附近反复树化和退化造成性能抖动。5.3 树化与扩容的优先级这里有个实际开发中值得注意的点扩容的优先级高于树化。也就是说当你往一个容量16的HashMap里塞元素某个桶的链表到了8此时不会立刻树化而是先扩容到32。如果扩容后这个桶的链表长度降到7以下就永远不会树化。只有容量已经到64、链表还是8以上才会真正转成红黑树。理解这个优先级能帮你解释一些为什么我的HashMap没变成红黑树的疑惑。6. 实际开发中关于扩容的几个实用结论6.1 预设初始容量能省掉大量扩容开销如果你明确知道要存大约N个元素最好在创建时就指定容量。但要注意传入的值会被tableSizeFor向上取整到2的幂而且实际能容纳的元素数是容量 * 0.75。所以如果你要存1000个元素应该传1000 / 0.75 ≈ 1334再向上取整到2048。// 要存1000个元素避免扩容的推荐写法 int expectedSize 1000; int initialCapacity (int) (expectedSize / 0.75f) 1; MapString, Object map new HashMap(initialCapacity);如果不预设从默认16开始存1000个元素要经历多次扩容16→32→64→...→2048每次扩容都要重新计算索引、拆分链表开销不小。6.2 扩容的代价到底有多大单次扩容的时间复杂度是O(n)n是当前元素数量。虽然均摊到每次put上是O(1)但在扩容发生的那一次put上延迟会明显升高。对于延迟敏感的场景比如高频交易、实时计算这种偶发的长延迟是需要警惕的。我个人的经验是如果一个Map的生命周期内元素数量会持续增长且不可预估预设一个偏大的初始容量比让它反复扩容要划算。多占的那点内存通常比扩容带来的CPU抖动更值得。6.3 遍历顺序在扩容后会变虽然尾插法保持了单个桶内链表的顺序但整个Map的遍历顺序在扩容后仍然会变。因为元素被重新分配到了不同的桶桶与桶之间的相对顺序变了。所以任何依赖HashMap遍历顺序的代码都是不可靠的这一点在扩容前后尤其明显。6.4 关于hash扰动函数的补充JDK8的hash计算是(h key.hashCode()) ^ (h 16)把高16位异或到低16位。这样做的目的是让高位也参与到索引计算中减少冲突。因为索引计算用的是(n-1) hash当n比较小时只有hash的低几位起作用高位信息被浪费了。扰动函数把高位信息混到低位让分布更均匀。这个设计配合扩容时的(e.hash oldCap)判断效果很好因为hash的高位已经被扰动过所以判断第5位是0还是1时分布也相对均匀不会出现大量元素挤到同一个新桶的情况。7. 我在读这段源码时踩过的几个理解误区第一个误区是以为(e.hash oldCap)和(e.hash (oldCap - 1))是一回事。实际上前者判断的是多出来的那一位后者算的是旧索引。这两个运算的目的完全不同前者用于分流后者用于定位。我当初就是混淆了这两个导致怎么都想不通为什么新索引只有两种可能。第二个误区是以为尾插法是为了保证顺序而设计的。其实顺序保持只是尾插法的一个副产品它真正的动机是规避头插法在多线程下的环形链表问题。如果你只盯着顺序去理解就会觉得这个设计没什么必要——反正HashMap又不保证顺序。但一旦从并发安全的角度看尾插法的价值就凸显出来了。第三个误区是以为扩容时链表拆分是重新计算每个节点的索引。实际上它根本没有重新算索引只是用(e.hash oldCap)做了一次分流然后直接挂到j和j oldCap两个位置。这个优化避免了每个节点都做一次完整的索引计算是扩容性能优化的一个细节。第四个误区是忽略了loTail.next null和hiTail.next null这两行。它们的作用是断开新链表的尾部防止新链表意外地指向旧链表中的其他节点。如果漏了这两行新链表可能会带着一串本不该属于它的节点造成数据错乱。这个细节在阅读源码时很容易被跳过但它是保证正确性的关键。把上面这些点都理清楚之后再回头看resize()那段代码你会发现它其实没有一行是多余的。每个变量、每个判断、每次指针操作背后都有明确的意图。这种每一行都能讲出为什么的代码才是真正值得反复读的。