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知识点总结（附源码分析链接）