HashMap 为什么扩容策略是倍增
HashMap 的扩容策略通常是倍增（2倍扩容），这种设计是基于性能和空间效率的平衡。
[!summary]
HashMap选择 2 倍扩容的原因主要包括以下几点：
- 减少哈希冲突，提高查询效率。
- 基于负载因子设计，2 倍扩容在时间和空间的平衡上表现更优。
- 扩容后的再哈希操作简单高效。
- 适度扩容避免频繁扩容带来的性能损耗，也避免浪费过多内存。
这种扩容策略已经证明是大多数应用场景中非常高效的做法。
1 避免频繁扩容，减少哈希冲突
HashMap 的底层数据结构是数组（称为哈希桶），其中每个数组位置（桶）存储链表或红黑树。当哈希表中的元素数量逐渐增多时，哈希冲突的概率也会增加，影响查找效率。为了解决这个问题，HashMap 会进行扩容。
扩容为原容量的两倍有助于减少哈希冲突，从而保持高效的 O(1) 查找性能。
如果每次扩容只是少量增加（比如增加一小部分），哈希冲突问题仍然存在，扩容后的哈希表仍然容易变得稠密。这会导致频繁的再哈希操作，从而影响性能。
2 负载因子与扩容
HashMap 的默认负载因子是 0.75，当填充率达到 75% 时，HashMap 会触发扩容。
比如一个大小为 16 的 HashMap，当插入 12 个元素时（16 × 0.75 = 12），就会触发扩容。
扩容后的容量为原来的两倍，意味着新容量为 32。这使得在扩容后的哈希表中，原先的哈希冲突可能会显著减少，因为散列空间增大了两倍，从而让更多的元素分布在新的桶中。
3 再哈希计算简单
HashMap 扩容为 2 倍时，重新计算哈希的位置只需要对哈希值的高位做判断。
HashMap 使用哈希值模数组长度（hash % length）来确定元素在数组中的位置。由于长度是 2 的幂次，取模运算可以简单地通过位操作来完成：
index = hash & (length - 1)这个公式可以快速地根据新的数组大小重新分配元素位置，而无需复杂的数学运算。当数组大小为 2 的幂次时，这种位运算比取模操作高效得多，因此扩容后的再哈希效率更高。
4 空间和时间的折中
倍增策略在性能和空间之间取得了一个平衡：
- 如果扩容倍数太小（比如扩容 1.5 倍），会导致频繁的扩容，带来性能开销。
- 如果扩容倍数太大（比如扩容 4 倍），会消耗大量的内存，并且某些情况下可能导致过度分配内存，浪费空间。
2 倍扩容既可以保证较少的扩容次数，又可以保证每次扩容后有足够的空间存储新元素，而不会浪费太多内存。
5 结合其他常见数据结构的设计
倍增扩容不仅在 HashMap 中常见，它也是其他数据结构的常用策略。例如，ArrayList 的动态数组也会在扩容时采用 1.5 倍或 2 倍扩容策略。