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