说说 HashMap 的扩容机制？如何扩容的？

2026年01月21日

面试考察点

当面试官提出这个问题时，他不仅仅是想听你复述 “当元素超过容量*负载因子时，容量会翻倍” 这个基础事实。他更深层次地希望考察你：

对核心机制的理解深度：你是否能清晰地阐述从触发条件到完成迁移的完整流程？
对性能影响的认知：你是否理解扩容是一个 “昂贵” 的操作？能否解释其时间复杂度，以及如何通过初始化容量来优化？
对底层实现的掌握：你是否了解 JDK 8 前后（尤其是引入红黑树后）扩容机制的关键优化（如高位链表和低位链表的拆分）？
对并发安全的警惕性：你是否意识到 HashMap 在并发扩容时可能导致的问题（如死循环）？这自然引向对 ConcurrentHashMap 的探讨。
对设计抉择的理解：你是否能解释为什么容量总是保持为 2 的幂次方？这与扩容机制和哈希计算有何关联？

核心答案

HashMap 的扩容发生在当前元素数量超过 容量 * 负载因子 时。默认负载因子为 0.75，默认初始容量为 16。

扩容过程核心分为三步：

计算新容量和新阈值：新容量 = 旧容量 * 2，新阈值 = 新容量 * 负载因子。
创建新数组：实例化一个新的 Node<K， V>[] 数组，长度为新容量。
迁移数据（重哈希）：遍历旧数组的每个桶，将其中的所有键值对重新计算哈希位置（(新容量 - 1) & hash），并放入新数组对应的桶中。在 JDK 8 中，此过程针对链表和红黑树进行了优化。

深度解析

原理/机制

触发时机：每次执行 put 操作后，会检查 if (++size > threshold) resize();。注意，是在插入后检查。
为何是 2 的幂：为了使 (n - 1) & hash 这个取模操作等效于 hash % n，且效率更高。这保证了扩容时，原桶中的元素在新数组中的位置要么在原索引处，要么在原索引加上旧容量的偏移处。这是实现高效迁移的关键。
JDK 8 的优化 - 高低位链表拆分：迁移链表时，不再像 JDK 7 那样逐个重新计算并头插，而是利用 hash & oldCap 的结果（oldCap 为旧容量）。如果结果为 0，则元素在新数组的低位（原索引）；如果结果不为 0，则元素在高位（原索引 + oldCap）。这样，一个链表最多被拆分成两个链表，并保持原有顺序，避免了 JDK 7 并发扩容下可能产生的死循环问题。

代码示例 (JDK 8+ resize() 方法关键片段摘录与解析)：

// 假设 oldTab 为旧数组， newTab 为新数组
for (int j = 0; j < oldCap; ++j) {
    Node<K，V> e;
    if ((e = oldTab[j]) != null) {
        oldTab[j] = null; // 清空旧桶，帮助GC
        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; // 高位链表头尾
            Node<K，V> next;
            do {
                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;
                }
            } while ((e = next) != null);
            // 将拆分后的链表放入新数组
            if (loTail != null) {
                loTail.next = null;
                newTab[j] = loHead; // 放入原索引位置（低位）
            }
            if (hiTail != null) {
                hiTail.next = null;
                newTab[j + oldCap] = hiHead; // 放入原索引+oldCap位置（高位）
            }
        }
    }
}

最佳实践

预估容量：如果你能预估要存储的元素数量 N，在创建 HashMap 时，应指定初始容量为 (N / loadFactor) + 1，以避免或减少扩容次数。例如，要存 1000 个元素，应使用 new HashMap<>( (int)(1000/0.75) + 1 ) 或更简单地 new HashMap<>(1337)。
权衡负载因子：负载因子 0.75 是空间和时间成本的一个较好折衷。提高它（如 1.0）可以减少空间开销但增加哈希冲突；降低它可以减少冲突但增加扩容频率。

常见误区

误认为初始化容量就是最终能存的元素数：能存多少取决于 阈值（threshold），而不是 容量（capacity）。new HashMap<>(16) 在默认负载因子下，存第 13 个元素时就会触发扩容。
忽视扩容的性能开销：扩容涉及创建新数组、重新计算哈希和复制数据，其时间复杂度为 O(n)。在性能敏感或数据量大的场景，初始化时指定合适容量至关重要。
在并发环境中直接使用 HashMap：HashMap 非线程安全，多线程并发 put 和 resize 可能导致数据错乱、死循环（JDK 7）或元素丢失。应使用 ConcurrentHashMap。

总结

HashMap 的扩容机制是其高性能的基石，也是一个典型的以空间换时间的策略；理解其触发条件、2 的幂次方设计、以及 JDK 8 优化的高低位链表拆分，是掌握其精髓和进行有效性能调优的关键。

发布于2026年01月21日|17:03:02