Hash链表转换为红黑树，和树转换为链表的条件

• 2022 年 3 月 24 日
• 筆記
• JAVA

链表转换位红黑树

两个条件，必须同时满足两个条件才能进行转换

• 条件1：单个链表长度大于等于8
• 条件2：hashMap的总长度大于64个、且树化的节点位置不能为空
  从源码看
  条件一：
  在putVal()方法中，可知当binCount大于7即节点数大于8时进行

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
 // ...省略
  for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
      p.next = newNode(hash, key, value, null);
// TREEIFY_THRESHOLD == 8 当binCount大于等于7时 即结点数大于八时进行
      if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
        treeifyBin(tab, hash);
      break;
    }
  }
//...省略
}

条件二：
对于treeifyBin（）方法

    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
// MIN_TREEIFY_CAPACITY= 64 当数据长度小于64是进行扩容 大于64才进行树化
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
// 且树化的节点位置不能为空
        else if ((e = tab[index = (n - 1) & hash]) != null) {
//... 省略
  }
}

红黑树退化为链表

两种情况

• 第一 树内节点数小于等于6
• 第二：根节点为空，根节点的左右子树为空，根节点的左子树的左子树为空

// 条件一 在树的空间调整代码中
     final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
//...省略
            for (TreeNode<K,V> e = b, next; e != null; e = next) {
                next = (TreeNode<K,V>)e.next;
                e.next = null;
                if ((e.hash & bit) == 0) {
                    if ((e.prev = loTail) == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                    ++lc;
                }
                else {
                    if ((e.prev = hiTail) == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                    ++hc;
                }
            }

            if (loHead != null) {
  // lc 记录的是存放在原本位置不变的数据的个数
  //UNTREEIFY_THRESHOLD = 6  untreeify() 树的退化操作
                if (lc <= UNTREEIFY_THRESHOLD)
                    tab[index] = loHead.untreeify(map);
                else {
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                        loHead.treeify(tab);
                }
            }
//... 省略
}

//条件二 在移除树节点的方法内 removeTreeNode()
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                  boolean movable) {
// 进行对根节点，左右子树，左左子树的判断然后进行进行退化操作
   if (root == null || root.right == null ||
                  (rl = root.left) == null || rl.left == null) {
                  tab[index] = first.untreeify(map);  // too small
                  return;
              }
}