HashMap是先进行元素插入还是先进行扩容？请说明一下原因？

八股文_Java集合面试题 0 3

参考回答**

在 Java 8 的 HashMap 中，当我们向 HashMap 中插入一个元素时，HashMap 是先检查是否需要扩容，再进行元素插入。

原因

1. 保证数据存储的一致性

如果先插入元素再扩容，扩容时需要重新计算所有元素的哈希值并重新分配桶的位置（rehash）。如果插入的元素在扩容前被计算到一个桶中，而扩容后可能会被计算到另一个桶中，这会造成数据不一致。
因此，扩容必须发生在元素插入之前，保证元素在正确的桶中。

2. 避免额外的性能开销

如果在插入时直接进行扩容操作，可以确保新插入的元素直接分配到扩容后的正确位置，避免插入到旧桶后再重新分配的额外操作。
这可以提升插入效率并减少扩容的复杂性。

HashMap 的扩容规则

触发扩容的条件：
- 当 HashMap 中的元素数量超过 扩容阈值（threshold）时，就会触发扩容。
- 扩容阈值=容量（table.length） × 负载因子（loadFactor）。
  - 默认容量为 16，默认负载因子为 0.75，因此初始扩容阈值为 16 × 0.75 = 12。
扩容过程：
- 扩容时，HashMap 会将数组容量翻倍，并将原数组中的元素重新分配到新数组中（rehash）。

插入和扩容的源码解析

在 HashMap 的 put 方法中，可以看到扩容发生在插入之前。以下是 Java 8 中的 put 方法的部分源码：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab;
    Node<K,V> p;
    int n, i;

    // 如果哈希表为空，则进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 计算桶索引，如果当前桶为空，则直接创建新节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 如果桶中已有节点，则进行链表或红黑树操作（省略）
    }

    // 判断是否需要扩容
    if (++size > threshold)
        resize();

    return null;
}

扩容的关键点

resize() 方法的调用：
- 在 putVal 方法中，首先会检查哈希表是否为空（table == null）或是否需要扩容。
- 如果满足条件，会调用 resize() 方法进行扩容。
扩容过程中重新分配元素：
- resize() 方法会将现有元素重新分配到新的哈希表中，计算新的桶索引。

示例：验证扩容发生在插入之前

下面的代码展示了 HashMap 扩容的触发过程：

import java.util.HashMap;

public class HashMapResizeExample {
    public static void main(String[] args) {
        HashMap<Integer, String> map = new HashMap<>(4, 0.75f);

        for (int i = 1; i <= 5; i++) {
            System.out.println("Inserting key: " + i);
            map.put(i, "Value" + i);
            System.out.println("Map size: " + map.size());
        }
    }
}

输出示例：

Inserting key: 1
Map size: 1
Inserting key: 2
Map size: 2
Inserting key: 3
Map size: 3
Inserting key: 4
Map size: 4
Inserting key: 5
Map size: 5

为什么扩容优先于插入？

数据一致性：
- 扩容会改变数组大小，元素的存储位置（桶索引）也会发生变化。
- 如果扩容发生在插入之后，插入的元素可能会被分配到错误的桶中，导致数据不一致。
性能优化：
- 如果扩容优先于插入，插入时会直接将元素放入扩容后的桶中，避免了在旧桶中插入后再重新分配的性能损耗。

扩容的时间复杂度

扩容时，需要将所有已有元素重新分配到新的桶中，因此扩容的时间复杂度是 O(n)，其中 n 是 HashMap 中的元素数量。

为了减小扩容的性能影响：

HashMap 使用了 负载因子 来延迟扩容。
Java 8 引入了红黑树，在高冲突场景下降低链表查找的复杂度。

总结

在 HashMap中扩容发生在插入之。
- 通过扩容可以确保新插入的元素直接存储到正确的桶中，避免后续重新分配位置的开销。
扩容的触发条件：
- 当元素数量超过扩容阈值（容量 × 负载因子）时触发。
扩容过程：
- 数组容量翻倍，重新分配现有元素的位置。
扩容优先的原因：
- 保证数据一致性。
- 避免不必要的重复计算，优化性能。