前几天面试被问懵了,还是对于 HashMap 的面试题,什么是负载因子?为什么是 0.75?第一个问题还好答复,然而第二个问题就有点含糊其辞说不清楚了,所以明天就来好好复盘一下这道题。
HashMap 负载因子 load factor,也叫做扩容因子和装载因子,它是 HashMap 在进行扩容时的一个阈值,当 HashMap 中的元素个数超过了容量乘以负载因子时,就会进行扩容。默认的负载因子是 0.75,也就是说当 HashMap 中的元素个数超过了容量的 75% 时,就会进行扩容。当然,咱们也能够通过构造函数来指定负载因子,如下所示:
扩容计算公式
HashMap 扩容的计算公式是:initialCapacity * loadFactor = HashMap 扩容。
其中,initialCapacity 是初始容量,默认值为 16(懒加载机制,只有当第一次 put 的时候才创立),loadFactor 是负载因子,默认值为 0.75。也就是说当 16 * 0.75 = 12 时,HashMap 就会开始扩容。
为什么要进行扩容?
HashMap 扩容的目标是为了缩小哈希抵触,进步 HashMap 性能的。
为什么默认负载因子是 0.75?
HashMap 负载因子 loadFactor 的默认值是 0.75,为什么是 0.75 呢?官网给的答案是这样的:
As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.
下面的意思,简略来说是默认负载因子为 0.75,是因为它提供了空间和工夫复杂度之间的良好均衡。
负载因子太低会导致大量的空桶节约空间,负载因子太高会导致大量的碰撞,升高性能。0.75 的负载因子在这两个因素之间获得了良好的均衡。
负载因子 0.75 的迷信揣测
也就是说官网并未对负载因子为 0.75 做过的的解释,只是大略的说了一下,0.75 是空间和工夫复杂度的均衡,但更多的细节是未做阐明的,然而 Stack Overflow 一位大神 https://stackoverflow.com/questions/10901752/what-is-the-significance-of-load-factor-in-hashmap 从迷信的角度揣测了这个问题的答案。
简略来说是通过二项式哈希函数的抵触概率来解释 0.75 这个问题的。
假如一个哈希桶为空和非空的概率为 0.5,咱们用 s 示意容量,n 示意已增加元素个数。
用 s 示意增加的键的大小和 n 个键的数目。依据二项式定理,桶为空的概率为:
P(0) = C(n, 0) (1/s)^0 (1 – 1/s)^(n – 0)
因而,如果桶中元素个数小于以下数值,则桶可能是空的:
log(2)/log(s/(s – 1))
当 s 趋于无穷大时,如果减少的键的数量是 P(0) = 0.5,那么 n/s 很快趋近于 log(2),而 log(2) ~ 0.693。
所以,正当值大略在 0.7 左右,这就是对负载因子为 0.75 的一个迷信揣测。
小结
负载因子 loadFactor 是 HashMap 在进行扩容时的一个阈值,扩容的计算公式是:initialCapacity * loadFactor = HashMap 扩容。它的默认值为 0.75,此值提供了空间和工夫复杂度之间的良好均衡。
参考文章
https://hollischuang.gitee.io/tobetopjavaer/#/basics/java-bas…
本文已收录至《Java 面试突击》,专一 Java 面试 100 年,查看更多:www.javacn.site