HashMap初始化大小的选择

创建HashMap时为什么最好要初始化大小?(阿里开发者手册也这样要求)？

我个人理解是这样的，当场景中如果装载数量明确的时候，为避免HashMap因resize而引起的不必要的开销，从而一定程度上可以提高你的性能。所以我们今天来讨论一下HashMap初始化的时候大小如何确定。

场景：我们确定装在100个元素。这时候应该如何确定初始化大小。

首先，了解HashMap中,最重要的两个参数:初始化大小C，加载因子i。

HashMap中初始化大小默认是4

默认加载因子是0.75

加载因子是说,哈希表在其容量自动扩容之前可以达到多满的一个程度,当

哈希表中的数量达到c*i的时候，便会出发resize。075是在空间与时间成本上的一个折中。

回到我们问题的出发点，我们装载100个元素，为在时间与空间上达到最佳性能，HashMap的初始化容量可以设置为：

100/0.75=133.333，向上取整为134。

但是这里还有一个问题，Hash碰撞，当我们将初始化容量设置为134，怎么来保证hash碰撞会是比较少的呢？要么我们需要重写hashCode()方法，否则也没有什么办法来保证。

所以我们引出HashMap为元素选择下标的方法。

n为hash表的长度length，hash为key进行hash后的到的值，而

134-1=128+6-1

那么length-1的二进制后三位为101。

假如，100个元素的key进行hash后得到两个值，他们的二进制除了后三位外，其余位都相同，所以在进行&运算时：

011&101=001；

001&101=001；

这时候他们的值就相等了，这便是hash碰撞。

此外101的第二位是0，所以key的hash无论第二位是1或者0，在进行&运算后得到的结果都是0；这时候，无论key的hash是多少，只要低位第二位值为1，如：1001,1010,0001,0111，这个下标所代表的空间会一直是空的，因为在进行&运算后永远不肯能产生低位第二位为1的值，这就大大浪费了空间，而且还增加了hash碰撞的概率。这显然是很影响效率的。

如何来减少这个问题呢？最好的方法自然是length-1的二进制都是1，所以length最佳的值为length=2^n，只要将hash的长度设置为2的幂次方，这时候所有下标所代表的空间就都是可用的。（这也是面试中经常会问的一个问题的答案，为什么hashMap的扩容是2幂次方）

再次回到我们一开始的问题本身，距离134最近的2的幂次方数是128，但是这时候必然是会引起hashMap的resize操作的，而hashMap的resize操作是代价非常大的。这种方式必然是不可取的（这时设置为128和默认4的长度本质上是没有区别的，因为必然都会引起hashMap扩容）。所以这时候我们可取的长度变为256。

这时候由于长度加大和空间的有效利用，这时的hash碰撞会大大降低，这时的hashMap效率上应该是比较高了。

综上所述，我们一般在初始化大小的时候都可以这样来计算，

2^n=length>(元素个数/0.75+1)，这时候的length应该就是一个表合适的大小了。