HashMap的数组容量为什么是2的N次幂

HashMap的数组容量为什么是2的N次幂，首先我们要清楚数组的索引值是0到N-1，而hashCode的计算范围是42亿，也就是所有对象的hashCode有42亿种可能，我们要把它丢到这16的长度的数组里面时，我们应该怎么做？怎么将42亿种可能变为0到N-1种可能，通常我们会想到用取模的方法来计算,但是它有两个缺点：
1、负数求余还是负数 2、 性能较慢（对比位运算）

我们来看看HashMap源码是怎么做的，它用的是不是取模运算呢？向HashMap中添加元素，或者扩容时是怎么存放元素的。


第一张图，向HashMap中添加元素putVal()方法的部分源码，可以看出，向集合中添加元素时，会使用(n - 1) & hash的计算方法来得出该元素在集合中的位置；第二张图，resize()扩容方法，可以看出会新建一个数组，然后遍历旧的数组，将旧的元素进过e.hash & (newCap - 1)的计算添加进新的数组中（java 7 好像在扩容这有bug，将旧数组元素添加到新数组时会死锁导致形成环），也就是(n - 1) & hash的计算方法，其中n是数组的容量，hash是添加的元素进过hash函数计算出来的hash值，而这个算法计算出来的数组下标会使得元素平均分布，减少哈希碰撞(哈希碰撞后会形成链，链超过8会形成红黑树)。

那么问题来了，为什么一定要是2的N次幂呢? 和这个(n - 1) & hash这个计算方法有很大关系

从截图看，2的N次幂如果是16（默认初始容量）它的的二进制为10000，减1等于1111，假如此时hash值计算为一个32位int值，最后的结尾位1001，进行按位与&的运算，使用位运算，计算机能直接运算，特别高效，那计算出来的数组下标为1001，那我们为什么要使用2的N次幂，就是为了让length-1拿到的值全部为1，假如不是2的N次幂，那么拿到的值其中某一位会出现为0，那么会导致数组永远会有一些桶是空着的，会导致整个数组分布不均，只有用2的N次幂的时候能够快速计算数组下标并且它的分布还是均匀的。

下面就来看一下HashMap的容量不是2的n次幂的情况，当容量为10时，二进制为01010，(n-1)的二进制是01001，向里面添加同样的元素，结果为：

可以看出，有三个不同的元素进过&运算得出了同样的结果，严重的hash碰撞了。

终上所述，HashMap计算添加元素的位置时，使用的位运算，这是特别高效的运算；另外，HashMap的初始容量是2的n次幂，扩容也是2倍的形式进行扩容，是因为容量是2的n次幂，可以使得添加的元素均匀分布在HashMap中的数组上，减少hash碰撞，避免形成链表的结构，使得查询效率降低！