为什么是2的n次方？
我们知道，在初始化hashMap时，容量大小Capacity必需满足为2的n次方，为什么需要这个规定呢？

最近在HashMap源码中看到了这样一个表达式

i = (cap - 1) & hash   //putVal方法中摘抄出来的一个表达式

对里面的索引表达式 (cap -1) & hash 很不解，于是就自己手动模拟了几个值算了一下，

当n=3时：
cap = 2^n = 8;
用8位二进制表示cap：
0000 1000
用8位二进制表示cap - 1：
0000 0111
然后随便取几个Hash值（8位二进制表示）：
hash1 = 0010 1000
hash2 = 1101 0011
hash3 = 1111 1111
hash4 = 0000 0001
hash5 = 0000 0010
hash6 = 0100 0101
hash7 = 1001 0100
然后计算(cap - 1) & hash 的值（8位二进制表示）：
hash1: 0000 0111 & 0010 1011 = 0000 0000 = 0
hash2: 0000 0111 & 1101 0011 = 0000 0011 = 3
hash3: 0000 0111 & 1111 1111 = 0000 0111 = 7
hash4: 0000 0111 & 0000 0001 = 0000 0001 = 1
hash5: 0000 0111 & 0000 0010 = 0000 0010 = 2
hash6: 0000 0111 & 0100 0101 = 0000 0101 = 5
hash7: 0000 0111 & 1001 0100 = 0000 0100 = 4

可以看出，当容量为2的n次方时，无论hash值为多少，最后计算得到的索引值有且仅有落在数组上（0到2^n-1的闭区间上）所有点的可能。
当容量不为2的n次方时，无论hash值为多少，最后计算得到的索引值有且仅有落在数组中部分点的可能。
只有当可以分布在数组的所有点上时，才能减小hash碰撞的可能性，这也就是为什么会有容量大小Capacity必需满足为2的n次方的规定 了。

那么，问题又来了，我要是传入一个不满足规定的值，这个规定是怎么强制执行的呢？上代码

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}