HashMap扩容的核心思想-牧云

在 JDK 8 中，HashMap 的扩容机制相比早期版本（如 JDK 7）有了重要优化，尤其是在元素重新分配（rehashing） 过程中，避免了不必要的链表反转和更高效的迁移策略。下面我们深入解析 JDK 8 HashMap 扩容后元素如何重新分配的原理。

一、背景：为什么需要扩容？

HashMap 底层是一个数组 + 链表/红黑树的结构。当元素数量超过阈值（threshold = capacity * loadFactor，默认负载因子 0.75）时，为避免哈希冲突过多导致性能下降，会触发扩容（resize）：

容量翻倍（newCap = oldCap << 1）
重新计算每个元素在新数组中的位置

二、JDK 8 扩容的核心思想：高低位拆分

这是 JDK 8 相比 JDK 7 最大的优化点。

关键观察：

由于 HashMap 的容量始终是 2 的幂（如 16, 32, 64...），扩容后新容量 newCap = oldCap * 2。

对于任意一个 key，其在数组中的索引由下式决定：

index = hash(key) & (capacity - 1)

假设原容量为 oldCap = 16（二进制 10000），则 oldCap - 1 = 15（二进制 01111）。
扩容后 newCap = 32，newCap - 1 = 31（二进制 11111）。

关键点：新旧索引的差异，只取决于 hash(key) 在 oldCap 对应位（即第 4 位，从 0 开始）是 0 还是 1。

举例说明：

hash(key) (二进制)	old index = hash & 15	new index = hash & 31	差异
`xxxxx0yyyy`	`0yyyy`	`0yyyy`	不变
`xxxxx1yyyy`	`0yyyy`	`1yyyy = 0yyyy + 16`	原索引 + oldCap

👉 结论：
扩容后，每个元素要么留在原位置，要么移动到原位置 + oldCap 的位置。

三、JDK 8 如何高效迁移？

在 JDK 8 中，resize() 方法对每个桶（bucket）做如下处理：

情况 1：桶为空

直接跳过。

情况 2：桶只有一个节点

直接根据上述规则计算新位置，放入新数组。

情况 3：桶是链表或红黑树（重点！）

🔹 对于链表（长度 < 8）：

JDK 8 将原链表拆分为两条链表：

低位链表（low）：hash & oldCap == 0 → 放在新数组的 原索引位置
高位链表（high）：hash & oldCap != 0 → 放在新数组的 原索引 + oldCap 位置

并且保持原有顺序（不会像 JDK 7 那样反转链表）！

代码逻辑简化示意：

Node<K,V> loHead = null, loTail = null; // 低位链表头尾
Node<K,V> hiHead = null, hiTail = null; // 高位链表头尾

for (Node<K,V> e = oldTab[j]; e != null; e = 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;
    }
}

// 放入新数组
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;               // 原位置
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;      // 原位置 + oldCap
}

✅ 优点：

无需重新计算每个 key 的 hash 值（只需 hash & oldCap 判断）
保持插入顺序，避免链表反转带来的潜在问题
时间复杂度 O(n)，且常数更小

🔹 对于红黑树（长度 ≥ 8）：

类似地，也会拆分为两棵红黑树（或退化为链表），分别放到两个位置。

四、图解示例

假设 oldCap = 16，某个桶 index = 5 上有链表：A → B → C

它们的 hash 值二进制末 5 位如下（只看第 4 位，因为 oldCap=16=2⁴）：

节点	hash (…xxxxx)	第 4 位	新位置
A	…0 0101	0	5
B	…1 0101	1	5+16=21
C	…0 0101	0	5

扩容后：

新数组 [5]：A → C
新数组 [21]：B

五、与 JDK 7 的对比

特性	JDK 7	JDK 8
扩容时 rehash	重新计算每个 key 的 index	利用 `hash & oldCap` 快速判断
链表顺序	反转（头插法导致）	保持原顺序（尾插法）
性能	较慢，易出错（并发下可能成环）	更快、更安全
红黑树支持	无	有（链表过长转红黑树）

💡 正是因为 JDK 7 的头插法 + 扩容反转，在多线程环境下可能导致死循环。JDK 8 的尾插法 + 顺序保持，大大提升了安全性（但 HashMap 仍非线程安全！）。

六、总结

JDK 8 HashMap 扩容后元素重新分配的核心原理是：

利用容量为 2 的幂的特性，通过 hash & oldCap 判断元素应放在“原位置”还是“原位置 + oldCap”，并将链表/红黑树拆分为高低两部分，保持顺序迁移。

这种设计：

✅ 避免了重复哈希计算
✅ 保持元素插入顺序
✅ 提升扩容效率
✅ 减少并发风险（虽仍不线程安全）

理解这一机制，不仅能掌握 HashMap 的底层实现，也为面试高频题打下坚实基础！

📌 提示：如果你在使用 ConcurrentHashMap，它的扩容机制更复杂（支持多线程协助扩容），但 JDK 8 的 HashMap 本身仍是非线程安全的，切勿在并发场景直接使用！

目录CONTENT

HashMap扩容的核心思想