个人网站

你知道 HashMap 会扩容，但面试官追问"什么时候触发扩容"、“扩容时元素怎么迁移”、“JDK 7 和 8 的扩容有什么区别”，你答得上吗？HashMap 的扩容机制远比你想象的复杂，尤其是 JDK 8 引入的高低位拆分优化。

今天咱们把 HashMap 的扩容机制从触发到迁移彻底讲透。

一、先说结论：扩容核心事实

维度	说明
触发条件	size > capacity × loadFactor
扩容比例	2 倍
新容量	旧容量 << 1
元素迁移	JDK 7：重新 hash；JDK 8：高低位拆分
链表顺序	JDK 7：倒序；JDK 8：保持原序
树的拆分	红黑树拆成两棵子树，可能退化为链表

一句话记住：HashMap 扩容像仓库搬家——东西太多就换个两倍大的仓库，每件东西重新算放在哪。

二、触发时机：两种情况

情况一：元素数量超过阈值

// putVal 末尾
if (++size > threshold)  // size > 容量 × 0.75 👈
    resize();

注意：是整体 size 超过阈值，不是某个桶的链表过长。

情况二：链表转树时数组太短

// treeifyBin 方法
if (tab == null || tab.length < MIN_TREEIFY_CAPACITY)
    resize();  // 数组 < 64，优先扩容而非转树 👈

为什么？ 数组太小时，扩容比转树更有效——扩容后元素分散到更多桶，链表自然变短。

三、JDK 8 扩容的核心：高低位拆分

这是 JDK 8 最大的优化——扩容时不需要重新计算 hash！

核心发现： 容量从 n 扩到 2n，元素的新位置只有两种可能：

原位置 index = hash & (n - 1)
新位置要么 = index           → 低位
新位置要么 = index + n       → 高位 👈

判断方法：看 hash 的新增高位位是否为 1

图解：

容量 n = 16（二进制 10000），n-1 = 01111
容量 2n = 32（二进制 100000），2n-1 = 011111

hash = 19（二进制 10011）
旧位置 = 10011 & 01111 = 00011 = 3
新位置 = 10011 & 011111 = 10011 = 19 = 3 + 16 👈 高位！

hash = 3（二进制 00011）
旧位置 = 00011 & 01111 = 00011 = 3
新位置 = 00011 & 011111 = 00011 = 3 👈 低位！

判断规则：

// JDK 8 扩容迁移的核心逻辑
if ((e.hash & oldCap) == 0) {
    // 低位：留在原位置 👈
} else {
    // 高位：移到原位置 + oldCap 👈
}

e.hash & oldCap 就是检查 hash 在新增的那一位是否为 1。

四、扩容迁移详解

链表迁移

// JDK 8 源码（简化）
Node<K,V> loHead = null, loTail = null;  // 低位链表
Node<K,V> hiHead = null, hiTail = null;  // 高位链表

do {
    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 = e.next) != null);

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

JDK 7 的问题： 每个元素重新计算 hash 并头插法插入新链表，多线程下可能导致链表成环。

JDK 8 的改进： 高低位拆分 + 尾插法，保持原顺序，避免成环。

红黑树迁移

// 红黑树也按高低位拆分
TreeNode<K,V> loHead, loTail;
TreeNode<K,V> hiHead, hiTail;

// 拆分后
if (loHead != null) {
    if (loHead.树节点数 <= UNTREEIFY_THRESHOLD)  // ≤ 6
        newTab[j] = loHead.untreeify();  // 退化为链表 👈
    else
        newTab[j] = loHead;  // 仍然是红黑树
}

红黑树拆分后可能退化为链表——因为元素分散到两棵子树，每棵的节点数可能 ≤ 6。

五、扩容的性能代价

时间复杂度：O(n)——需要遍历所有元素并迁移。

空间复杂度：O(2n)——新旧两个数组同时存在。

优化建议：

// ✅ 预知元素数量，指定初始容量，避免多次扩容
int expectedSize = 1000;
int capacity = (int) (expectedSize / 0.75) + 1;  // 1334
Map<String, String> map = new HashMap<>(capacity);

// ❌ 默认容量，多次扩容
Map<String, String> map = new HashMap<>();  // 16 → 32 → 64 → ... → 1024（7 次扩容）

Guava 的便捷方法：

Maps.newHashMapWithExpectedSize(1000);  // 👈 自动计算初始容量

HashMap 扩容机制 全景

HashMap 扩容机制 全景

触发条件
├── size > capacity × 0.75
└── 链表转树时数组 < 64 → 优先扩容

扩容比例
├── 新容量 = 旧容量 × 2
├── 新阈值 = 新容量 × 0.75
└── 最大容量 = 2^30

JDK 8 高低位拆分
├── 核心发现 ── 新位置 = 原位置 或 原位置 + oldCap
├── 判断方法 ── (hash & oldCap) == 0 → 低位，否则高位
├── 链表 ── 拆成两条，尾插保持原序
└── 红黑树 ── 拆成两棵，可能退化为链表

JDK 7 vs JDK 8
├── 迁移方式 ── 重新hash vs 高低位拆分
├── 插入方式 ── 头插法 vs 尾插法
└── 链表顺序 ── 倒序 vs 保持原序

口诀：扩容两倍阈值触发，高低拆分是精髓，
      低位原位高位加，尾插保序防成环，
      预知大小先指定，省得扩容费功夫。

回答技巧与点评

标准回答

HashMap 在元素数量超过容量 × 负载因子（默认 0.75）时触发扩容，新容量为旧容量的 2 倍。JDK 8 的扩容采用高低位拆分优化——容量从 n 扩到 2n 时，元素的新位置只有两种可能：原位置或原位置 + oldCap，通过 (hash & oldCap) == 0 判断。这种方式不需要重新计算 hash，而且尾插法保持了链表的原顺序，避免了 JDK 7 头插法在多线程下链表成环的问题。红黑树拆分后如果节点数 ≤ 6 会退化为链表。

加分回答

1. 高低位拆分的数学本质：容量 n 是 2 的幂，n-1 的二进制是 k 个 1。扩容到 2n 后，2n-1 是 k+1 个 1。新增的那一位正好对应 oldCap 的那一位。所以 hash & oldCap 判断的就是新增位是否为 1——这是"容量必须是 2 的幂"带来的数学性质
2. 为什么负载因子是 0.75：统计学上，负载因子 0.75 时链表长度的期望值约为 0.5，即大部分桶只有 0-1 个元素。这个值在时间和空间之间取得了很好的平衡——0.5 太浪费空间，1.0 碰撞太多
3. 扩容期间的并发问题：即使 JDK 8 的尾插法避免了链表成环，HashMap 在多线程下仍然不安全——put 可能丢失数据、size 可能不准确。不要以为 JDK 8 修复了"死循环"就等于 HashMap 线程安全了

面试官点评

这道题考的是你对 HashMap 扩容细节的深入理解。能说出"超过阈值扩容、2 倍扩容"是基本要求，能讲清楚 JDK 8 的高低拆分原理和尾插法改进，才算及格。如果你能从数学角度解释高低位拆分的本质、分析红黑树的退化逻辑、强调 HashMap 仍然不线程安全，面试官会认为你对扩容机制的理解已经深入到设计和数学层面。

原文阅读

---

内容有帮助？点赞、收藏、关注三连！评论区等你 💪