HashMap 在 JDK1.8 中的擴容流程（源碼分析）

擴容發生的條件

• 當 HashMap 中鍵值對 key-value 個數大于閥值的時候（注意不是什麼桶或數組的占用情況）
• HashMap 為空或者數組長度為 0
• 更新成紅黑樹時，數組長度小于64，會進行一次擴容代替更新

//在put時會執行putVal()方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    ... ...
	//數組為空，或者數組長度為0會擴容
	if ((tab = table) == null || (n = tab.length) == 0)
	    n = (tab = resize()).length;
	... ...
	//鍵值對的個數大于閥值會擴容   
	if (++size > threshold)
	    resize();
	... ...
}
/**
 * The number of key-value mappings contained in this map.
 */
transient int size;
           

//更新紅黑樹時
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //數組長度小于64，會進行一次擴容代替更新
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if() {
    //連結清單更新紅黑樹
    }
}
           

擴容流程

1. 1.8版本中擴容時如果 Node 桶的資料結構是連結清單會生成 low 和 high 兩條連結清單，是紅黑樹則生成 low 和 high 兩顆紅黑樹
2. 依靠 (hash & oldCap) == 0 判斷 Node 中的每個結點歸屬于 low 還是 high。
3. 把 low 插入到 新數組中 目前數組下标的位置，把 high 連結清單插入到 新數組中 [目前數組下标 + 舊數組長度] 的位置
4. - HashMap 在擴容時為什麼能通過位運算 (e.hash & oldCap) 得到新數組下标

連結清單與紅黑樹的擴容情況

連結清單

 如果是連結清單則生成 low 和 high 兩條連結清單，再插入到新數組的相應下标的位置。low 對應新數組中的下标為 [目前數組下标]，high 對應新數組中的下标為 [目前數組下标 + 舊數組長度]

//把原連結清單中的元素插入到 low 和 high 連結清單中，依靠 (e.hash & oldCap) == 0 判斷
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;
}

//把 low 的頭結點插入到目前數組下标的位置，
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
//把 high 的頭結點插入  新數組中 [目前數組下标 + 舊數組長度] 的位置
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}
           

紅黑樹

 如果是紅黑樹生成的 low，high的插入，如果生成的 low，high 樹中元素個數小于等于6退化成連結清單再插入到新數組的相應下标的位置。low 對應新數組中的下标為 [目前數組下标]，high 對應新數組中的下标為 [目前數組下标 + 舊數組長度]

if (loHead != null) {
	//如果生成的紅黑樹元素個數小于等于6退化
    if (lc <= UNTREEIFY_THRESHOLD)
        tab[index] = loHead.untreeify(map);
    else {
    	//插入的下标為 [目前數組下标 + 舊數組長度]
        tab[index] = loHead;
        if (hiHead != null) // (else is already treeified)
            loHead.treeify(tab);
    }
}
if (hiHead != null) {
	//如果生成的紅黑樹元素個數小于等于6退化
    if (hc <= UNTREEIFY_THRESHOLD)
    	//插入的下标為 [目前數組下标 + 舊數組長度]
        tab[index + bit] = hiHead.untreeify(map);
    else {
        tab[index + bit] = hiHead;
        if (loHead != null)
            hiHead.treeify(tab);
    }
}
           

HashMap知識點總結（附源碼分析連結）