摘要：前言系列文章目錄上一篇我們說(shuō)明了的構(gòu)造函數(shù)談到構(gòu)造函數(shù)中并不會(huì)初始化變量變量是在過(guò)程中初始化的本篇我們就來(lái)聊聊的擴(kuò)容本文的源碼基于版本用于以下兩種情況之一初始化在大小超過(guò)之后進(jìn)行擴(kuò)容下面我們直接來(lái)對(duì)照源碼分析原中已經(jīng)有值已經(jīng)超過(guò)最大限制不再
前言
系列文章目錄
上一篇我們說(shuō)明了HashMap的構(gòu)造函數(shù), 談到構(gòu)造函數(shù)中并不會(huì)初始化table 變量, table 變量是在 resize過(guò)程中初始化的.
本篇我們就來(lái)聊聊HashMap的擴(kuò)容: resize
本文的源碼基于 jdk8 版本.
resize
resize用于以下兩種情況之一
初始化table
在table大小超過(guò)threshold之后進(jìn)行擴(kuò)容
下面我們直接來(lái)對(duì)照源碼分析:
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 原table中已經(jīng)有值
if (oldCap > 0) {
// 已經(jīng)超過(guò)最大限制, 不再擴(kuò)容, 直接返回
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 注意, 這里擴(kuò)容是變成原來(lái)的兩倍
// 但是有一個(gè)條件: `oldCap >= DEFAULT_INITIAL_CAPACITY`
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 在構(gòu)造函數(shù)一節(jié)中我們知道
// 如果沒(méi)有指定initialCapacity, 則不會(huì)給threshold賦值, 該值被初始化為0
// 如果指定了initialCapacity, 該值被初始化成大于initialCapacity的最小的2的次冪
// 這里是指, 如果構(gòu)造時(shí)指定了initialCapacity, 則用threshold作為table的實(shí)際大小
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 如果構(gòu)造時(shí)沒(méi)有指定initialCapacity, 則用默認(rèn)值
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計(jì)算指定了initialCapacity情況下的新的 threshold
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//從以上操作我們知道, 初始化HashMap時(shí),
//如果構(gòu)造函數(shù)沒(méi)有指定initialCapacity, 則table大小為16
//如果構(gòu)造函數(shù)指定了initialCapacity, 則table大小為threshold, 即大于指定initialCapacity的最小的2的整數(shù)次冪
// 從下面開(kāi)始, 初始化table或者擴(kuò)容, 實(shí)際上都是通過(guò)新建一個(gè)table來(lái)完成的
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
// 下面這段就是把原來(lái)table里面的值全部搬到新的table里面
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
// 這里注意, table中存放的只是Node的引用, 這里將oldTab[j]=null只是清除舊表的引用, 但是真正的node節(jié)點(diǎn)還在, 只是現(xiàn)在由e指向它
oldTab[j] = null;
// 如果該存儲(chǔ)桶里面只有一個(gè)bin, 就直接將它放到新表的目標(biāo)位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果該存儲(chǔ)桶里面存的是紅黑樹(shù), 則拆分樹(shù)
else if (e instanceof TreeNode)
//紅黑樹(shù)的部分以后有機(jī)會(huì)再講吧
((TreeNode)e).split(this, newTab, j, oldCap);
// 下面這段代碼很精妙, 我們多帶帶分一段詳細(xì)來(lái)講
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node 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;
}
resize時(shí)的鏈表拆分
下面我們多帶帶來(lái)看看這段設(shè)計(jì)的很精妙的代碼
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node 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;
}
首先我們看源碼時(shí)要抓住一個(gè)大框架, 不要被它復(fù)雜的流程唬住, 我們一段一段來(lái)看:
第一段
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
上面這段定義了四個(gè)Node的引用, 從變量命名上,我們初步猜測(cè), 這里定義了兩個(gè)鏈表, 我們把它稱為 lo鏈表 和 hi鏈表, loHead 和 loTail 分別指向 lo鏈表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn), hiHead 和 hiTail以此類(lèi)推.
第二段
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);
上面這段是一個(gè)do-while循環(huán), 我們先從中提取出主要框架:
do {
next = e.next;
...
} while ((e = next) != null);
從上面的框架上來(lái)看, 就是在按順序遍歷該存儲(chǔ)桶位置上的鏈表中的節(jié)點(diǎn).
我們?cè)倏?b>if-else 語(yǔ)句的內(nèi)容:
// 插入lo鏈表
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
// 插入hi鏈表
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
上面結(jié)構(gòu)類(lèi)似的兩段看上去就是一個(gè)將節(jié)點(diǎn)e插入鏈表的動(dòng)作.
最后再加上 if 塊, 則上面這段的目的就很清晰了:
我們首先準(zhǔn)備了兩個(gè)鏈表 lo 和 hi, 然后我們順序遍歷該存儲(chǔ)桶上的鏈表的每個(gè)節(jié)點(diǎn), 如果 (e.hash & oldCap) == 0, 我們就將節(jié)點(diǎn)放入lo鏈表, 否則, 放入hi鏈表.
第三段
第二段弄明白之后, 我們?cè)賮?lái)看第三段:
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
這一段看上去就很簡(jiǎn)單了:
如果lo鏈表非空, 我們就把整個(gè)lo鏈表放到新table的j位置上
如果hi鏈表非空, 我們就把整個(gè)hi鏈表放到新table的j+oldCap位置上
綜上我們知道, 這段代碼的意義就是將原來(lái)的鏈表拆分成兩個(gè)鏈表, 并將這兩個(gè)鏈表分別放到新的table的 j 位置和 j+oldCap 上, j位置就是原鏈表在原table中的位置, 拆分的標(biāo)準(zhǔn)就是:
(e.hash & oldCap) == 0
為了幫助大家理解，我畫(huà)了個(gè)示意圖：
（ps: 畫(huà)個(gè)圖真的好累啊， 大家有什么好的畫(huà)圖工具推薦嗎？）
關(guān)于 (e.hash & oldCap) == 0 j 以及 j+oldCap
上面我們已經(jīng)弄懂了鏈表拆分的代碼, 但是這個(gè)拆分條件看上去很奇怪, 這里我們來(lái)稍微解釋一下:
首先我們要明確三點(diǎn):
oldCap一定是2的整數(shù)次冪, 這里假設(shè)是2^m
newCap是oldCap的兩倍, 則會(huì)是2^(m+1)
hash對(duì)數(shù)組大小取模(n - 1) & hash 其實(shí)就是取hash的低m位
例如:
我們假設(shè) oldCap = 16, 即 2^4,
16 - 1 = 15, 二進(jìn)制表示為 0000 0000 0000 0000 0000 0000 0000 1111
可見(jiàn)除了低4位, 其他位置都是0（簡(jiǎn)潔起見(jiàn)，高位的0后面就不寫(xiě)了）, 則 (16-1) & hash 自然就是取hash值的低4位,我們假設(shè)它為 abcd.
以此類(lèi)推, 當(dāng)我們將oldCap擴(kuò)大兩倍后, 新的index的位置就變成了 (32-1) & hash, 其實(shí)就是取 hash值的低5位. 那么對(duì)于同一個(gè)Node, 低5位的值無(wú)外乎下面兩種情況:
0abcd
1abcd
其中, 0abcd與原來(lái)的index值一致, 而1abcd = 0abcd + 10000 = 0abcd + oldCap
故雖然數(shù)組大小擴(kuò)大了一倍，但是同一個(gè)key在新舊table中對(duì)應(yīng)的index卻存在一定聯(lián)系： 要么一致，要么相差一個(gè) oldCap。
而新舊index是否一致就體現(xiàn)在hash值的第4位(我們把最低為稱作第0位), 怎么拿到這一位的值呢, 只要:
hash & 0000 0000 0000 0000 0000 0000 0001 0000
上式就等效于
hash & oldCap
故得出結(jié)論:
如果 (e.hash & oldCap) == 0 則該節(jié)點(diǎn)在新表的下標(biāo)位置與舊表一致都為 j
如果 (e.hash & oldCap) == 1 則該節(jié)點(diǎn)在新表的下標(biāo)位置 j + oldCap
根據(jù)這個(gè)條件, 我們將原位置的鏈表拆分成兩個(gè)鏈表, 然后一次性將整個(gè)鏈表放到新的Table對(duì)應(yīng)的位置上.
怎么樣? 這個(gè)設(shè)計(jì)是不是很巧妙, 反正LZ是無(wú)比佩服源碼作者的!
總結(jié)
resize發(fā)生在table初始化, 或者table中的節(jié)點(diǎn)數(shù)超過(guò)threshold值的時(shí)候, threshold的值一般為負(fù)載因子乘以容量大小.
每次擴(kuò)容都會(huì)新建一個(gè)table, 新建的table的大小為原大小的2倍.
擴(kuò)容時(shí),會(huì)將原table中的節(jié)點(diǎn)re-hash到新的table中, 但節(jié)點(diǎn)在新舊table中的位置存在一定聯(lián)系: 要么下標(biāo)相同, 要么相差一個(gè)oldCap(原table的大小).
（完）
下一篇: 深入理解HashMap(五): 關(guān)鍵源碼逐行分析之put
查看更多系列文章：系列文章目錄
