hashmap扩容后数据的迁移

🔥高频面试资料免费领！点击获取→
（链接: https://pan.baidu.com/s/1RUVf75gmDVsg8MQp4yRChg?pwd=9b3g 提取码: 9b3g）

HashMap扩容触发条件与核心机制

当HashMap中元素数量超过扩容阈值（threshold = capacity * loadFactor）时触发扩容。默认扩容因子为0.75，这意味着当哈希表填充达到容量的75%时，就会执行2倍扩容。这种设计既保证了空间利用率，又减少了哈希冲突概率。

---

数据迁移过程详解

1. 新数组创建与容量翻倍

HashMap会先创建一个容量为原数组2倍的新数组（例如从16扩容到32），这是为了保持容量始终为2的n次幂。这种设计使得计算元素下标时可以通过(n-1) & hash快速定位，避免取模运算。

2. 链表节点迁移策略

遍历旧数组的每个桶时，JDK1.8采用高位判定位算法：

if ((e.hash & oldCap) == 0) {
    // 保持原下标位置
} else {
    // 新位置=原下标+oldCap
}

这种位运算的效率远高于重新计算哈希值，整个过程时间复杂度为O(n)。

3. 红黑树拆分优化

当桶中节点数超过8时，链表会转化为红黑树。迁移时会根据树节点的高位哈希值将树拆分为两个链表，如果拆分后链表长度小于6则退化为链表。

---

为什么必须是2的幂次方？

• 快速定位桶下标：(n-1) & hash等效于取模运算但效率更高
• 均匀分布：二次哈希时高位参与运算，减少哈希碰撞
• 扩容迁移优化：通过高位判定位快速判断新位置

---

并发场景下的死循环问题

在JDK1.7中，头插法迁移链表时多线程操作可能导致环形链表，进而引发死循环。JDK1.8改用尾插法解决了这个问题，但HashMap仍然是线程不安全的，高并发场景应使用ConcurrentHashMap。

---

高频面试注意事项

1. 明确扩容阈值计算公式：capacity * loadFactor
2. 解释2的n次幂的设计优势时，要结合位运算特点
3. 对比JDK1.7和1.8的迁移策略差异
4. 强调HashMap非线程安全的本质

小提示：如果需要购买面试鸭会员，通过面试鸭返利网联系我可返利25元，助你高效备战面试！

🔥还没领取面试资料？点击这里→