1. 从一个反直觉的现象说起：为什么JDK8的HashMap扩容后链表顺序反而"正"了
很多人第一次接触HashMap扩容机制时，都会有一个想当然的判断：既然JDK8把链表插入方式从"头插法"改成了"尾插法"，那扩容之后元素的相对顺序应该跟原来一样吧？实际上恰恰相反——JDK7用头插法，扩容后链表顺序会反转；JDK8用尾插法，扩容后链表顺序反而保持不变。这个结论乍一看很绕，但只要你把扩容时"拆链表"的那段代码逐行读一遍，就会发现它其实是一个非常精巧的设计。
我在带新人的时候经常拿这个点做切入点，因为它同时牵扯到三件事：哈希桶的索引计算逻辑、链表在扩容时的拆分策略、以及多线程场景下头插法为什么会形成环形链表。把这三件事串起来讲清楚，JDK8扩容的核心基本就吃透了。
这篇内容适合已经用过HashMap、但对其内部扩容机制只有模糊印象的开发者。如果你能看懂put和get的大致流程，但对resize()里那段loHead/loTail/hiHead/hiTail的代码一直没搞明白，那这篇就是写给你的。我会从索引计算讲起，把扩容拆链表的每一步都拆开，再对比JDK7的头插法问题，最后给出几个实际开发中能用上的结论。
2. 扩容的起点：table长度、阈值与索引计算这三者的联动关系
2.1 为什么容量必须是2的幂
HashMap的底层是一个Node<K,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、阈值12），size变成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 = 16，oldCap - 1 =0000 1111，newCap = 32，newCap - 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的扩容代码用了一组很巧妙的指针来拆分链表：
Node<K,V> loHead = null, loTail = null; // 低位链：留在原索引 Node<K,V> hiHead = null, hiTail = null; // 高位链：移到 原索引+oldCap Node<K,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（都留在低位）。遍历过程是：
- 处理A：loTail为null，所以
loHead = A，然后loTail = A。此时低位链：A。 - 处理B：loTail不为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 (Entry<K,V> e : table) { while (e != null) { Entry<K,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但容量还不到64，HashMap不会树化，而是优先扩容。因为容量小的时候，冲突多往往是因为桶太少，扩容比树化更划算。
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; Map<String, 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()那段代码，你会发现它其实没有一行是多余的。每个变量、每个判断、每次指针操作，背后都有明确的意图。这种"每一行都能讲出为什么"的代码，才是真正值得反复读的。
