每個 Java 程序員都得了解 HashMap 的擴(kuò)容機(jī)制
美團(tuán)一面：說說 HashMap 的擴(kuò)容機(jī)制吧
看完這篇，如果你還不懂 HashMap 的擴(kuò)容機(jī)制，那我就哭了！
看完這篇還不懂HashMap的擴(kuò)容機(jī)制，那我要哭了~
因?yàn)闆]給學(xué)弟講明白HashMap的擴(kuò)容機(jī)制，小二哭的稀里嘩啦~
HashMap 發(fā)出的 Warning：這是《Java 程序員進(jìn)階之路》專欄的第 56 篇。那天，小二垂頭喪氣地跑來給我訴苦，“老王，有個學(xué)弟小默問我‘ HashMap 的擴(kuò)容機(jī)制’，我愣是支支吾吾講了半天，沒給他講明白，講到最后我內(nèi)心都是崩潰的，差點(diǎn)哭出聲！”
我安慰了小二好一會，他激動的情緒才穩(wěn)定下來。我給他說，HashMap 的擴(kuò)容機(jī)制本來就很難理解，尤其是 JDK8 新增了紅黑樹之后。先基于 JDK7 講，再把紅黑樹那塊加上去就會容易理解很多。
小二這才恍然大悟，佩服地點(diǎn)了點(diǎn)頭。
HashMap 發(fā)出的呼聲：有 GitHub 賬號的小伙伴記得去安排一波 star 呀，《Java 程序員進(jìn)階之路》開源教程目前在 GitHub 上有 285 個 star 了，準(zhǔn)備沖 1000 了，求求各位了。
GitHub 地址：https://github.com/itwanger/toBeBetterJavaer
在線閱讀地址：https://itwanger.gitee.io/tobebetterjavaer
大家都知道，數(shù)組一旦初始化后大小就無法改變了，所以就有了 ArrayList這種“動態(tài)數(shù)組”，可以自動擴(kuò)容。
HashMap 的底層用的也是數(shù)組。向 HashMap 里不停地添加元素，當(dāng)數(shù)組無法裝載更多元素時(shí)，就需要對數(shù)組進(jìn)行擴(kuò)容，以便裝入更多的元素。
當(dāng)然了，數(shù)組是無法自動擴(kuò)容的，所以如果要擴(kuò)容的話，就需要新建一個大的數(shù)組，然后把小數(shù)組的元素復(fù)制過去。
HashMap 的擴(kuò)容是通過 resize 方法來實(shí)現(xiàn)的，JDK 8 中融入了紅黑樹，比較復(fù)雜，為了便于理解，就還使用 JDK 7 的源碼，搞清楚了 JDK 7 的，我們后面再詳細(xì)說明 JDK 8 和 JDK 7 之間的區(qū)別。
resize 方法的源碼：
// newCapacity為新的容量
void resize(int newCapacity) {
// 小數(shù)組，臨時(shí)過度下
Entry[] oldTable = table;
// 擴(kuò)容前的容量
int oldCapacity = oldTable.length;
// MAXIMUM_CAPACITY 為最大容量，2 的 30 次方 = 1<<30
if (oldCapacity == MAXIMUM_CAPACITY) {
// 容量調(diào)整為 Integer 的最大值 0x7fffffff（十六進(jìn)制）=2 的 31 次方-1
threshold = Integer.MAX_VALUE;
return;
}
// 初始化一個新的數(shù)組（大容量）
Entry[] newTable = new Entry[newCapacity];
// 把小數(shù)組的元素轉(zhuǎn)移到大數(shù)組中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 引用新的大數(shù)組
table = newTable;
// 重新計(jì)算閾值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
代碼注釋里出現(xiàn)了左移（<<），這里簡單介紹一下：
a=39
b = a << 2
十進(jìn)制 39 用 8 位的二進(jìn)制來表示，就是 00100111，左移兩位后是 10011100（低位用 0 補(bǔ)上），再轉(zhuǎn)成十進(jìn)制數(shù)就是 156。
移位運(yùn)算通?？梢杂脕泶娉朔ㄟ\(yùn)算和除法運(yùn)算。例如，將 0010011（39）左移兩位就是 10011100（156），剛好變成了原來的 4 倍。
實(shí)際上呢，二進(jìn)制數(shù)左移后會變成原來的 2 倍、4 倍、8 倍。
transfer 方法用來轉(zhuǎn)移，將小數(shù)組的元素拷貝到新的數(shù)組中。
void transfer(Entry[] newTable, boolean rehash) {
// 新的容量
int newCapacity = newTable.length;
// 遍歷小數(shù)組
for (Entry<K,V> e : table) {
while(null != e) {
// 拉鏈法，相同 key 上的不同值
Entry<K,V> next = e.next;
// 是否需要重新計(jì)算 hash
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 根據(jù)大數(shù)組的容量，和鍵的 hash 計(jì)算元素在數(shù)組中的下標(biāo)
int i = indexFor(e.hash, newCapacity);
// 同一位置上的新元素被放在鏈表的頭部
e.next = newTable[i];
// 放在新的數(shù)組上
newTable[i] = e;
// 鏈表上的下一個元素
e = next;
}
}
}
e.next = newTable[i]，也就是使用了單鏈表的頭插入方式，同一位置上新元素總會被放在鏈表的頭部位置；這樣先放在一個索引上的元素終會被放到鏈表的尾部（如果發(fā)生了hash沖突的話），這一點(diǎn)和 JDK 8 有區(qū)別。
在舊數(shù)組中同一個鏈表上的元素，通過重新計(jì)算索引位置后，有可能被放到了新數(shù)組的不同位置上（仔細(xì)看下面的內(nèi)容，會解釋清楚這一點(diǎn)）。
假設(shè) hash 算法（之前的章節(jié)有講到，點(diǎn)擊鏈接再溫故一下）就是簡單的用鍵的哈希值（一個 int 值）和數(shù)組大小取模（也就是 hashCode % table.length）。
繼續(xù)假設(shè)：
- 數(shù)組 table 的長度為 2
- 鍵的哈希值為 3、7、5
取模運(yùn)算后，哈希沖突都到 table[1] 上了，因?yàn)橛鄶?shù)為 1。那么擴(kuò)容前的樣子如下圖所示。
小數(shù)組的容量為 2， key 3、7、5 都在 table[1] 的鏈表上。
假設(shè)負(fù)載因子 loadFactor 為 1，也就是當(dāng)元素的實(shí)際大小大于 table 的實(shí)際大小時(shí)進(jìn)行擴(kuò)容。
擴(kuò)容后的大數(shù)組的容量為 4。
- key 3 取模（3%4）后是 3，放在 table[3] 上。
- key 7 取模（7%4）后是 3，放在 table[3] 上的鏈表頭部。
- key 5 取模（5%4）后是 1，放在 table[1] 上。
按照我們的預(yù)期，擴(kuò)容后的 7 仍然應(yīng)該在 3 這條鏈表的后面，但實(shí)際上呢？ 7 跑到 3 這條鏈表的頭部了。針對 JDK 7 中的這個情況，JDK 8 做了哪些優(yōu)化呢？
看下面這張圖。
n 為 table 的長度，默認(rèn)值為 16。
- n-1 也就是二進(jìn)制的 0000 1111（1X
+1X
+1X
+1X
=1+2+4+8=15）；
- key1 哈希值的最后 8 位為 0000 0101
- key2 哈希值的最后 8 位為 0001 0101（和 key1 不同）
- 做與運(yùn)算后發(fā)生了哈希沖突，索引都在（0000 0101）上。
擴(kuò)容后為 32。
- n-1 也就是二進(jìn)制的 0001 1111（1X
=1+2+4+8+16=31），擴(kuò)容前是 0000 1111。
- key1 哈希值的低位為 0000 0101
- key2 哈希值的低位為 0001 0101（和 key1 不同）
- key1 做與運(yùn)算后，索引為 0000 0101。
- key2 做與運(yùn)算后，索引為 0001 0101。
新的索引就會發(fā)生這樣的變化：
- 原來的索引是 5（0 0101）
- 原來的容量是 16
- 擴(kuò)容后的容量是 32
- 擴(kuò)容后的索引是 21（1 0101），也就是 5+16，也就是原來的索引+原來的容量
也就是說，JDK 8 不需要像 JDK 7 那樣重新計(jì)算 hash，只需要看原來的hash值新增的那個bit是1還是0就好了，是0的話就表示索引沒變，是1的話，索引就變成了“原索引+原來的容量”。
JDK 8 的這個設(shè)計(jì)非常巧妙，既省去了重新計(jì)算hash的時(shí)間，同時(shí)，由于新增的1 bit是0還是1是隨機(jī)的，因此擴(kuò)容的過程，可以均勻地把之前的節(jié)點(diǎn)分散到新的位置上。
woc，只能說 HashMap 的作者 Doug Lea、Josh Bloch、Arthur van Hoff、Neal Gafter 真的強(qiáng)——的一筆。
JDK 8 擴(kuò)容的源代碼：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超過最大值就不再擴(kuò)充了，就只好隨你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 沒超過最大值，就擴(kuò)充為原來的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計(jì)算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 小數(shù)組復(fù)制到大數(shù)組
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 鏈表優(yōu)化重 hash 的代碼塊
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原來的索引
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 索引+原來的容量
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
參考鏈接：
