HashMap底层，负载因子，为啥是2^n？

[问答题]

请你解释HashMap的容量为什么是2的n次幂？

zhaoshg

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进行与运算

发表于 2019-01-20 22:14:38 回复(0)

顶不住也得上啊

一个哈希表，为了减少哈希碰撞，我们首先想到的方法是取余运算，因为取余就可以使得整数均匀地分布到哈希表的每一个位置上。比如现在的哈希表的长度是16，那么11如果要放到哈希表上，那就用11%16,得到了11，那么11就放在索引为11的位置。但是呢，计算机的取余操作效率不高，而位运算的效率是很高的，所以为了提高效率，java的工程师在原码里面就用了x&(length-1)的操作，这里的长度16-1 = 15，11和15做位运算，就是11&（1111），最后得到的结果也是11，也就是说，x&(length-1)的结果是和x%length的结果是一样的，因为当length为2的整数次幂时，length-1的二进制位数上都为1，这样就保证了取余和位运算的结果相等，所以原码为了提高效率就要求长度为2的整数次幂。

发表于 2019-04-12 11:09:22 回复(0)

Promote

HashMap的初始容量和扩容都是以2的次方来进行的，目的时为了减少哈希碰撞，提高代码运行效率。

减少哈希碰撞就是尽量让数组的每一个位置下的链表数为相同, 做法：h & （length - 1)；length 值为2的次方，length-1换算成二进制的话肯定所有位都为1，就比如2的3次方为8，length-1的二进制表示就是111，所以h& (length-1)运算从数值上来讲其实等价于对length取模，也就是h%length，但是按位与比取模运算效率高。

发表于 2019-08-23 17:09:34 回复(0)