解释一下HashMap是如何进行扩容的？

八股文_Java集合面试题 0 2

参考回答**

HashMap 的扩容（resize）是指当存储的键值对数量超过容量阈值时，自动将容量扩大为原来的两倍，以保证其性能。扩容的过程包括分配新的数组和重新哈希旧数组中的键值对。

以下是 HashMap 扩容的核心步骤：

触发条件
扩容发生在插入新元素时，如果当前元素数量超过了 threshold（容量 * 负载因子），则触发扩容。
容量翻倍
新数组的容量为原数组容量的两倍，保持容量为 2 的幂次方。
重新哈希（Rehashing）
将旧数组中的键值对重新分配到新数组中，重新计算每个键值对在新数组中的位置。
性能影响
扩容是一种代价较高的操作，需要分配新内存并重新计算所有键值对的位置，因此应尽量避免频繁扩容。

详细讲解与源码分析

以下是扩容的源码解析与详细过程说明：

1. 触发扩容

扩容的触发条件是插入新元素后，当前元素数量 size 超过了 threshold。threshold 的计算公式为：

threshold = capacity * loadFactor;

capacity 是数组的当前容量（初始为 16）。
loadFactor 是负载因子，默认值为 0.75。

例如，当初始容量为 16 且负载因子为 0.75 时，threshold = 16 * 0.75 = 12。当插入第 13 个元素时会触发扩容。

2. 扩容逻辑：resize()

resize() 方法是 HashMap 中扩容的核心实现，主要代码如下：

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) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE; // 超过最大容量不再扩容
            return oldTab;
        }
        newCap = oldCap << 1; // 容量翻倍
        newThr = oldThr << 1; // 阈值翻倍
    } else if (oldThr > 0) { // 使用初始阈值
        newCap = oldThr;
    } else { // 默认初始容量
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    // 创建新数组
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    threshold = newThr;

    // 将旧数组中的键值对迁移到新数组
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != 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;
                    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; // 高位链表
                    }
                }
            }
        }
    }
    return newTab;
}

3. 具体扩容步骤解析

计算新容量和阈值
- 新容量是旧容量的两倍。
- 新阈值是旧阈值的两倍。
创建新数组
分配一个大小为新容量的数组，用于存储新的键值对。
重新哈希键值对
遍历旧数组，将其中的键值对重新分配到新数组中。
- 对于链表，使用 (e.hash & oldCap) == 0 来区分节点是留在旧索引还是移到新索引。
红黑树的拆分
如果桶中是红黑树，则调用 split() 方法将红黑树拆分到新数组中。

4. 举例：扩容过程

假设初始容量为 4，负载因子为 0.75，当前存储了 3 个键值对，当插入第 4 个键值对时，触发扩容：

初始状态

数组索引	键值对
0	A
1	B
2	null
3	C

扩容后容量
新容量 = 4 * 2 = 8，新数组大小为 8。
重新哈希

键 A 的哈希值映射到新数组的索引 0。
键 B 的哈希值映射到新数组的索引 1。
键 C 的哈希值映射到新数组的索引 7。

新数组索引	键值对
0	A
1	B
2	null
3	null
4	null
5	null
6	null
7	C

5. 扩展知识

扩容的时间复杂度

扩容涉及重新分配内存和迁移数据，时间复杂度为 O(n)，其中 n 是 HashMap 中的元素数量。

如何减少扩容的影响？

在创建

“`
HashMap
“`

时指定初始容量，避免频繁扩容。例如：

“`java
HashMap<String, String> map = new HashMap<>(32);
“`

扩容带来的影响

扩容会导致所有键值对重新分配位置，因此 HashMap 不适合频繁插入的场景。
在多线程环境下扩容可能导致死循环，建议使用线程安全的 ConcurrentHashMap。