【Java集合篇】负载因子和容量的关系

??典型解析

HashMap 中有几个属性，如 capacity 记录了 HashMap 中 table 的 length，size记录了HashMap中KV的对数，threshold记录了扩容的阈值 (=loadFactor*capacity) ，loadFactor则是负载因子，一般是3/4。


当 HashMap 刚刚初始化的时候，如果不指定容量，那么threshold默认是16，如果指定，则默认是第个比指定的容量大的2的幕(如上文所说)，此时size=0，capacity=threshold=16，loadfactor 默认是0.75F。


当 HashMap 开始装载的时候 (即调用#put方法)，那么size=KV的对数，capacity=16暂时不变，threashold=12 (loadfactor*capacity) ，loadfactor=0.75F。


当 HashMap 中的 size > 12 (threashold) 时，capacity=32 (16 << 1)threashold=24(loadfactor*capacity) ， loadfactor=0.75F。


由此可得，负载因子决定了什么时候扩容，也间接的决定了HashMap中容量的多少。

??loadfactor为啥默认是0.75F，不是1呢?

??为什么HashMap的默认负载因子设置成0.75

我们知道，当负载因子为1的时候，HashMap就只有当容量满了才会扩容，这样会显得更加节省内存空间，HashMap为什么不这样做呢?

首先，当HashMap完全填满时，发生扩容操作的代价会很高，因为需要重新计算所有键的哈希码并重新分配到新的桶中。这可能导致性能下降。而且，随着HashMap中添加的元素越来越多，哈希冲突的概率会增加，因为元素分布在相对较少的桶中，极端情况下可能会导致某个 Entry 下引用了很长的链表，最终的结果就是虽然节省了空间，但是查询和插入都会很耗时间。

在JDK的官方文档中，有这样一段描述：

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).

翻译过来意思大概就是：

一般来说，默认的负载因子(0.75)在时间和空间成本之间提供了很好的权衡。更高的值减少了空间开销，但增加了查找成本(反映在HashMap类的大多数操作中，包括get和put

??0.75的数学依据是什么

另外，我们可以通过一种数学思维来计算下这个值是多少合适。

我们假设一个 bucket 空和非空的概率为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) 约等于0.693…所以合理值大概在0.7左右。

当然，这个数学计算方法，并不是在Java的官方文档中体现的，我们也无从考察到底有没有这层考虑这个推测来源于 Stack Overflor

??0.75的必然因素

理论上我们认为负载因子不能太大，不然会导致大量的哈希冲突，也不能太小，那样会浪费空间。

通过一个数学推理，测算出这个数值在0.7左右是比较合理的。

🤣那么，为什么最终选定了0.75呢?

答：因为threshold=loadFactor*capacity，并且capacity永远都是2的幂，为了保证负载因子 (loadFactor) * 容量 (capacity) 的结果是一个整数，这个值是0.75(3/4)比较合理，因为这个数和任何2的幂乘积结果都是整数。

??HashMap的初始值设为多少合适?

根据阿里巴巴Java开发手册的描述来看：

假如说我们预期的Map中的值为16个，那么我们不能直接使用 new HashMap<>(16)，因为HashMap会在size>12的时候开始扩容，所以合理的方式应该是使用 new HashMap<>(16*4/3+1)才对，这种计算对于开发者来说，显然会复杂一点，所以推荐使用Guava提供的集合工具类，其源码如下：

public static <K,V> HashMap<K，V> newHashMapwithExpectedSize(int expectedsize) {
	return new HashMap<K，V>(capacity(expectedsize));
}

/**
*  Returns a capacity that is sufficient to keep the map from being resized as long as it grows no
* larger than expectedsize and the load factor is > its default (0.75).
*/
static int capacity(int expectedsize) {
	if (expectedsize < 3) {
		checkNonnegative(expectedsize，"expectedsize");
		return expectedsize + 1;
	}
	if (expectedsize < Ints.MAX_POWER_OF_TWO) {
		// This is the calculation used in JDK8 to resize when a putAll
		// happens; it seems to be the most conservative calculation we
		//can make,  0.75 is the default load factor.
		return (int) ((float) expectedsize / 0.75F + 1.0F);
	}
	return Integer.MAX_VALUE; // any large value
}

不过很多时候，我们其实需要的是一些不可变的Map，可以直接使用Guava提供的不可变集合，就没有上面所说的一些问题了。