彻底拆解 Java HashMap 扩容机制

Java HashMap 是最常用的集合类之一，其扩容（resize）机制是其高效性和动态性的核心。扩容发生在元素数量超过阈值时，目的是减少哈希冲突、保持 O(1) 的平均访问时间。下面从基础原理到源码细节，进行彻底拆解（基于 OpenJDK 17–21 版本，机制基本稳定；JDK 8+ 引入红黑树优化）。

我会结合源码分析、流程图、表格和示例，确保清晰易懂。如果你想看具体版本源码差异，可以提供 JDK 版本，我再细化。

1. HashMap 基础回顾（为什么需要扩容？）

HashMap 底层是数组 + 链表/红黑树的结构：

数组（table）：存储桶（bucket），默认大小 16（2^4），总是 2 的幂次方（便于位运算优化）。
负载因子（load factor）：默认 0.75，表示数组“满”到多少比例时扩容。平衡内存和性能（太高冲突多，太低浪费空间）。
阈值（threshold）：容量 * 负载因子。当 size > threshold 时，触发扩容。
哈希冲突：通过链表（或树）解决，但链表过长会退化为 O(n)，扩容能均匀分布元素。

扩容的核心目标：翻倍容量，重新分布元素，减少冲突。

2. 扩容触发条件

扩容不是随意发生的，主要在 put() 操作中检查：

条件：size >= threshold 且当前桶不为空（优化：如果桶为空，添加元素不会立即扩容）。
时机：通常在 putVal() 方法中，添加元素后检查。
默认值：
初始容量：16
负载因子：0.75
初始阈值：12（16 * 0.75）

示例：添加第 13 个元素时，size=13 > 12，触发扩容。

源码片段（从 HashMap.putVal()）：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // ... 省略哈希计算和桶定位
    if (++size > threshold)  // size 自增后检查
        resize();           // 触发扩容
    // ...
}

3. 扩容过程详解（resize() 方法）

扩容的核心是 resize() 方法：创建新数组，迁移旧元素。

步骤分解：

计算新容量：

新容量 = 旧容量 * 2（oldCap << 1）。
如果旧容量已达最大（2^30），阈值设为 Integer.MAX_VALUE。
更新阈值 = 新容量 * 负载因子。

创建新数组：

Node[] newTab = new Node[newCap];

迁移元素（rehash）：

遍历旧数组的所有桶。
对于每个桶的链表/树：
- 如果是单个节点，直接计算新位置：newIndex = (hash & (newCap - 1))。
- 如果是链表：使用位运算优化拆分链表（无需全量重新哈希）。
- 如果是树：拆分树为两个子链表（如果子链表 > 6，转回链表）。

优化点：由于容量是 2 的幂，rehash 只需检查 hash 的高位 bit（oldCap 对应的 bit）。

如果 (e.hash & oldCap) == 0：留在原位置（lo 链）。
否则：移到 oldIndex + oldCap（hi 链）。

流程伪代码（简化版）：

Node<K,V>[] resize() {
    int oldCap = table.length;  // 旧容量
    int newCap = oldCap << 1;   // 新容量 = 旧 * 2
    int newThr = newCap * loadFactor;  // 新阈值

    Node<K,V>[] newTab = new Node[newCap];  // 新数组

    for (int j = 0; j < oldCap; ++j) {  // 遍历旧桶
        Node<K,V> e = oldTab[j];
        if (e != 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) {  // 关键优化：检查高位 bit
                        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; }
            }
        }
    }
    table = newTab;  // 更新 table
    threshold = newThr;
    return newTab;
}

可视化流程（假设容量从 16 → 32）：

旧桶 index = hash & 15（4 bits）
新桶 index = hash & 31（5 bits）
第 5 bit (16=2^4) 决定：0 → 原位；1 → 原位 + 16

例如：

hash = 0b00001（1） → 新位 = 1 & 31 = 1（原位）
hash = 0b10001（17） → 新位 = 17 & 31 = 17（原位 + 16）

4. 扩容中的关键优化与特性

特性 / 优化	说明	为什么重要？
容量总是 2^n	哈希计算用 `& (cap-1)` 代替 `% cap`，位运算更快。	性能提升，避免慢的模运算。
位运算拆分链表	无需为每个节点重新计算完整 hash，只检查一个 bit。	扩容时间从 O(n) 降到 O(链表长度)。
树化 / 去树化	JDK8+：链表 >8 时转红黑树；扩容后若子链表 <=6，转回链表。	防最坏 O(n) 退化，提高极端场景性能。
延迟扩容	仅当 size > threshold 且桶不空时扩容。	避免不必要的扩容，节省资源。
最大容量	2^30（1<<30），超过后不再扩容（阈值 = Integer.MAX_VALUE）。	防止内存溢出。

5. 扩容的性能影响与注意事项

时间复杂度：扩容 O(n)，因为需遍历所有元素。但平均分摊到每次 put() 是 O(1)。
内存开销：扩容时临时双倍内存（旧+新数组），GC 后释放旧数组。
并发问题：
JDK7 问题：多线程扩容可能导致链表环（无限循环）。源码中链表头插法逆序，导致线程竞争时循环。
JDK8+ 修复：使用尾插法 + 位运算，避免环。但 HashMap 仍非线程安全，推荐 ConcurrentHashMap。
自定义负载因子：构造函数可设（e.g., new HashMap(16, 0.5f)），低负载因子减少冲突，但浪费内存。
初始容量建议：预估元素数，设为 (预计 size / 0.75) 的下一个 2^n，避免多次扩容。

示例：扩容前后变化

HashMap<String, Integer> map = new HashMap<>();  // 容量16，阈值12
for (int i = 0; i < 13; i++) {
    map.put("key" + i, i);  // 第13个时扩容到32
}
System.out.println(map.size());  // 13
// 内部：table 从16→32，所有元素重新分布

6. 常见问题解答

扩容后哈希不变吗？ 不变，但 index 可能变（多一位 bit 参与计算）。
为什么翻倍而不是加固定值？ 翻倍保持 2^n，优化位运算；加固定值需全量重哈希，慢。
空 HashMap 何时扩容？ 添加第一个元素时，初始化 table=16，阈值=12。
HashMap vs Hashtable？ Hashtable 线程安全，但扩容机制类似（翻倍+1，奇数容量）。
生产优化：用 new HashMap((int)(expectedSize / 0.75f) + 1) 预设容量，避免扩容。

总结一句话

Java HashMap 扩容机制通过阈值触发 + 容量翻倍 + 位运算优化迁移，实现了高效动态增长，同时在 JDK8+ 结合树化防退化，确保了高负载下的性能稳定性。

想深入某个部分？如 ConcurrentHashMap 扩容对比、性能测试代码、或特定 JDK 版本差异？随时告诉我～

彻底拆解 Java HashMap 扩容机制