HashMap中紅黑樹退化成連結清單的條件（源碼分析）

條件

1. 擴容 resize( ) 時，紅黑樹拆分成的 樹的結點數小于等于臨界值6個，則退化成連結清單。
2. 移除元素 remove( ) 時，在removeTreeNode( ) 方法會檢查紅黑樹是否滿足退化條件，與結點數無關。如果紅黑樹根 root 為空，或者 root 的左子樹/右子樹為空，root.left.left 根的左子樹的左子樹為空，都會發生紅黑樹退化成連結清單。

擴容 resize( ) 的源碼分析

1. 擴容時如果是紅黑樹結構會執行紅黑樹的 split( ) 方法
2. split 方法中會初始化生成 loHead 和 hiHead 兩個紅黑樹的頭結點（之後會用 low 和 high 表示）
3. lc 和 hc 分别為 low 和 high 的元素個數，初始化為0
4. 把紅黑樹中的結點依次添加到 low 和 high 兩顆紅黑樹中，依靠 (e.hash & bit) == 0 的位運算來判斷屬于哪顆樹，bit是傳過來的舊數組下标。每顆樹元素的增加都會使對應的 lc 或 hc 自增1。
5. 生成完 low 和 high 兩顆紅黑樹後，如果對應的元素個數 lc，hc 小于等于6，退化成連結清單，否則維持紅黑樹形态。
6. low樹插入到新數組 tab[index] 的位置上，index是目前紅黑樹所在舊數組坐标；high樹插入到新數組 tab[index + bit] 的位置上，bit是舊數組長度。

//退化連結清單的臨界值
static final int UNTREEIFY_THRESHOLD = 6;

//1、擴容時如果是紅黑樹結構會執行split方法
else if (e instanceof TreeNode)
	((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
	
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
	//生成 low 和 high 兩個紅黑樹
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    //lc是low樹的元素個數，hc是high數的。
    int lc = 0, hc = 0;
    
    //把紅黑樹中的結點依次添加到 low 和 high 兩顆紅黑樹中
    //還是依靠 (e.hash & bit) == 0 的位運算來判斷屬于哪顆樹，bit是傳過來的舊數組下标
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
    	......
        if ((e.hash & bit) == 0) {
        	//添加到 loHead
        	......
            ++lc;
        }
        else {
        	//添加到 hiHead
        	......
            ++hc;
        }
    }
	
	if (loHead != null) {
		//如果low樹的元素個數小于等于6，退化成連結清單
		//并插入到新數組 tab[index] 的位置上，index是目前紅黑樹所在舊數組坐标
    	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) {
		//如果high樹的元素個數小于等于6，退化成連結清單
		//并插入到新數組 tab[index + bit] 的位置上，index是目前紅黑樹所在舊數組坐标，bit是舊數組長度
    	if (hc <= UNTREEIFY_THRESHOLD)
        	tab[index + bit] = hiHead.untreeify(map);
    	else {
        	tab[index + bit] = hiHead;
        	if (loHead != null)
            	hiHead.treeify(tab);
    	}
	}
}
           

移除元素 remove( ) 時的源碼

• 在 remove( ) 時如果是紅黑樹則執行 removeTreeNode( ) 方法 。
• 在 removeTreeNode( )的方法中，滿足一定條件後會退化成連結清單，如果紅黑樹根 root 為空，或者 root 的左子樹/右子樹為空，root.left.left 根的左子樹的左子樹為空，都會發生紅黑樹退化成連結清單。

//remove時
//在removeTreeNode()的方法中，滿足一定條件後會退化成連結清單
//條件中的movable是remove()方法傳進來的true，ctrl+f沒有發現哪裡有做更改
//如果紅黑樹根root為空，或者root的左子樹/右子樹為空，root.left.left根的左子樹的左子樹為空
//這幾種情況都會發生紅黑樹退化成連結清單
if (root == null
    || (movable
        && (root.right == null
            || (rl = root.left) == null
            || rl.left == null))) {
    tab[index] = first.untreeify(map);  // too small
    return;
}
           

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