面试题：Java 中 HashMap 的扩容机制是怎样的？

在 Java 中，HashMap 的扩容机制是为了在键值对数量增加时，动态调整数组容量以减少哈希冲突并保持高效的查询和插入性能。以下是其核心原理和流程的详细解析：

1. 扩容触发条件

当 HashMap 中的键值对数量 超过当前容量与负载因子的乘积 时，会触发扩容。

默认负载因子：0.75
默认初始容量：16
示例：
- 初始容量为 16，负载因子为 0.75 → threshold = 16 × 0.75 = 12
- 插入第 13 个元素时触发扩容。

2. 扩容流程（resize 方法）

扩容的核心流程分为四步，具体如下：

Step 1: 创建新数组

新容量翻倍：newCap = oldCap << 1（即 oldCap × 2）
更新阈值：newThr = oldThr << 1（即 oldThr × 2）
示例：
- 旧容量为 16 → 新容量为 32
- 旧阈值为 12 → 新阈值为 24

Step 2: 遍历旧数组

遍历旧数组中的每个桶（bucket），处理其中的节点（链表或红黑树）。

Step 3: 数据迁移（关键优化）

无需重新计算哈希值：
- 在 JDK 8 中，通过 位运算 判断元素的新位置，仅需检查哈希值的高位是否为 1：
  - 若 (e.hash & oldCap) == 0 → 新索引 = 原索引
  - 否则 → 新索引 = 原索引 + oldCap
- 原理：
  - 容量始终为 2 的 n 次方，扩容后新容量是旧容量的 2 倍。
  - 哈希值的高位决定了元素在新数组中的位置，避免了全量哈希重计算。
- 示例：
  - 旧容量为 16（二进制 10000），新容量为 32（二进制 100000）。
  - 哈希值的第 5 位（从右往左）为 0 → 位置不变；为 1 → 位置变为 原索引 + 16。
链表/红黑树拆分：
- 链表：拆分为两个链表（低位链和高位链），分别放入新数组的 原索引 和 原索引 + oldCap。
- 红黑树：先拆分为链表，若链表长度 ≤ 6 → 退化为链表；否则重建红黑树。
- 尾插法：JDK 8 使用尾插法避免多线程下的死循环问题（JDK 7 头插法存在此风险）。

Step 4: 更新引用

将新数组设置为 HashMap 的 table，完成扩容。

3. 扩容优化的关键点

(1) 2 的 n 次方容量设计

索引计算：使用位运算 (hash & (capacity - 1)) 替代取模运算，效率更高。
扩容迁移：仅需判断哈希值的高位即可确定新位置，避免全量哈希重计算。

(2) 链表转红黑树的逻辑

链表长度 ≥ 8 且数组长度 < 64：优先扩容而非树化（避免小数组下频繁树化开销）。
链表长度 ≥ 8 且数组长度 ≥ 64：链表转红黑树。
红黑树节点数 ≤ 6：退化为链表。

(3) 线程安全问题

JDK 7：头插法迁移链表节点 → 多线程下可能导致链表成环（get() 死循环）。
JDK 8：尾插法 → 避免成环，但 HashMap 仍非线程安全（需使用 ConcurrentHashMap）。

4. 性能与优化建议

(1) 扩容代价

时间复杂度：O(n)（需遍历所有节点并迁移）。
优化建议：
- 预估数据量：初始化时设置合适的容量（initialCapacity），减少扩容次数。
  - 计算公式：initialCapacity ≈ 预期元素数 / 负载因子。
  - 示例：预期存储 20 个元素 → 20 / 0.75 ≈ 27 → 设置 initialCapacity = 32。

(2) 负载因子的平衡

负载因子太小（如 0.5）：频繁扩容 → 内存浪费。
负载因子太大（如 1.0）：哈希冲突增加 → 查询性能下降。
默认值 0.75：在空间利用率和时间性能之间取得最佳平衡。

5. 扩容流程图解

初始状态：capacity=16, threshold=12
插入第13个元素 → 触发扩容
新容量=32, 新阈值=24
迁移元素：
  - 哈希值高位为0 → 原索引位置
  - 哈希值高位为1 → 原索引 + 16
链表拆分：
  - 低位链 → 放入新数组[原索引]
  - 高位链 → 放入新数组[原索引 + 16]

6. 源码片段（JDK 8）

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    // Step 1: 计算新容量和新阈值
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        newCap = oldCap << 1; // 容量翻倍
        newThr = oldThr << 1; // 阈值翻倍
    } else if (oldThr > 0) { // 初始未指定容量
        newCap = oldThr;
        newThr = (int)(oldThr * loadFactor);
    } else { // 默认初始容量
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    // Step 2: 创建新数组
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;

    // Step 3: 数据迁移
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null; // 释放旧数组内存
                // 处理单个节点
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 处理红黑树或链表
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    do {
                        Node<K,V> 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;
                        }
                        e = next;
                    } while (e != null);
                    // 放入低位链
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 放入高位链
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    threshold = newThr;
    return newTab;
}

7. 总结

HashMap 的扩容机制通过 动态调整数组容量 和 高效的数据迁移算法，在空间利用率和时间性能之间取得了平衡。其核心设计包括：

2 的 n 次方容量：确保位运算高效性。
位运算优化迁移：无需重新计算哈希值，仅判断高位即可。
链表/红黑树拆分：减少冲突并保持查询性能。
合理设置负载因子：避免频繁扩容或哈希冲突。

理解这一机制有助于在实际开发中优化 HashMap 的使用，避免性能瓶颈。

THE END

Java 集合类