HashMap中红黑树扩容split()

亦凉 2023-10-01 21:46 30阅读 0赞

HashMap中红黑树的扩容和链表的扩容相似，都是拉高低链表，拆分

链表扩容的源码解读见：[HashMap扩容操作resize（链表扩容）][HashMap_resize]

### 上源码 ###

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
                TreeNode<K,V> b = this;
                // Relink into lo and hi lists, preserving order
        		//定义低位链表的头尾节点
                TreeNode<K,V> loHead = null, loTail = null;
        		//定义高位链表的头尾节点
                TreeNode<K,V> hiHead = null, hiTail = null;
        		//分别记录低位链表和高位链表的长度，决定着后续红黑树是否要转回链表
                int lc = 0, hc = 0;
        		//因为红黑树是由链表改造的，所以红黑树的扩容还是对链表进行操作
        		//对for循环链表(红黑树)进行高低拆分操作
                for (TreeNode<K,V> e = b, next; e != null; e = next) {
                    //取e的下一节点赋值给next遍历
                    next = (TreeNode<K,V>)e.next;
                    //取好e的下一个节点后将其赋值为空，方便GC回收
                    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;
                    }
                }
    			/*
    				拆分之后判断链表的长度是否<=UNTREEIFY_THRESHOLD=6
    				如果满足，则将红黑树转回链表
    			*/
        		//如果低位链表首节点不为null，说明有这个链表存在
                if (loHead != null) {
                    //如果低位链表的长度<=UNTREEIFY_THRESHOLD=6
                    if (lc <= UNTREEIFY_THRESHOLD)
                        //调用红黑树转链表的方法
                        tab[index] = loHead.untreeify(map);
                    else {
                        //否则，把红黑树的头节点转移到数组的新节点上(红黑树的根节点一定是链表的头节点)
                        //下标 = 原数组下标
                        tab[index] = loHead;
                        //如果存在高位链表，说明红黑树已经被拆分成两个链表
                        if (hiHead != null) // (else is already treeified)
                            //构建新的红黑树
                            loHead.treeify(tab);
                    }
                }
        		//如果高位链表首节点不为null，说明有这个链表存在
                if (hiHead != null) {
                    如果高位链表的长度<=UNTREEIFY_THRESHOLD=6
                    if (hc <= UNTREEIFY_THRESHOLD)
                         //调用红黑树转链表的方法
                        tab[index + bit] = hiHead.untreeify(map);
                    else {
                        //否则，把红黑树的头节点转移到数组的新节点上(红黑树的根节点一定是链表的头节点)
                        //下标 = 原数组下标 + 原数组长度
                        tab[index + bit] = hiHead;
                        //如果存在低位链表，说明红黑树已经被拆分成两个链表
                        if (loHead != null)
                            //构建新的红黑树
                            hiHead.treeify(tab);
                    }
                }
            }

[HashMap_resize]: https://blog.csdn.net/weixin_57504474/article/details/124428081?spm=1001.2014.3001.5501