HashMap的初始化大小為什么是2的冪
首先看下java初始化大小的源碼（代碼來(lái)自jdk1.8）
//構(gòu)造方法
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 這里是初始化的長(zhǎng)度
this.threshold = tableSizeFor(initialCapacity);
}
//初始化長(zhǎng)度的方法
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
我們可以看到在初始化長(zhǎng)度的不管我們傳入的是多少，其實(shí)真實(shí)的長(zhǎng)度并不一定使我們傳入的值。它底層進(jìn)行了一些運(yùn)算。這個(gè)運(yùn)算的結(jié)果是比我們傳入的參數(shù)要大，而且是離我們傳入的參數(shù)最近的2的冪的數(shù)。
運(yùn)算原理案例：（假如我們傳入cap=5）
核心原理：從左到右，使用左邊第一個(gè)`1`填充后面的所有位置
int n = cap -1; n=4 00000100
n|= n>>>1; n做無(wú)符號(hào)右移1位再和n做 `|`運(yùn)算，
n>>>1: 00000100 -> 00000010
|n : 00000100 |
00000010
------------------
結(jié)果：00000110
n|=n>>>2; n做無(wú)符號(hào)右移2位再和n做 `|`運(yùn)算，
n>>>2: 00000110 -> 00000001 10(后面兩位超出邊界舍棄)
|n : 00000110 |
00000001
------------------
結(jié)果：00000111
...
以此類(lèi)推就可以將任何傳入的參數(shù)改變?yōu)楸人蟮亩沂请x它最近的2的冪
為什么初始化的大小必須是2的冪
原因有兩點(diǎn)：1.加快哈希運(yùn)算 2.減少哈希沖突
1.加快哈希運(yùn)算
我們都知道比如向hashMap中存入一個(gè)值,通常做法是對(duì)這個(gè)值求hashCode()得到一個(gè)數(shù)hash,然后在用hash對(duì)集合長(zhǎng)度求余數(shù),也就是 hash%length=positon得到的結(jié)果就是存放的位置。
但是求余%的運(yùn)算效率比較低。有沒(méi)有更快的運(yùn)算呢？答案是使用&運(yùn)算。但是使用&運(yùn)算怎么樣才能和使用%效果一樣呢？那就是，當(dāng)HashMap的長(zhǎng)度為2的冪的時(shí)候一下公式就成立了:hash%length==hash&(length-1)。
所以就可以使用&運(yùn)算來(lái)求位置下標(biāo)了。
2.減少哈希沖突,保證數(shù)據(jù)分散
使用2的冪為長(zhǎng)度，則length-1后為奇數(shù)，該奇數(shù)轉(zhuǎn)為2進(jìn)制后最后一位肯定是1。
假如長(zhǎng)度為4,則長(zhǎng)度-1為3,再轉(zhuǎn)為2進(jìn)制==0000011，該值與任何hash做&運(yùn)算都會(huì)形成==奇數(shù)==或者==偶數(shù)==兩種情況,保證數(shù)據(jù)時(shí)分散的。
可能有人會(huì)想這有什么用？那么我們假如長(zhǎng)度不是4而是3，則3-1為2,再轉(zhuǎn)為2進(jìn)制==0000010，該值與任何hash做&運(yùn)算都會(huì)形成==偶數(shù)==,那也就是說(shuō)我的奇數(shù)的下標(biāo)都不能用了。這樣就不僅浪費(fèi)一般的空間，而且增加了hash沖突的概率.
