Java 集合 - 为什么HashMap的容量是2的幂次方
最近在看集合的源码，看到hashMapd的源码的时候，发现hashMap的容量都是2的幂次方（源码是通过左移运算），于是好奇为什么要这样设计，所以上网查阅了相关资料，但是发现很多资料讲的都不是很清楚，也不是很好理解，所以自己在理解的基础上做了自己的总结，希望我的总结能帮到读者更好的理解这个问题。当然，前提是读者要知道hashMap的数据结构，不然就没法理解我下面的总结，关于hashMap的数据结构，读者可以百度下其他博客，我后面那也会写一篇关于hashMap的数据结构分析的文章。
我们已经知道hashMap的底层数据结构是数组+链表的结构，所以hashMap每次保存的数据都是分散保存在数组的各个index位置，而为了存取效率达到最高，就要要求hashMap每次保存的时候尽量平均分散到数组的各个位置，因为如果每个index位置都只有一个元素的话，不存在链表数据，这样可以避免每次存取都要遍历链表造成额外的时间成本开销；所以我们就想到通过hashMap对数组长度取余运算（hashCode%size），这样可以达到最大的平均分配；但是hashMap的作者想到了如果通过位运算来计算取余的话效率会比10进制的取余运算来的快，因为我们知道计算机的底层运算都是转化位二进制运算的；所以为了位运算的取余效果能到10进制的效果，作者推算出了如果容量为2的N次方的话，那么hash&(length-1) == hash%length;length转为二进制位一个1+N个0，length-1转为二进制位一个0+N个1；则任意的hash值和length-1做位运算，结构都是后面N个位的的二进制，因为length-1的二进制前面都是0，位运算后都是0，相当于舍弃了高位，保留了后面的N位，后面的N位刚好在0-length之间，也就是等于hash%length取余；具体推算过程：
假设hash值为20，hashMap的容量为length=16
十进制取余算法：20%16 = 4；所以任何的hash值得取余都在0-15之间，达到了最有可能得平均分配；
二进制算法：20转为二进制位10100，length-1=15 = 01111；所以二进制算法为10100 & 01111 = 0100 = 4，高位和length-1的0相与后全部舍弃，直接保留了hash值最后N位，而最后N位刚好就是十进制的取余运算的结果；任何hash值都是这样；
再比如随便的二进制的hash值位101010101010111，假设容量length依旧位2的4（N=4）次方16，所以length-1的hash值还是0111，101010101010111和0111相与后结果为0111，十进制为7，相当于高位全部被舍弃，实际上就是保留了hash值的低N位；读者可以将101010101010111转为10进制在对16取余，验证余数是否为7；就是验证公式：hash&(length-1) == hash%length；
假如不是按2的幂次方，随便假设为length = 15，hash= 17，则10进制取余运算为2，二进制位运算为10001&01110 =0，不会等于10进制的的运算结果；而实际上length-1 = 14 = 01110和任何的hash相与，最后的一位的0都会被舍弃，所以任何的hash值和01110相与的结果都不会出现1101（13），1001（9）等数据，所以相当于table的数组中index =13或者9的位置永远不会保存到数据，造成空间浪费；所以就不能用位运算计算key对应的value的值，就要用10进制计算，速度就比不上二进制算法；
所以总结出：如果既要达到最可能的平均分配hashMap的value的在table的各个index，又要用二进制计算实现存取效率，就要要求hashMap的容量必须为2的幂次方；
最后更新于