HashMap的长度为什么要是2的n次方

小鱼儿 2022-10-02 03:49 143阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法；  
这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算，源码中做了优化hash&(length-1)，  
hash%length==hash&(length-1)的前提是length是2的n次方；  
为什么这样能均匀分布减少碰撞呢？2的n次方实际就是1后面n个0，2的n次方-1 实际就是n个1；  
例如长度为9时候，3&(9-1)=0 2&(9-1)=0 ，都在0上，碰撞了；  
例如长度为8时候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞；

其实就是按位“与”的时候，每一位都能 &1 ，也就是和1111……1111111进行与运算

0000 0011 3

& 0000 1000 8

= 0000 0000 0

0000 0010 2

& 0000 1000 8

= 0000 0000 0

\-------------------------------------------------------------

0000 0011 3

& 0000 0111 7

= 0000 0011 3

0000 0010 2

& 0000 0111 7

= 0000 0010 2

当然如果不考虑效率直接求余即可（就不需要要求长度必须是2的n次方了）；

有人怀疑两种运算效率差别到底有多少，我做个测试：

1.  `/**`
2.  `*`
3.  `* 直接【求余】和【按位】运算的差别验证`
4.  `*/`
5.  `public static void main(String[] args) {`
6.  
7.  `long currentTimeMillis = System.currentTimeMillis();`
8.  `int a=0;`
9.  `int times = 10000*10000;`
10. `for (long i = 0; i < times; i++) {`
11. `a=9999%1024;`
12. `}`
13. `long currentTimeMillis2 = System.currentTimeMillis();`
14. 
15. `int b=0;`
16. `for (long i = 0; i < times; i++) {`
17. `b=9999&(1024-1);`
18. `}`
19. 
20. `long currentTimeMillis3 = System.currentTimeMillis();`
21. `System.out.println(a+","+b);`
22. `System.out.println("%: "+(currentTimeMillis2-currentTimeMillis));`
23. `System.out.println("&: "+(currentTimeMillis3-currentTimeMillis2));`
24. `}`

结果：

783,783  
%: 359  
&: 93

转载于:https://my.oschina.net/xiaominmin/blog/1845384

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220113/c2ad51a2cfc0480da160f4f488502695.png