為什么HashMap的數(shù)組長度一定是2的次冪？

首先，HashMap的初始化的數(shù)組長度一定是2的n次的，每次擴容仍是原來的2倍的話，就不會破壞這個規(guī)律，每次擴容后，原數(shù)據(jù)都會進行數(shù)據(jù)遷移，根據(jù)二進制的計算，擴容后數(shù)據(jù)要么在原來位置，要么在【原來位置+擴容長度】，這樣就不需要重新hash，效率上更高。

HashMap中，如果想存入數(shù)據(jù)，首先它需要根據(jù)key的哈希值去定位落入哪個桶中。

HashMap的做法，我總結(jié)的是，三步：>>>無符號右移、^異或、&與

具體是：拿著key的哈希值，先“>>>”無符號右移16位，然后“^”異或上key的哈希值，得到一個值，再拿著這個值去“&”上數(shù)組長度減一

最后得出一個數(shù)(如果數(shù)組長度是15的話，那這個數(shù)就是一個0-15之間的一個數(shù))，這個數(shù)就是得出的數(shù)組腳標位置，也就是存入的桶的位置。

由上邊可以知道，定位桶的位置最后需要做一個 “&” 與運算，&完了得出一個數(shù)，就是桶的位置

知道了這些以后，再來說為什么HashMap的長度之所以一定是2的次冪?

至少有以下兩個原因：

1、HashMap的長度是2的次冪的話，可以讓數(shù)據(jù)更散列更均勻的分布，更充分的利用數(shù)組的空間

怎么理解呢?下面舉例子說一下如果不是2的次冪的數(shù)的話假設(shè)數(shù)組長度是一個奇數(shù)，那參與最后的&運算的肯定就是偶數(shù)，那偶數(shù)的話，它二進制的最后一個低位肯定是0，0做完&運算得到的肯定也是0，那意味著&完后得到的數(shù)的最低位一定是0最低位一定是0的話，那說明一定是一個偶數(shù)，換句話說就是：&完得到的數(shù)一定是一個偶數(shù)，所以&完獲取到的腳標永遠是偶數(shù)位，那意味著奇數(shù)位的腳標永遠都沒值，有一半的空間是浪費的奇數(shù)說完了，來說一下偶數(shù)，假設(shè)數(shù)組長度是一個偶數(shù)，比如6，那參與&運算的就是55的二進制 00000000 00000000 00000000 00000101發(fā)現(xiàn)任何一個數(shù)&上5，倒數(shù)第二低位永遠是0，那就意味著&完以后，最起碼肯定得不出2或者3(這點剛開始不好理解，但是好好想一下就能明白)意味著第二和第三腳標位肯定不會有值

雖然偶數(shù)的話，不會像奇數(shù)那么夸張會有一半的腳標位得不到，但是也總會有一些腳標位得不到的。所以不是2的次冪的話，不管是奇數(shù)還是偶數(shù)，就肯定注定了某些腳標位永遠是沒有值的，而某些腳標位永遠是沒有值的，就意味著浪費空間，會讓數(shù)據(jù)散列的不充分，這對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對應的上方數(shù)字是0還是1如果是0則擴容后在原來位置，如果是1則擴容后在原腳標位+擴容長度的位置HashMap源碼里擴容也是這么做的。

總結(jié)來說，就是hash&(n-1)這個計算有關(guān)。如果不為n不為2的n次方的話，那轉(zhuǎn)換為二進制情況下，n-1就會有某一位為0，那與hash做了&運算后，該位置永遠為0，那么計算出來的數(shù)組位置就永遠會有某個下標的數(shù)組位置是空的，也就是這個位置永遠不會有值。