问题

17. HashMap 什么时候会触发扩容？扩容的代价是什么？如何减少扩容次数？

标准答案

HashMap 触发扩容的条件是元素个数（size）超过 capacity * loadFactor，默认负载因子为 0.75，即当元素数量超过桶容量的 75% 时，HashMap 会扩容为原来的 2 倍，并重新计算所有元素的哈希位置（rehash）。扩容的代价主要包括创建更大数组、重新计算哈希值、数据迁移，会导致较高的 CPU 和内存开销。减少扩容次数的方法包括：

1. 合理预估元素数量，通过 new HashMap<>(initialCapacity, loadFactor) 预设初始容量，避免频繁扩容。
2. 使用合适的负载因子，高负载因子（如 0.8~0.9）可以减少扩容，但可能导致更多哈希冲突。
3. 使用静态哈希表（如 ImmutableMap）避免动态扩容，在高并发场景使用 ConcurrentHashMap。

答案解析

HashMap 的存储结构与扩容触发条件

HashMap 的底层数据结构是数组 + 链表 + 红黑树（JDK 1.8 之后），数据存储在Node<K,V>[] table 数组中。当 put() 方法插入新元素时，会计算哈希值并存入数组对应索引。如果数组装填超过阈值（threshold），就会触发扩容，公式如下：

threshold = capacity * loadFactor;

默认情况下（loadFactor = 0.75）：

• 初始 capacity = 16，threshold = 16 × 0.75 = 12，当存入第 13 个元素时触发扩容。
• 扩容后，capacity = 32，threshold = 32 × 0.75 = 24，当存入第 25 个元素时再次扩容。

HashMap 扩容的完整执行流程

当 HashMap 触发扩容时，resize() 方法会执行以下操作：

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) { // 已存在数组
        newCap = oldCap << 1; // 容量翻倍
        newThr = oldThr << 1; // 计算新阈值
    } else { // 第一次创建
        newCap = DEFAULT_INITIAL_CAPACITY; // 默认16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    for (Node<K,V> e : oldTab) { // 遍历旧数组，重新映射
        do {
            Node<K,V> next = e.next;
            int i = e.hash & (newCap - 1); // 计算新索引
            e.next = newTab[i]; // 头插法
            newTab[i] = e;
        } while ((e = next) != null);
    }
    return newTab;
}

详细步骤如下：

1. 计算新容量和阈值：capacity *= 2，threshold *= 2。
2. 创建新的 Node<K, V>[] 数组，容量翻倍。
3. 遍历旧数组，重新计算哈希值，迁移数据。
4. 元素重新分布：哈希索引变化规则：

   newIndex = oldIndex & (newCapacity - 1)
   

   由于 capacity 是 2 的幂次方，扩容后索引要么不变（hash & oldCap == 0），要么偏移 oldCap 个位置，减少 rehash 计算。

HashMap 扩容的代价分析

扩容操作涉及多个昂贵的计算：

1. 数组创建开销

   • Java 需要在堆上申请新的数组对象，并在 Eden 区分配内存。
   • 如果扩容后 old 数组仍然有强引用，可能导致 GC 迟迟无法释放旧数据。

2. 数据迁移（rehash）

   • 旧数组中的所有元素都需要重新计算哈希值，新哈希值可能导致不同的索引位置变化。
   • 在 Java 7 及以前，扩容时采用尾插法，多线程下可能导致环形链表（死循环）。
   • 在 Java 8 之后，采用头插法和低位掩码优化，减少 rehash 开销。

3. CPU 计算开销

   • 由于 hashCode() 可能涉及复杂计算，每个元素的哈希值重新计算会占用 CPU 资源，影响性能。

4. 影响 GC（垃圾回收）

   • 扩容导致旧数组被废弃，触发 GC 清理大量对象，导致**Stop-the-world（STW）**暂停时间变长。
   • 迁移期间可能造成大对象晋升到老年代，引发 Full GC。

如何减少扩容次数

1. 合理预估初始容量

   • 计算公式：

     capacity = (expectedSize / loadFactor) + 1
     

   • 例如预计存储 1000 个元素，最小 capacity = (1000 / 0.75) ≈ 1333（向上取 2 的幂，即 2048）。
   • 代码示例：

     Map<String, Integer> map = new HashMap<>(2048);
     

   • 这样可以一次性分配足够大的数组，避免后续扩容。

2. 降低扩容阈值，优化负载因子

   • 默认 loadFactor = 0.75，可以适当调高（如 0.9）减少扩容，但可能增加哈希冲突。
   • 适用于写少读多的应用，如缓存、只读字典表等。

3. 避免并发环境下使用 HashMap

   • HashMap 线程不安全，扩容时可能导致死循环或数据丢失。
   • 推荐使用 ConcurrentHashMap，它采用分段扩容，避免全局 rehash。

深入追问

1. 为什么 HashMap 扩容时选择 2 倍增长，而不是其他增长方式？

   • 2 的幂次倍增可以确保 hash & (newCap - 1) 计算索引时无需取模，提高计算效率。
   • 取模 % 操作在 CPU 上比位运算 & 慢 10 倍以上。

2. 扩容对 GC 有何影响？

   • 由于数组对象是大对象，扩容时可能直接晋升到老年代，导致 Full GC，影响吞吐量。
   • 解决方案：使用 -XX:+UseG1GC，减少老年代 GC 影响。

3. ConcurrentHashMap 如何优化扩容？

   • 采用分段扩容，避免全局锁，并发扩容时不同桶可以独立扩展。
   • 采用 CAS + 迁移指针 进行渐进式扩容，不会一次性迁移所有数据。

相关面试题

• HashMap 为什么扩容必须是 2 的幂？
• HashMap 如何优化 rehash？
• ConcurrentHashMap 如何避免 HashMap 扩容引起的性能问题？