# 问题

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;
1

默认情况下(loadFactor = 0.75):

  • 初始 capacity = 16threshold = 16 × 0.75 = 12,当存入第 13 个元素时触发扩容。
  • 扩容后,capacity = 32threshold = 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

详细步骤如下:

  1. 计算新容量和阈值capacity *= 2threshold *= 2
  2. 创建新的 Node<K, V>[] 数组,容量翻倍。
  3. 遍历旧数组,重新计算哈希值,迁移数据
  4. 元素重新分布:哈希索引变化规则:
    newIndex = oldIndex & (newCapacity - 1)
    
    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
      
      1
    • 例如预计存储 1000 个元素,最小 capacity = (1000 / 0.75) ≈ 1333(向上取 2 的幂,即 2048)。
    • 代码示例:
      Map<String, Integer> map = new HashMap<>(2048);
      
      1
    • 这样可以一次性分配足够大的数组,避免后续扩容
  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 扩容引起的性能问题?