HashMap的初始化大小為什么是2的冪
首先看下java初始化大小的源碼（代碼來自jdk1.8）
//構造方法
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;
// 這里是初始化的長度
this.threshold = tableSizeFor(initialCapacity);
}
//初始化長度的方法
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;
}
我們可以看到在初始化長度的不管我們傳入的是多少秧秉，其實真實的長度并不一定使我們傳入的值。它底層進行了一些運算。這個運算的結果是比我們傳入的參數(shù)要大削茁，而且是離我們傳入的參數(shù)最近的2的冪的數(shù)瓢宦。
運算原理案例：（假如我們傳入cap=5）
核心原理：從左到右斥季，使用左邊第一個`1`填充后面的所有位置
int n = cap -1; n=4 00000100
n|= n>>>1; n做無符號右移1位再和n做 `|`運算锦溪，
n>>>1: 00000100 -> 00000010
|n : 00000100 |
00000010
------------------
結果：00000110
n|=n>>>2; n做無符號右移2位再和n做 `|`運算，
n>>>2: 00000110 -> 00000001 10(后面兩位超出邊界舍棄)
|n : 00000110 |
00000001
------------------
結果：00000111
...
以此類推就可以將任何傳入的參數(shù)改變?yōu)楸人蟮亩沂请x它最近的2的冪
為什么初始化的大小必須是2的冪
原因有兩點：1.加快哈希運算 2.減少哈希沖突
1.加快哈希運算
我們都知道比如向hashMap中存入一個值,通常做法是對這個值求hashCode()得到一個數(shù)hash,然后在用hash對集合長度求余數(shù),也就是 hash%length=positon得到的結果就是存放的位置综苔。
但是求余%的運算效率比較低惩系。有沒有更快的運算呢？答案是使用&運算如筛。但是使用&運算怎么樣才能和使用%效果一樣呢堡牡？那就是，當HashMap的長度為2的冪的時候一下公式就成立了:hash%length==hash&(length-1)杨刨。
所以就可以使用&運算來求位置下標了晤柄。
2.減少哈希沖突,保證數(shù)據(jù)分散
使用2的冪為長度，則length-1后為奇數(shù)妖胀，該奇數(shù)轉為2進制后最后一位肯定是1芥颈。
假如長度為4,則長度-1為3,再轉為2進制==0000011，該值與任何hash做&運算都會形成==奇數(shù)==或者==偶數(shù)==兩種情況,保證數(shù)據(jù)時分散的赚抡。
可能有人會想這有什么用爬坑？那么我們假如長度不是4而是3，則3-1為2,再轉為2進制==0000010怕品，該值與任何hash做&運算都會形成==偶數(shù)==,那也就是說我的奇數(shù)的下標都不能用了妇垢。這樣就不僅浪費一般的空間，而且增加了hash沖突的概率.
