为什么HashMap的数组长度一定是2的次幂？

首先，HashMap的初始化的数组长度一定是2的n次的，每次扩容仍是原来的2倍的话，就不会破坏这个规律，每次扩容后，原数据都会进行数据迁移，根据二进制的计算，扩容后数据要么在原来位置，要么在【原来位置+扩容长度】，这样就不需要重新hash，效率上更高。

HashMap中，如果想存入数据，首先它需要根据key的哈希值去定位落入哪个桶中。

HashMap的做法，我总结的是，三步：>>>无符号右移、^异或、&与

具体是：拿着key的哈希值，先“>>>”无符号右移16位，然后“^”异或上key的哈希值，得到一个值，再拿着这个值去“&”上数组长度减一

最后得出一个数(如果数组长度是15的话，那这个数就是一个0-15之间的一个数)，这个数就是得出的数组脚标位置，也就是存入的桶的位置。

由上边可以知道，定位桶的位置最后需要做一个 “&” 与运算，&完了得出一个数，就是桶的位置

知道了这些以后，再来说为什么HashMap的长度之所以一定是2的次幂?

至少有以下两个原因：

1、HashMap的长度是2的次幂的话，可以让数据更散列更均匀的分布，更充分的利用数组的空间

怎么理解呢?下面举例子说一下如果不是2的次幂的数的话假设数组长度是一个奇数，那参与最后的&运算的肯定就是偶数，那偶数的话，它二进制的最后一个低位肯定是0，0做完&运算得到的肯定也是0，那意味着&完后得到的数的最低位一定是0最低位一定是0的话，那说明一定是一个偶数，换句话说就是：&完得到的数一定是一个偶数，所以&完获取到的脚标永远是偶数位，那意味着奇数位的脚标永远都没值，有一半的空间是浪费的奇数说完了，来说一下偶数，假设数组长度是一个偶数，比如6，那参与&运算的就是55的二进制 00000000 00000000 00000000 00000101发现任何一个数&上5，倒数第二低位永远是0，那就意味着&完以后，最起码肯定得不出2或者3(这点刚开始不好理解，但是好好想一下就能明白)意味着第二和第三脚标位肯定不会有值

虽然偶数的话，不会像奇数那么夸张会有一半的脚标位得不到，但是也总会有一些脚标位得不到的。所以不是2的次幂的话，不管是奇数还是偶数，就肯定注定了某些脚标位永远是没有值的，而某些脚标位永远是没有值的，就意味着浪费空间，会让数据散列的不充分，这对HashMap来说绝对是个灾难!

2、HashMap的长度一定是2的次幂，还有另外一个原因，那就是在扩容迁移的时候不需要再重新通过哈希定位新的位置了。扩容后，元素新的位置，要么在原脚标位，要么在原脚标位+扩容长度这么一个位置。

比如扩容前长度是8，扩容后长度是16
 
第一种情况：
扩容前：
 00000000 00000000 00000000 00000101
&00000000 00000000 00000000 00000111     8-1=7
-------------------------------------
                                 101   ===== 5 原来脚标位是5
 
扩容后：                       
 00000000 00000000 00000000 00000101
&00000000 00000000 00000000 00001111    16-1=15
-------------------------------------
                                 101   ===== 5 扩容后脚标位是5（原脚标位）
 
 
第二种情况：
扩容前：
 00000000 00000000 00000000 00001101
&00000000 00000000 00000000 00000111     8-1=7
-------------------------------------
                                 101   ===== 5 原来脚标位是5
                            
扩容后：                            
 00000000 00000000 00000000 00001101
&00000000 00000000 00000000 00001111    16-1=15
-------------------------------------
                                1101   ===== 13 扩容后脚标位是13（原脚标位+扩容长度）

扩容后到底是在原来位置还是在原脚标位+扩容长度的位置，主要是看新扩容最左边一个1对应的上方数字是0还是1如果是0则扩容后在原来位置，如果是1则扩容后在原脚标位+扩容长度的位置HashMap源码里扩容也是这么做的。

总结来说，就是hash&(n-1)这个计算有关。如果不为n不为2的n次方的话，那转换为二进制情况下，n-1就会有某一位为0，那与hash做了&运算后，该位置永远为0，那么计算出来的数组位置就永远会有某个下标的数组位置是空的，也就是这个位置永远不会有值。