面试题：Java中HashMap扩容机制的基本原理是什么以及对性能有哪些直接影响？

Question

请详细阐述Java中HashMap扩容机制，包括扩容的触发条件、扩容的过程，并且分析这种机制对HashMap在添加元素、查询元素等操作时性能的直接影响。

Answer 1

1. 扩容触发条件

• 容量达到阈值：HashMap有两个重要参数，容量（capacity）和负载因子（load factor）。当HashMap中元素的数量（size）达到容量（capacity）与负载因子（load factor）的乘积时，就会触发扩容。例如，默认的初始容量为16，负载因子为0.75，那么当元素数量达到16 * 0.75 = 12时，就会触发扩容。

2. 扩容过程

• 创建新数组：扩容时会创建一个新的数组，新数组的容量是原数组容量的两倍。例如原数组容量为16，扩容后变为32。
• 重新计算哈希值与位置：将原数组中的所有键值对重新计算哈希值，并根据新的容量将其放入新数组对应的位置。这是因为哈希值在计算存储位置时与数组容量有关（通常是通过取模运算，在Java中使用(n - 1) & hash这种更高效的方式计算位置，其中n为数组容量），容量变化后位置可能改变。

3. 对添加元素性能的影响

• 添加元素时：在未触发扩容前，添加元素的时间复杂度通常为O(1)，因为可以快速通过哈希值计算出存储位置。当触发扩容时，由于需要创建新数组并重新计算哈希值和迁移元素，时间复杂度会变为O(n)，n为原HashMap中的元素数量，这会导致在扩容瞬间添加元素的性能明显下降。扩容完成后，添加元素的性能又恢复到接近O(1)。

4. 对查询元素性能的影响

• 查询元素时：在未触发扩容前，查询元素时间复杂度接近O(1)，通过哈希值快速定位到元素所在位置。扩容时，由于元素位置重新计算和迁移，在扩容过程中查询可能出现找不到元素的情况（因为元素正在迁移）。扩容完成后，查询性能恢复正常，但如果扩容不合理导致哈希冲突严重，查询性能会下降，时间复杂度会偏离O(1)，趋近于O(n)。