HashMap初始容量为什么是2的n次幂及扩容为什么是2倍的形式？

快来打我* 2022-10-28 15:19 193阅读 0赞

## 前言 ##

逛了一圈发现大家对于这个问题的回答写的都比较散乱，简而言之两点原因：

**1.得到的新的数组索引和老数组索引只有最高位区别，更快地得到新索引**

**2.rehash时的取余操作，hash % length == hash & (length - 1)这个关系只有在length等于二的幂次方时成立，位运算能比%高效得多**

## 论述 ##

**1.为了保证得到的新的数组索引和老数组索引一致**。HashMap的初始容量是2的n次幂，扩容也是2倍的形式进行扩容，是因为容量是2的n次幂，可以使得添加的元素均匀分布在HashMap中的数组上，减少hash碰撞，避免形成链表的结构，使得查询效率降低！

hashMap的数组长度一定保持2的次幂，比如16的二进制表示为 10000，那么length-1就是15，二进制为01111，同理扩容后的数组长度为32，二进制表示为100000，length-1为31，二进制表示为011111。从下图可以我们也能看到这样会保证低位全为1，而扩容后只有一位差异，也就是多出了最左位的1，这样在通过 h&(length-1)的时候，只要h对应的最左边的那一个差异位为0，就能保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换)，个人理解。  
![image-20210105144132113][]

还有，数组长度保持2的次幂，length-1的低位都为1，会使得获得的数组索引index更加均匀，比如：

![image-20210105144157034][]

我们看到，上面的&运算，高位是不会对结果产生影响的（hash函数采用各种位运算可能也是为了使得低位更加散列），我们只关注低位bit，如果低位全部为1，那么对于h低位部分来说，任何一位的变化都会对结果产生影响，也就是说，要得到index=21这个存储位置，h的低位只有这一种组合。这也是数组长度设计为必须为2的次幂的原因。

![image-20210105144212809][]  
如果不是2的次幂，也就是低位不是全为1此时，要使得index=21，h的低位部分不再具有唯一性了，哈希冲突的几率会变的更大，同时，index对应的这个bit位无论如何不会等于1了，而对应的那些数组位置也就被白白浪费了。

参考文章 [https://blog.csdn.net/samniwu/article/details/90550196][https_blog.csdn.net_samniwu_article_details_90550196]

**2.rehash时的取余操作，hash % length == hash & (length - 1)这个关系只有在length等于二的幂次方时成立，位运算能比%高效得多**。

参考文章[https://www.cnblogs.com/littleKing163/p/5695153.html][https_www.cnblogs.com_littleKing163_p_5695153.html]

[image-20210105144132113]: /images/20221024/1ac4d53b329c4040bfbc47b84ee472b4.png
[image-20210105144157034]: /images/20221024/078e2a688e4e48188f4b4df7bed08ce8.png
[image-20210105144212809]: /images/20221024/3935979711434e029d722d3eb7c30fb7.png
[https_blog.csdn.net_samniwu_article_details_90550196]: https://blog.csdn.net/samniwu/article/details/90550196
[https_www.cnblogs.com_littleKing163_p_5695153.html]: https://www.cnblogs.com/littleKing163/p/5695153.html