每個(gè) 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 篇莹妒。那天名船，小二垂頭喪氣地跑來給我訴苦，“老王旨怠，有個(gè)學(xué)弟小默問我‘ HashMap 的擴(kuò)容機(jī)制’渠驼，我愣是支支吾吾講了半天，沒給他講明白鉴腻，講到最后我內(nèi)心都是崩潰的迷扇，差點(diǎn)哭出聲百揭！”
我安慰了小二好一會(huì)，他激動(dòng)的情緒才穩(wěn)定下來蜓席。我給他說器一，HashMap 的擴(kuò)容機(jī)制本來就很難理解，尤其是 JDK8 新增了紅黑樹之后瓮床。先基于 JDK7 講盹舞，再把紅黑樹那塊加上去就會(huì)容易理解很多。
小二這才恍然大悟隘庄，佩服地點(diǎn)了點(diǎn)頭踢步。
HashMap 發(fā)出的呼聲：有 GitHub 賬號(hào)的小伙伴記得去安排一波 star 呀，《Java 程序員進(jìn)階之路》開源教程目前在 GitHub 上有 285 個(gè) star 了丑掺，準(zhǔn)備沖 1000 了获印，求求各位了。
GitHub 地址：https://github.com/itwanger/toBeBetterJavaer
在線閱讀地址：https://itwanger.gitee.io/tobebetterjavaer
大家都知道街州，數(shù)組一旦初始化后大小就無法改變了兼丰，所以就有了 ArrayList這種“動(dòng)態(tài)數(shù)組”，可以自動(dòng)擴(kuò)容唆缴。
HashMap 的底層用的也是數(shù)組鳍征。向 HashMap 里不停地添加元素，當(dāng)數(shù)組無法裝載更多元素時(shí)面徽，就需要對(duì)數(shù)組進(jìn)行擴(kuò)容艳丛，以便裝入更多的元素。
當(dāng)然了趟紊，數(shù)組是無法自動(dòng)擴(kuò)容的氮双，所以如果要擴(kuò)容的話，就需要新建一個(gè)大的數(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;
}
// 初始化一個(gè)新的數(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)了左移（<<），這里簡(jiǎ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ù)左移后會(huì)變成原來的 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;
// 鏈表上的下一個(gè)元素
e = next;
}
}
}
e.next = newTable[i]情萤，也就是使用了單鏈表的頭插入方式，同一位置上新元素總會(huì)被放在鏈表的頭部位置摹恨；這樣先放在一個(gè)索引上的元素終會(huì)被放到鏈表的尾部（如果發(fā)生了hash沖突的話）筋岛，這一點(diǎn)和 JDK 8 有區(qū)別。
在舊數(shù)組中同一個(gè)鏈表上的元素晒哄，通過重新計(jì)算索引位置后泉蝌，有可能被放到了新數(shù)組的不同位置上（仔細(xì)看下面的內(nèi)容，會(huì)解釋清楚這一點(diǎn)）揩晴。
假設(shè) hash 算法（之前的章節(jié)有講到，點(diǎn)擊鏈接再溫故一下）就是簡(jiǎn)單的用鍵的哈希值（一個(gè) int 值）和數(shù)組大小取模（也就是 hashCode % table.length）贪磺。
繼續(xù)假設(shè)：
- 數(shù)組 table 的長(zhǎng)度為 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 這條鏈表的頭部了喻粹。針對(duì) JDK 7 中的這個(gè)情況，JDK 8 做了哪些優(yōu)化呢较曼？
看下面這張圖磷斧。
n 為 table 的長(zhǎng)度，默認(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拒担。
新的索引就會(huì)發(fā)生這樣的變化：
- 原來的索引是 5（0 0101）
- 原來的容量是 16
- 擴(kuò)容后的容量是 32
- 擴(kuò)容后的索引是 21（1 0101），也就是 5+16攻询，也就是原來的索引+原來的容量
也就是說从撼，JDK 8 不需要像 JDK 7 那樣重新計(jì)算 hash，只需要看原來的hash值新增的那個(gè)bit是1還是0就好了钧栖，是0的話就表示索引沒變低零，是1的話，索引就變成了“原索引+原來的容量”拯杠。
JDK 8 的這個(gè)設(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;
}
參考鏈接：
