被问懵了：什么是负载因子？为什么是0.75？

前几天面试被问懵了，还是关于 HashMap 的面试题，什么是负载因子？为什么是0.75？第一个问题还好回答，然而第二个问题就有点含糊其辞说不清楚了，所以今天就来好好复盘一下这道题。

HashMap 负载因子 load factor，也叫做扩容因子和装载因子，它是 HashMap 在进行扩容时的一个阈值，当 HashMap 中的元素个数超过了容量乘以负载因子时，就会进行扩容。默认的负载因子是 0.75，也就是说当 HashMap 中的元素个数超过了容量的 75% 时，就会进行扩容。当然，我们也可以通过构造函数来指定负载因子，如下所示：
被问懵了：什么是负载因子？为什么是0.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 个键的数目。根据二项式定理，桶为空的概率为：