391 字
2 分钟
扩容在什么时候呢?为什么扩容因子是 0.75?

扩容在什么时候呢?为什么扩容因子是 0.75?#

HashMap 会在存储的键值对数量超过阈值(即容量 * 加载因子)时进行扩容。

默认的加载因子是 0.75,这意味着当 HashMap 填满了大约 75%的容量时,就会进行扩容。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

默认的初始容量是 16,那就是大于16x0.75=12时,就会触发第一次扩容操作。

那么为什么选择了 0.75 作为 HashMap 的默认加载因子呢?#

简单来说,这是对空间成本和时间成本平衡的考虑。 在 HashMap 中有这样一段注释:

/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize()

关于默认负载因子的注释

我们都知道,HashMap 的散列构造方式是 Hash 取余,负载因子决定元素个数达到多少时候扩容。 假如我们设的比较大,元素比较多,空位比较少的时候才扩容,那么发生哈希冲突的概率就增加了,查找的时间成本就增加了。

我们设的比较小的话,元素比较少,空位比较多的时候就扩容了,发生哈希碰撞的概率就降低了,查找时间成本降低,但是就需要更多的空间去存储元素,空间成本就增加了。

扩容在什么时候呢?为什么扩容因子是 0.75?
作者
强人自传
发布于
2024-02-15
许可协议
CC BY-NC-SA 4.0