了解過HashMap都應(yīng)該知道，HashMap內(nèi)部會(huì)創(chuàng)建一個(gè)Entry<K, V> table數(shù)組來(lái)存放元素艇拍，而且這個(gè)數(shù)組的長(zhǎng)度永遠(yuǎn)都是2的指數(shù)次方握础。那么問題來(lái)了，為什么選擇2的指數(shù)次方呢甚亭？
首先，思考一下計(jì)算出hash值后击胜，應(yīng)該存放在數(shù)組的哪個(gè)位置亏狰？顯然用求余(模)最簡(jiǎn)單。然而模的效率并不高偶摔，看看JDK是怎么做的暇唾，indexFor方法：
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
其中h就是hash值，length是table的長(zhǎng)度。對(duì)2的指數(shù)次方求模運(yùn)算(h % length)和h & (length-1)結(jié)果是一樣的策州，這點(diǎn)從代碼注釋也可以知道瘸味，不明白可以看最后的備注。
接著看看為什么容量是2的指數(shù)次方的問題够挂，假如容量分別是16和15兩種情況旁仿，對(duì)應(yīng)的length-1的二進(jìn)制分別是1111和1110，然后我們思考hash值分別是8和9這兩種情況孽糖，8 & 1111 = 8枯冈，9 & 1111 = 9，存放在table[8]和table[9]對(duì)應(yīng)的位置办悟，沒有發(fā)生碰撞尘奏；然后8 & 1110 = 8，9 & 1110 = 8誉尖，兩個(gè)hash值都被存放在了table的同一位置罪既，顯然發(fā)生了碰撞铸题。放大來(lái)看铡恕，如果容量是15的話，length - 1對(duì)應(yīng)的二進(jìn)制是1110丢间，進(jìn)行與運(yùn)算后探熔，最后一位永遠(yuǎn)是0，即xxx0烘挫，這將會(huì)導(dǎo)致table中0001诀艰，0011，0101饮六，1001其垄，1011，0111卤橄，1101這幾個(gè)位置永遠(yuǎn)都不能存放元素了绿满，空間浪費(fèi)不說(shuō)，碰撞概率也增大窟扑。而我們2的指數(shù)次方對(duì)應(yīng)的數(shù)length-1后二進(jìn)制全是1喇颁，進(jìn)行與運(yùn)算顯然不會(huì)干擾到原h(huán)ash值，不會(huì)導(dǎo)致table中哪個(gè)位置不能存放元素嚎货。
解釋一下“對(duì)2的指數(shù)次方求模運(yùn)算(
h % length)和h & (length-1)結(jié)果是一樣的”橘霎，以4(二進(jìn)制為11)為例：
0 % 4 = 0 同 4 % 4 = 0 ……
1 % 4 = 1 同 5 % 4 = 1 ……
2 % 4 = 2 同 6 % 4 = 2 ……
3 % 4 = 3 同 7 % 4 = 3 ……
00 & 11 = 0 同 100 && 11 = 0 ……
01 & 11 = 1 同 101 && 11 = 1 ……
10 & 11 = 2 同 110 && 11 = 2 ……
11 & 11 = 3 同 111 && 11 = 3 ……
明顯，求余運(yùn)算每4個(gè)一循環(huán)殖属，對(duì)應(yīng)二進(jìn)制大于4之后姐叁，高位的數(shù)字與0進(jìn)行與運(yùn)算，始終為0，效果等同于每4個(gè)一循環(huán)外潜。
總結(jié)一下：使用2的指數(shù)次方作為HashMap中存放元素?cái)?shù)組的大小谭溉，可以避免求余操作，效率較高橡卤，同時(shí)扮念，減少了碰撞次數(shù)。
