HashMap中红黑树TreeNode的split()方法源码分析

向右看齐 2023-03-03 14:26 36阅读 0赞

spit()方法的作用是将旧数组转移到新数组，split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit)方法的四个参数
     分别是：当前hashMap对象、新数组、正在遍历的旧数组下标、旧数组的长度。在分析HashMap$TreeNode(既是树又是链表)
     的split()方法的源码时，我们会发现它主要分两部分操作：

*  一、数据从旧数组转移到新数组中时，旧数组上的数据会根据(e.hash & bit)是否等于0，重新rehash计算其在数组上的索引位置，分两种情况：

1、等于0时，则将该树链表头节点放到新数组时的索引位置等于其在旧数组时的索引位置，记为低位区树链表lo。
     2、不等于0时，则将该树链表头节点放到新数组时的索引位置等于其在旧数组时的索引位置再加上旧数组长度，记为高位区树链表hi。

*  二、当红黑树被split分割开成为两个小红黑树后：

1、当低位区小红黑树元素个数小于等于6时，开始去树化untreeify操作；
     2、当低位区小红黑树元素个数大于6且高位区红黑树不为null时，开始树化操作(赋予红黑树的特性)。

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 (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)//低位尾部标记为null,表示还未开始处理，此时e是第一个要处理的低位树链表
                        //节点，故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) { //低位树链表不为null
                    if (lc <= UNTREEIFY_THRESHOLD)//低位树链表元素个数若小于等于6
                        tab[index] = loHead.untreeify(map);//开始去树化操作(就是将元素TreeNode节点都转换成Node节点)
                    else { 
                        tab[index] = loHead;
                        if (hiHead != null) // (else is already treeified) //若高位数链表头节点为空，说明还没有处理完高位
                        //，还不能进行树化操作
                            loHead.treeify(tab);//低位树链表元素个数若大于6且高位树链表头节点不等于null，开始将低位树链表真
                            //正树化成红黑树(前面都只是挂着TreeNode的名号，但实际只是链表结构，还没包含红黑树的特性，
                            //在这里才赋予了它红黑树的特性)
                    }
                }
                if (hiHead != null) { //高位树链表不为null
                    if (hc <= UNTREEIFY_THRESHOLD)//高位树链表元素个数若小于等于6
                        tab[index + bit] = hiHead.untreeify(map);//开始去树化操作(就是将元素TreeNode节点都转换成Node节点)
                    else { 
                        tab[index + bit] = hiHead;
                        if (loHead != null) //若低位数链表头节点为空，说明还没有处理完低位，还不能进行树化操作
                            hiHead.treeify(tab);//高位树链表元素个数若大于6且低位树链表头节点不等于null，
                            //开始将高位树链表真正树化成红黑树
                    }
                }
            }