HashMap的初始容量为什么最好设为2的次幂

首先我们来看看如果初始容量不是2的次幂会出现什么问题。为了更好的演示接下来出现的问题，我们取比较特殊一点的数字。假设我要存12个元素，为了防止HashMap扩容，初始容量应设为(12/0.75) + 1 = 17。
下面我们来看下HashMap计算数组索引的源码，如下图：

上图中有三个变量：tab（数组）、n（数组的长度）、i（数组的索引）。从源码中可知i=(n - 1) & hash，即将数组长度-1与hash作与运算。上面已经定义了HashMap的数组的初始容量为17，所以，i=(17 - 1) & hash=16 & hash。接下来我们看一段代码，如下图：

问题出现了，计算出来的索引要么是0，要么是16，这就会导致元素不能均匀的散列在数组上，会创建过多链表来存储元素，降低性能。可能有的人会说，HashMap对hash算法作了优化，那我们来看下优化的版本，见下图：

结果没有任何变化。根本问题不在于hash算法，而是与运算。16的二进制是10000，根据与运算的特点可知，任何数&10000得到到只能是10000或00000。进而我们可以推导出，只要有0出现就有可能导致索引冲突。比如，101&000=000、101&010=000。
到此我们已经知道了问题的所在，接下来我们再看下2的次幂能不能解决上面的问题。
我们还以上面的例子为例，这个时候的初始容量就不能取17 ，而是要向上取最近的一个2的次幂的数，也就是32。为了后面好书写，这里改一下，取16。
16的二进制是10000，那么(16-1)的二进制就是01111，所以：
1. (16-1)&hash，计算的索引会落在[0,15]，不会越界。
2. 与运算的结果取决于hash值，这样只要保证hash是均匀散列的，也就是保证1均匀分布就能防止索引冲突。

注：(n-1)&hash，取n-1是为了防止索引越界
1. n>hash
((n-1)&hash) <= hash < n
2. n<=hash
((n-1)&hash) <= (n-1) <n