HashMap在jdk1.8之后引入了红黑树的概念，表示若桶中链表元素超过8时，会自动转化成红黑树；若桶中元素小于等于6时，树结构还原成链表形式。

原因：

红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。

还有选择6和8的原因是：

中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。
————————————————
版权声明：本文为CSDN博主「创客公元」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_37264997/article/details/106074846

jdk1.8的hashmap真的是大于8就转换成红黑树，小于6就变成链表吗?????

最近研究hashmap源码的时候，会结合网上的一些博客来促进理解。而关于红黑树和链表相互转换这一块，大部分的文章都会这样描述：hashmap中定义了两个常量：

/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;

/\*\*  
 \* The bin count threshold for untreeifying a (split) bin during a  
 \* resize operation. Should be less than TREEIFY\_THRESHOLD, and at  
 \* most 6 to mesh with shrinkage detection under removal.  
 \*/  
static final int UNTREEIFY\_THRESHOLD = 6;

当链表元素个数大于8的时候，就会转换为红黑树；当红黑树元素个数小于6的时候，就会转换回链表。
hashMap中确实定义了这两个常量，但并非简单通过元素个数的判断来进行转换。

链表转换为红黑树的最终目的，是为了解决在map中元素过多，hash冲突较大，而导致的读写效率降低的问题。在源码的putVal方法中，有关红黑树结构化的分支为：

        //此处遍历链表  
        for (int binCount = 0; ; ++binCount) {  
            //遍历到链表最后一个节点  
            if ((e = p.next) == null) {  
                p.next = newNode(hash, key, value, null);  
                //如果链表元素个数大于等于TREEIFY\_THRESHOLD  
                if (binCount >= TREEIFY\_THRESHOLD - 1) // -1 for 1st  
                    //红黑树转换逻辑  
                    treeifyBin(tab, hash);  
                break;  
            }  
            if (e.hash == hash &&  
                ((k = e.key) == key || (key != null && key.equals(k))))  
                break;  
            p = e;  
        }

即网上所说的，链表的长度大于8的时候，就转换为红黑树，我们来看看treeifyBin方法：

final void treeifyBin(Node<K,V>\[\] tab, int hash) {  
    int n, index; Node<K,V> e;  
    //首先tab的长度是否小于64,  
    if (tab == null || (n = tab.length) < MIN\_TREEIFY\_CAPACITY)  
    //小于64则进行扩容  
        resize();  
    else if ((e = tab\[index = (n - 1) & hash\]) != null) {  
        //否则才将列表转换为红黑树  
        TreeNode<K,V> hd = null, tl = null;  
        do {  
            TreeNode<K,V> p = replacementTreeNode(e, null);  
            if (tl == null)  
                hd = p;  
            else {  
                p.prev = tl;  
                tl.next = p;  
            }  
            tl = p;  
        } while ((e = e.next) != null);  
        if ((tab\[index\] = hd) != null)  
            hd.treeify(tab);  
    }  
}

可以看到在treeifyBin中并不是简单地将链表转换为红黑树，而是先判断table的长度是否大于64，如果小于64，就通过扩容的方式来解决，避免红黑树结构化。
链表长度大于8有两种情况：

• table长度足够，hash冲突过多
• hash没有冲突，但是在计算table下标的时候，由于table长度太小，导致很多hash不一致的
  第二种情况是可以用扩容的方式来避免的，扩容后链表长度变短，读写效率自然提高。另外，扩容相对于转换为红黑树的好处在于可以保证数据结构更简单。
  由此可见并不是链表长度超过8就一定会转换成红黑树，而是先尝试扩容

基本思想是当红黑树中的元素减少并小于一定数量时，会切换回链表。而元素减少有两种情况：
1、调用map的remove方法删除元素

final Node removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node[] tab; Node p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node node = null, e; K k; V v;
//根据hash值以及key判断当前的是否相等,如果相等直接返回
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
//判断是否为红黑树结构
if (p instanceof TreeNode)
node = ((TreeNode)p).getTreeNode(hash, key);
else {
//如果不是则为链表结构
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//判断当前桶是否是红黑树结构,如果是的话
if (node instanceof TreeNode)
((TreeNode)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}

final void removeTreeNode(HashMap map, Node[] tab,
boolean movable) {
int n;
if (tab == null || (n = tab.length) == 0)
return;
int index = (n - 1) & hash;
TreeNode first = (TreeNode)tab[index], root = first, rl;
TreeNode succ = (TreeNode)next, pred = prev;
if (pred == null)
tab[index] = first = succ;
else
pred.next = succ;
if (succ != null)
succ.prev = pred;
if (first == null)
return;
if (root.parent != null)
root = root.root();
//判断是否解除红黑树结构
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
tab[index] = first.untreeify(map); // too small
return;
}
TreeNode p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
TreeNode s = pr, sl;
while ((sl = s.left) != null) // find successor
s = sl;
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode sr = s.right;
TreeNode pp = p.parent;
if (s == pr) { // p was s's direct parent
p.parent = s;
s.right = p;
}
else {
TreeNode sp = s.parent;
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
pr.parent = s;
}
p.left = null;
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
if (sr != null)
replacement = sr;
else
replacement = p;
}
else if (pl != null)
replacement = pl;
else if (pr != null)
replacement = pr;
else
replacement = p;
if (replacement != p) {
TreeNode pp = replacement.parent = p.parent;
if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}

        TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);

        if (replacement == p) {  // detach  
            TreeNode<K,V> pp = p.parent;  
            p.parent = null;  
            if (pp != null) {  
                if (p == pp.left)  
                    pp.left = null;  
                else if (p == pp.right)  
                    pp.right = null;  
            }  
        }  
        if (movable)  
            moveRootToFront(tab, r);  
    }

可以看到，此处并没有利用到网上所说的，当节点数小于UNTREEIFY_THRESHOLD时才转换，而是通过红黑树根节点及其子节点是否为空来判断。

resize的时候，判断节点类型，如果是链表，则将链表拆分，如果是TreeNode，则执行TreeNode的split方法分割红黑树，而split方法中将红黑树转换为链表的分支如下：

final void split(HashMap map, Node[] tab, int index, int bit) {
TreeNode b = this;
// Relink into lo and hi lists, preserving order
TreeNode loHead = null, loTail = null;
TreeNode hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode e = b, next; e != null; e = next) {
next = (TreeNode)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;
}
}
//在这之前的逻辑是将红黑树每个节点的hash和一个bit进行&运算，
//根据运算结果将树划分为两棵红黑树，lc表示其中一棵树的节点数
if (loHead != null) {
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) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}

这里才用到了 UNTREEIFY_THRESHOLD 的判断，当红黑树节点元素小于等于6时，才调用untreeify方法转换回链表

1、hashMap并不是在链表元素个数大于8就一定会转换为红黑树，而是先考虑扩容，扩容达到默认限制后才转换。
2、hashMap的红黑树不一定小于6的时候才会转换为链表，而是只有在resize的时候才会根据 UNTREEIFY_THRESHOLD 进行转换。