对hashMap中,等于6还是小于6红黑树会退化为链表的理解

对hashMap中,等于6还是小于6红黑树会退化为链表的理解:

当对hashMap扩容时,会调用resize方法,resize会以桶(一个哈希表下标下所有元素)为单位,把元素转移到新哈希表中, 当桶为红黑树时,会调用split方法进行红黑树的扩容移动处理。

split方法中会出现红黑树退化为链表情况(整个hashMap中也只有这个方法会出现红黑树退化为链表的情况)。

split方法中,将当前红黑树分割放入lo,hi这两个变量(treeNode类型)里。可以先理解为两条链表。当lo链表中元素<=6,会将lo转换为真正的链表(Node类型),当lo链表中元素>6,则会进行树化处理, 例如对链表中节点的left,right等进行赋值,hi树同理。

以下是split方法源码:

(树化及退树化方法省略)


```java
/**
 * 从hashmap桶(一个哈希表数组某个索引下的元素,可以是单个node,
 * 可以是一个链表,也可以是一颗红黑树,此时为红黑树)中将红黑树分割成两棵树,
 *一颗为高位树hi,一颗为低位树lo,如果hi或者lo树节点太小,该树将会退化为链表
 * 再移动到新哈希表中,该方法仅在resize()方法调用到
 
 *
 * @param map 需要扩容的map,用于红黑树退化链表时,调用当前map类型的
 * replacementNode方法
 * @param tab 新的哈希表,存放扩容后元素
 * @param index 当前索引,扩容是从索引0的桶开始向右,以桶为单位进行扩容的
 * @param bit 扩容前哈希表容量
 */
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    //红黑树在node数组上的元素
    TreeNode<K,V> b = this;
    //loHead 低位树头结点, loTail 低位树尾结点
    TreeNode<K,V> loHead = null, loTail = null;
    //hiHead 高位树头结点, hiTail 高位树尾结点
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    //红黑树为链表转换而成,hashmap链表节点(node类型)在转换成红黑树(treeNode类型)时
    //保留了原有node节点的变量(next等等),数据,用于进行迭代器遍历,及退化为链表
    
    //虽然是红黑树,不过保留了next,可以按照链表方式进行遍历
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        //如果当前节点hash与运算扩容前map容量为0,代表扩容后索引位置不变
        //扩容后索引位置不变的节点放在低位树中
        if ((e.hash & bit) == 0) {
            //尾结点为空,此时还未放入输入,设置头结点为e
            if ((e.prev = loTail) == null)
                loHead = e;
           //尾结点不为空,此时已有数据,将尾结点next指向当前数据(尾插法)
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }
    //lc,hc从0开始增加,lo树中有6个元素,则lc=6
    //hi树有6个元素,则hc=6

    if (loHead != null) {
        //hashMap中UNTREEIFY_THRESHOLD设置为6
        //lc<=6,将lo树退化为链表,也就是lc树中有6个元素,就会退化为链表
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
            
        /**lc>6 将lc转化为真正的红黑树结构
        *前面lc只是next赋值了,还只是链表结构
        */红黑树需要对parent,left,right等属性赋值
        else {
            tab[index] = loHead;
            if (hiHead != null)  
                loHead.treeify(tab);
        }
    }
    //hi树与lo同理
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}
/**
*   hi树与lo树区别:
*  hi树放在扩容后哈希表的(旧哈希表index+旧哈希表容量)索引位置
*  lo树放在扩容后哈希表的(旧哈希表index)索引位置
*/

结论:
1.调用到了resize方法才可能会退化,没调用即使长度小于6也不会退化
2.小于等于6,进行退化,是针对分割后lo与hi这两条链表而言的,不能等价于整个树的长度。
3.只有lo链表或者hi链表长度小于等于6,才会进行退化(此时的退化是指将当前链表节点类型从treeNode转为Node)
4.lo,hi链表大于6会进行树化的具体操作
5.如果lo为null,不会进行任何操作,hi同理。

上一篇:Java - hello/hi的简单的网络聊天程序


下一篇:Lagrangian乘子法 对偶问题 KKT条件 Slater条件 与凸优化