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

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

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

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

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

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

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

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

至少有以下兩個(gè)原因：

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

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

雖然偶數(shù)的話，不會(huì)像奇數(shù)那么夸張會(huì)有一半的腳標(biāo)位得不到，但是也總會(huì)有一些腳標(biāo)位得不到的。所以不是2的次冪的話，不管是奇數(shù)還是偶數(shù)，就肯定注定了某些腳標(biāo)位永遠(yuǎn)是沒有值的，而某些腳標(biāo)位永遠(yuǎn)是沒有值的，就意味著浪費(fèi)空間，會(huì)讓數(shù)據(jù)散列的不充分，這對(duì)HashMap來說絕對(duì)是個(gè)災(zāi)難!

2、HashMap的長(zhǎng)度一定是2的次冪，還有另外一個(gè)原因，那就是在擴(kuò)容遷移的時(shí)候不需要再重新通過哈希定位新的位置了。擴(kuò)容后，元素新的位置，要么在原腳標(biāo)位，要么在原腳標(biāo)位+擴(kuò)容長(zhǎng)度這么一個(gè)位置。

比如擴(kuò)容前長(zhǎng)度是8，擴(kuò)容后長(zhǎng)度是16
 
第一種情況：
擴(kuò)容前：
 00000000 00000000 00000000 00000101
&00000000 00000000 00000000 00000111     8-1=7
-------------------------------------
                                 101   ===== 5 原來腳標(biāo)位是5
 
擴(kuò)容后：                       
 00000000 00000000 00000000 00000101
&00000000 00000000 00000000 00001111    16-1=15
-------------------------------------
                                 101   ===== 5 擴(kuò)容后腳標(biāo)位是5（原腳標(biāo)位）
 
 
第二種情況：
擴(kuò)容前：
 00000000 00000000 00000000 00001101
&00000000 00000000 00000000 00000111     8-1=7
-------------------------------------
                                 101   ===== 5 原來腳標(biāo)位是5
                            
擴(kuò)容后：                            
 00000000 00000000 00000000 00001101
&00000000 00000000 00000000 00001111    16-1=15
-------------------------------------
                                1101   ===== 13 擴(kuò)容后腳標(biāo)位是13（原腳標(biāo)位+擴(kuò)容長(zhǎng)度）

擴(kuò)容后到底是在原來位置還是在原腳標(biāo)位+擴(kuò)容長(zhǎng)度的位置，主要是看新擴(kuò)容最左邊一個(gè)1對(duì)應(yīng)的上方數(shù)字是0還是1如果是0則擴(kuò)容后在原來位置，如果是1則擴(kuò)容后在原腳標(biāo)位+擴(kuò)容長(zhǎng)度的位置HashMap源碼里擴(kuò)容也是這么做的。

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