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 倍扩容策略。