Skip to content

HashMap 为什么扩容策略是倍增

字数
953 字
阅读时间
4 分钟

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 的幂次,取模运算可以简单地通过位操作来完成:

java
index = hash & (length - 1)

这个公式可以快速地根据新的数组大小重新分配元素位置,而无需复杂的数学运算。当数组大小为 2 的幂次时,这种位运算比取模操作高效得多,因此扩容后的再哈希效率更高。

4 空间和时间的折中

倍增策略在性能和空间之间取得了一个平衡:

  • 如果扩容倍数太小(比如扩容 1.5 倍),会导致频繁的扩容,带来性能开销。
  • 如果扩容倍数太大(比如扩容 4 倍),会消耗大量的内存,并且某些情况下可能导致过度分配内存,浪费空间。

2 倍扩容既可以保证较少的扩容次数,又可以保证每次扩容后有足够的空间存储新元素,而不会浪费太多内存。

5 结合其他常见数据结构的设计

倍增扩容不仅在 HashMap 中常见,它也是其他数据结构的常用策略。例如,ArrayList 的动态数组也会在扩容时采用 1.5 倍或 2 倍扩容策略。