很多博文都是错的，ConcurrentHashMap的容量为什么是2的n次幂

很多博文都是错的，ConcurrentHashMap的容量为什么是2的n次幂

归根到底，是为了提高计算的效率，而不是很多博文说的使散列表分布更加均匀。

在jdk1.8中ConcurrentHashMap的数据结构为数组+链表+红黑树

在插入新数据时，要确定插入的索引位置。同样，在数组扩容时，旧数据需要迁移到新数组中，其中，有的数据的位置可能会发生变化。

下面就从插入数据时确定索引位置和迁移数据确定索引位置两个方面来讲。

1.1插入数据

插入数据时，先根据key的hashCode()计算出hash值，再通过一个扰动算法使hash值的高十六位与低十六位都参与进计算，尽可能的使散列表分布均匀(扰动算法这一步才是为了使散列表分散均匀，因为数组长度一般都在16位以下，如果不使用扰动算法，高16位没什么机会参与到运算，有很大几率使索引位置一样),最后hash&（n-1）得到插入的索引位置

//扰动算法计算出最终的hash值
 int hash = spread(key.hashCode());

//f = tabAt(tab, i = (n - 1) & hash)，f为对应索引位置处的值，i为索引位置
  else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }

static final int spread(int h) {
		//这个&运算会使计算出的值最高位为0，使其为正值
        return (h ^ (h >>> 16)) & HASH_BITS;
    }
//0x7fffffff == 0111 1111 1111 1111 1111 1111 1111 1111
static final int HASH_BITS = 0x7fffffff; 

抛开上边这些，如果现在计算出了一个数的hash值，根据值要找到这个数在数组中的位置。

比如说，一个数的hash值为0010 1101，数组长度为16，要找到这个数的索引位置，一般是用取模运算得到的。取模运算会使计算结果永远在0~15之间

0010 1101 == 45,

45 % 16 = 13，这个数应插在索引为13的位置上。

同样的，使用上边的hash & （n-1）

0010 1101
0000 1111
——————
0000 1101 == 13

因此，当数组长度为2的n次幂时，hash&(n-1)等价于hash%n，但是位运算的计算效率比取模要高，这就是数组长度为2的n次幂原因之一。

1.2 迁移数据

当数组扩容时，旧数据需要迁移到新数组中，这些数据的索引位置需要重新计算，因为hash&(n-1)，n变为原来的2倍，位置自然也会发生变化。

比如有三个数的hash值分别为：
0010 1100 0111 1010
1000 0111 0101 1010
0101 0011 1100 1010

当数组长度为16时，索引位置都为10(1010)
0010 1100 0111 1010
0000 0000 0000 1111
——————————
0000 0000 0000 1010

============================

1000 0111 0101 1010
0000 0000 0000 1111
——————————
0000 0000 0000 1010

============================
0101 0011 1100 1010
0000 0000 0000 1111
——————————
0000 0000 0000 1010

当数组长度由16扩容为32时，索引位置就不一样了
0010 1100 0111 1010
0000 0000 0001 1111
——————————
0000 0000 0001 1010

============================

1000 0111 0101 1010
0000 0000 0001 1111
——————————
0000 0000 0001 1010

============================

0101 0011 1100 1010
0000 0000 0001 1111
——————————
0000 0000 0000 1010

观察可知，当数组长度为16时，计算结果为hash值最后4位，当长度为32时，结果为最后5位。但是实际上只需要观察从低位往高位数第五位即可，第5位如果是1，说明新的索引位置为当前位置+旧数组长度。如果为0，索引位置不变。在数组长度是2的n次幂时，大大提高了计算效率。

总结：
ConcurrentHashMap的容量是2的n次幂的原因有两个。
第一个：当容量为2的n次幂时，可以用&运算替代%运算，hash&(n-1)这个方法很快的确定数据的索引位置。
第二个：因为数组扩容时，会扩容为原来的2倍，n-1就会在高位上多一位，只需要判断hash值对应的这一位是0还是1，即可很快的找到新缩印的位置。如果是1，说明新的索引位置为当前位置+旧数组长度。如果为0，索引位置不变。