JDK1.8 HashMap源码之扩容时处理红黑树的split、 treeify系列方法分析（三）

╰半橙微兮° 2022-11-19 01:09 83阅读 0赞

上一篇分析了hashMap 扩容原理，[预先参考][Link 1]，今天接着分析其中的split方法。

首先这个方法只在HashMap进行扩容时会调用到: ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

参数详解：

/** 这个方法在HashMap进行扩容时会调用到:  ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
     * @param map 代表要扩容的HashMap
     * @param tab 代表新创建的数组，用来存放旧数组迁移的数据
     * @param index 代表旧数组的索引
     * @param bit 代表旧数组的长度，需要配合使用来做按位与运算
     *    
     */

1、split方法注解后的源码：

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
        //做个赋值，因为这里是((TreeNode<K,V>)e)这个对象调用split()方法，所以this就是指(TreeNode<K,V>)e对象，所以才能类型对应赋值
        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;//定义两个变量lc和hc，初始值为0，后面比较要用，他们的大小决定了红黑树是否要转回链表
        //这个for循环就是对从e节点开始对整个红黑树做遍历
        for (TreeNode<K,V> e = b, next; e != null; e = next) {
            next = (TreeNode<K,V>)e.next;//取e的下一节点赋值给next遍历
            e.next = null;//取好e的下一节点后，把它赋值为空，方便GC回收
            /**
             * 1、等于0时，则将该树链表头节点放到新数组时的索引位置等于其在旧数组时的索引位置，记为低位区树链表lo。
             *  2、不等于0时，则将该树链表头节点放到新数组时的索引位置等于其在旧数组时的索引位置再加上旧数组长度，记为高位区树链表hi。
             *
             *  以下的操作就是做个按位与运算，按照结果拉出两条链表
             */
            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，即如果低位链表首节点不为null，说明有这个链表存在
            /**
             * 1、当低位区小红黑树元素个数小于等于6时，开始去树化untreeify操作；
             *  2、当低位区小红黑树元素个数大于6且高位区红黑树不为null时，开始树化操作(赋予红黑树的特性)。
             */
            if (lc <= UNTREEIFY_THRESHOLD)//低位树链表元素个数若小于等于6
                //那就从红黑树转链表了，低位链表，迁移到新数组中下标不变，还是等于原数组到下标
                tab[index] = loHead.untreeify(map);//开始去树化操作(就是将元素TreeNode节点都转换成Node节点)
            else {
                tab[index] = loHead;//低位链表，迁移到新数组中下标不变，还是等于原数组到下标，把低位链表整个拉到这个下标下，做个赋值
                //如果高位首节点不为空，说明原来的红黑树已经被拆分成两个链表了
                if (hiHead != null) // (else is already treeified) 若高位数链表头节点为空，说明还没有处理完高位，还不能进行树化操作
                /**
                 * 低位树链表元素个数若大于6且高位树链表头节点不等于null，开始将低位树链表真
                 * 正树化成红黑树(前面都只是挂着TreeNode的名号，但实际只是链表结构，还没包含红黑树的特性，
                 *  在这里才赋予了它红黑树的特性)
                 */
                    loHead.treeify(tab);
            }
        }
        //如果高位链表首节点不为null，说明有这个链表存在
        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，开始将高位树链表真正树化成红黑树
            }
        }
    }

2、点击 untreeify(map);方法：

final Node<K,V> untreeify(HashMap<K,V> map) {
        Node<K,V> hd = null, tl = null;
        for (Node<K,V> q = this; q != null; q = q.next) {
            Node<K,V> p = map.replacementNode(q, null);
            if (tl == null)
                hd = p;
            else
                tl.next = p;
            tl = p;
        }
        return hd;
    }

3、点击replacementNode方法，把树变成链表结构：

Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
        return new Node<>(p.hash, p.key, p.value, next);
    }

4、点击  treeify(tab);方法：

final void treeify(Node<K,V>[] tab) {
        TreeNode<K,V> root = null;// 定义树的根节点
        for (TreeNode<K,V> x = this, next; x != null; x = next) {// 遍历链表，x指向当前节点、next指向下一个节点
            next = (TreeNode<K,V>)x.next;// 下一个节点
            x.left = x.right = null;// 设置当前节点的左右节点为空
            if (root == null) {// 如果还没有根节点
                x.parent = null;// 当前节点的父节点设为空
                x.red = false;// 当前节点的红色属性设为false（把当前节点设为黑色）
                root = x;// 根节点指向到当前节点
            }
            else {// 如果已经存在根节点了
                K k = x.key;// 取得当前链表节点的key
                int h = x.hash;// 取得当前链表节点的hash值
                Class<?> kc = null;// 定义key所属的 Class
                for (TreeNode<K,V> p = root;;) {// 从根节点开始遍历，此遍历没有设置边界，只能从内部跳出
                    int dir, ph;// dir 标识方向（左右）、ph标识当前树节点的hash值
                    K pk = p.key;// 当前树节点的key
                    if ((ph = p.hash) > h)// 如果当前树节点hash值 大于 当前链表节点的hash值
                        dir = -1;// 标识当前链表节点会放到当前树节点的左侧
                    else if (ph < h)
                        dir = 1;// 右侧
                    /*
                     * 如果两个节点的key的hash值相等，那么还要通过其他方式再进行比较
                     * 如果当前链表节点的key实现了comparable接口，并且当前树节点和链表节点是相同Class的实例，那么通过comparable的方式再比较两者。
                     * 如果还是相等，最后再通过tieBreakOrder比较一次
                     */
                    else if ((kc == null &&
                            (kc = comparableClassFor(k)) == null) ||
                            (dir = compareComparables(kc, k, pk)) == 0)
                        //如果两者不具有compare的资格，或者compare之后仍然没有比较出大小。那么就要通过一个决胜局再比一次，这个决胜局就是tieBreakOrder方法。
                        dir = tieBreakOrder(k, pk);
    
                    TreeNode<K,V> xp = p;// 保存当前树节点
                    /*
                     * 如果dir 小于等于0 ： 当前链表节点一定放置在当前树节点的左侧，但不一定是该树节点的左孩子，也可能是左孩子的右孩子 或者 更深层次的节点。
                     * 如果dir 大于0 ： 当前链表节点一定放置在当前树节点的右侧，但不一定是该树节点的右孩子，也可能是右孩子的左孩子 或者 更深层次的节点。
                     * 如果当前树节点不是叶子节点，那么最终会以当前树节点的左孩子或者右孩子 为 起始节点  再从GOTO1 处开始 重新寻找自己（当前链表节点）的位置
                     * 如果当前树节点就是叶子节点，那么根据dir的值，就可以把当前链表节点挂载到当前树节点的左或者右侧了。
                     * 挂载之后，还需要重新把树进行平衡。平衡之后，就可以针对下一个链表节点进行处理了。
                     */
                    if ((p = (dir <= 0) ? p.left : p.right) == null) {
                        x.parent = xp;// 当前链表节点 作为 当前树节点的子节点
                        if (dir <= 0)
                            xp.left = x;// 作为左孩子
                        else
                            xp.right = x;// 作为右孩子
                        root = balanceInsertion(root, x);// 重新平衡，单独解析
                        break;
                    }
                }
            }
        }
        // 把所有的链表节点都遍历完之后，最终构造出来的树可能经历多个平衡操作，根节点目前到底是链表的哪一个节点是不确定的
        // 因为我们要基于树来做查找，所以就应该把 tab[N] 得到的对象一定根节点对象，而目前只是链表的第一个节点对象，所以要做相应的处理。
        moveRootToFront(tab, root);// 单独解析
    }

5、点击 comparableClassFor 方法：

/**
     *  
     * 那么hash值相同的时候呢？这时还是会先尝试看是否能够通过Comparable进行比较一下两个对象（当前节点的键对象和新元素的键对象），
     * 要想看看是否能基于Comparable进行比较的话，首先要看该元素键是否实现了Comparable接口，此时就需要用到comparableClassFor
     * 方法来获取该元素键的Class，然后再通过compareComparables方法来比较两个对象的大小
     * @param x
     * @return
     */
    /**
     * 如果对象x的类是C，如果C实现了Comparable<C>接口，那么返回C，否则返回null
     */
    static Class<?> comparableClassFor(Object x) {
        if (x instanceof Comparable) {
            Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
            if ((c = x.getClass()) == String.class) // 如果x是个字符串对象
                return c; // 返回String.class
            /*
             * 为什么如果x是个字符串就直接返回c了呢 ? 因为String  实现了 Comparable 接口，可参考如下String类的定义
             * public final class String implements java.io.Serializable, Comparable<String>, CharSequence
             */
    
            // 如果 c 不是字符串类，获取c直接实现的接口（如果是泛型接口则附带泛型信息）
            if ((ts = c.getGenericInterfaces()) != null) {
                for (int i = 0; i < ts.length; ++i) { // 遍历接口数组
                    // 如果当前接口t是个泛型接口
                    // 如果该泛型接口t的原始类型p 是 Comparable 接口
                    // 如果该Comparable接口p只定义了一个泛型参数
                    // 如果这一个泛型参数的类型就是c，那么返回c
                    if (((t = ts[i]) instanceof ParameterizedType) &&
                            ((p = (ParameterizedType)t).getRawType() ==
                                    Comparable.class) &&
                            (as = p.getActualTypeArguments()) != null &&
                            as.length == 1 && as[0] == c) // type arg is c
                        return c;
                }
                // 上面for循环的目的就是为了看看x的class是否 implements  Comparable<x的class>
            }
        }
        return null; // 如果c并没有实现 Comparable<c> 那么返回空
    }

6、点击 compareComparables 方法：

/**
     * 如果x所属的类是kc，返回k.compareTo(x)的比较结果
     * 如果x为空，或者其所属的类不是kc，返回0
     */
    static int compareComparables(Class<?> kc, Object k, Object x) {
        return (x == null || x.getClass() != kc ? 0 :
                ((Comparable)k).compareTo(x));
    }

7、点击  tieBreakOrder 方法：

/**
     * 用这个方法来比较两个对象，返回值要么大于0，要么小于0，不会为0
     * 也就是说这一步一定能确定要插入的节点要么是树的左节点，要么是右节点，不然就无法继续满足二叉树结构了
     *
     * 先比较两个对象的类名，类名是字符串对象，就按字符串的比较规则
     * 如果两个对象是同一个类型，那么调用本地方法为两个对象生成hashCode值，再进行比较，hashCode相等的话返回-1
     */
    static int tieBreakOrder(Object a, Object b) {
        int d;
        if (a == null || b == null ||
                (d = a.getClass().getName().
                        compareTo(b.getClass().getName())) == 0)
            d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                    -1 : 1);
        return d;
    }

8、点击 balanceInsertion(root, x);方法：

/**
     *  
     * 当树结构中新插入了一个节点后，要对树进行重新的结构化，以保证该树始终维持红黑树的特性。
     * root 当前根节点
     * x 新插入的节点
     * 返回重新平衡后的根节点
     * @return
     */
    static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                TreeNode<K,V> x) {
        x.red = true;// 新插入的节点标为红色
        /*
         * 这一步即定义了变量，又开起了循环，循环没有控制条件，只能从内部跳出
         * xp：当前节点的父节点、xpp：爷爷节点、xppl：左叔叔节点、xppr：右叔叔节点
         */
        for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
            // 如果父节点为空、说明当前节点就是根节点，那么把当前节点标为黑色，返回当前节点
            if ((xp = x.parent) == null) {// L1
                x.red = false;
                return x;
            }
            // 父节点不为空
            // 如果父节点为黑色 或者 【（父节点为红色 但是 爷爷节点为空） -> 这种情况何时出现？】
            else if (!xp.red || (xpp = xp.parent) == null)// L2
                return root;
            if (xp == (xppl = xpp.left)) {// 如果父节点是爷爷节点的左孩子  // L3
                if ((xppr = xpp.right) != null && xppr.red) {// 如果右叔叔不为空 并且 为红色  // L3_1
                    xppr.red = false;// 右叔叔置为黑色
                    xp.red = false;// 父节点置为黑色
                    xpp.red = true;// 爷爷节点置为红色
                    x = xpp;// 运行到这里之后，就又会进行下一轮的循环了，将爷爷节点当做处理的起始节点
                }
                else {// 如果右叔叔为空 或者 为黑色 // L3_2
                    if (x == xp.right) {// 如果当前节点是父节点的右孩子 // L3_2_1
                        root = rotateLeft(root, x = xp);// 父节点左旋，见下文左旋方法解析,重点分析
                        xpp = (xp = x.parent) == null ? null : xp.parent;// 获取爷爷节点
                    }
                    if (xp != null) {// 如果父节点不为空 // L3_2_2
                        xp.red = false;// 父节点 置为黑色
                        if (xpp != null) {// 爷爷节点不为空
                            xpp.red = true;// 爷爷节点置为 红色
                            root = rotateRight(root, xpp);//爷爷节点右旋，见下文右旋方法解析
                        }
                    }
                }
            }
            else {// 如果父节点是爷爷节点的右孩子 // L4
                if (xppl != null && xppl.red) {// 如果左叔叔是红色 // L4_1
                    xppl.red = false; // 左叔叔置为 黑色
                    xp.red = false; // 父节点置为黑色
                    xpp.red = true; // 爷爷置为红色
                    x = xpp; // 运行到这里之后，就又会进行下一轮的循环了，将爷爷节点当做处理的起始节点
                }
                else { // 如果左叔叔为空或者是黑色 // L4_2
                    if (x == xp.left) { // 如果当前节点是个左孩子 // L4_2_1
                        root = rotateRight(root, x = xp); // 针对父节点做右旋，见下文右旋方法解析
                        xpp = (xp = x.parent) == null ? null : xp.parent; // 获取爷爷节点
                    }
                    if (xp != null) { // 如果父节点不为空 // L4_2_4
                        xp.red = false; // 父节点置为黑色
                        if (xpp != null) { //如果爷爷节点不为空
                            xpp.red = true; // 爷爷节点置为红色
                            root = rotateLeft(root, xpp); // 针对爷爷节点做左旋
                        }
                    }
                }
            }
        }
    }

点击左旋方法  rotateLeft

/**
     * 节点左旋
     * root 根节点
     * p 要左旋的节点
     */
    static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                          TreeNode<K,V> p) {
        TreeNode<K,V> r, pp, rl;
        if (p != null && (r = p.right) != null) { // 要左旋的节点以及要左旋的节点的右孩子不为空
            if ((rl = p.right = r.left) != null) // 要左旋的节点的右孩子的左节点 赋给 要左旋的节点的右孩子 节点为：rl
                rl.parent = p; // 设置rl和要左旋的节点的父子关系【之前只是爹认了孩子，孩子还没有答应，这一步孩子也认了爹】
    
            // 将要左旋的节点的右孩子的父节点  指向 要左旋的节点的父节点，相当于右孩子提升了一层，
            // 此时如果父节点为空， 说明r 已经是顶层节点了，应该作为root 并且标为黑色
            if ((pp = r.parent = p.parent) == null)
                (root = r).red = false;
            else if (pp.left == p) // 如果父节点不为空 并且 要左旋的节点是个左孩子
                pp.left = r; // 设置r和父节点的父子关系【之前只是孩子认了爹，爹还没有答应，这一步爹也认了孩子】
            else // 要左旋的节点是个右孩子
                pp.right = r;
            r.left = p; // 要左旋的节点  作为 他的右孩子的左节点
            p.parent = r; // 要左旋的节点的右孩子  作为  他的父节点
        }
        return root; // 返回根节点
    }

点击右旋方法 rotateRight：

/**
     * 节点右旋
     * root 根节点
     * p 要右旋的节点
     */
    static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                           TreeNode<K,V> p) {
        TreeNode<K,V> l, pp, lr;
        if (p != null && (l = p.left) != null) { // 要右旋的节点不为空以及要右旋的节点的左孩子不为空
            if ((lr = p.left = l.right) != null) // 要右旋的节点的左孩子的右节点 赋给 要右旋节点的左孩子 节点为：lr
                lr.parent = p; // 设置lr和要右旋的节点的父子关系【之前只是爹认了孩子，孩子还没有答应，这一步孩子也认了爹】
    
            // 将要右旋的节点的左孩子的父节点  指向 要右旋的节点的父节点，相当于左孩子提升了一层，
            // 此时如果父节点为空， 说明l 已经是顶层节点了，应该作为root 并且标为黑色
            if ((pp = l.parent = p.parent) == null)
                (root = l).red = false;
            else if (pp.right == p) // 如果父节点不为空 并且 要右旋的节点是个右孩子
                pp.right = l; // 设置l和父节点的父子关系【之前只是孩子认了爹，爹还没有答应，这一步爹也认了孩子】
            else // 要右旋的节点是个左孩子
                pp.left = l; // 同上
            l.right = p; // 要右旋的节点 作为 他左孩子的右节点
            p.parent = l; // 要右旋的节点的父节点 指向 他的左孩子
        }
        return root;
    }

9、点击  moveRootToFront(tab, root);方法：

/**
     *  
     * 把红黑树的根节点设为  其所在的数组槽 的第一个元素
     * 首先明确：TreeNode既是一个红黑树结构，也是一个双链表结构
     * 这个方法里做的事情，就是保证树的根节点一定也要成为链表的首节点
     */
    static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
        int n;
        if (root != null && tab != null && (n = tab.length) > 0) {// 根节点不为空 并且 HashMap的元素数组不为空
            int index = (n - 1) & root.hash;// 根据根节点的Hash值 和 HashMap的元素数组长度  取得根节点在数组中的位置
            TreeNode<K,V> first = (TreeNode<K,V>)tab[index];// 首先取得该位置上的第一个节点对象
            if (root != first) {// 如果该节点对象 与 根节点对象 不同
                Node<K,V> rn;// 定义根节点的后一个节点
                tab[index] = root;// 把元素数组index位置的元素替换为根节点对象
                TreeNode<K,V> rp = root.prev;// 获取根节点对象的前一个节点
                if ((rn = root.next) != null)// 如果后节点不为空
                    ((TreeNode<K,V>)rn).prev = rp;// root后节点的前节点  指向到 root的前节点，相当于把root从链表中摘除
                if (rp != null)// 如果root的前节点不为空
                    rp.next = rn;// root前节点的后节点 指向到 root的后节点
                if (first != null)// 如果数组该位置上原来的元素不为空
                    first.prev = root;// 这个原有的元素的 前节点 指向到 root，相当于root目前位于链表的首位
                root.next = first;// 原来的第一个节点现在作为root的下一个节点，变成了第二个节点
                root.prev = null;// 首节点没有前节点
            }
            /*
             * 这一步是防御性的编程
             * 校验TreeNode对象是否满足红黑树和双链表的特性
             * 如果这个方法校验不通过：可能是因为用户编程失误，破坏了结构（例如：并发场景下）；也可能是TreeNode的实现有问题（这个是理论上的以防万一）；
             */
            assert checkInvariants(root);
        }
    }

点击 checkInvariants 检查方法：

/**
     * Recursive invariant check  递归检查此红黑树是否标准
     */
    static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
        TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
                tb = t.prev, tn = (TreeNode<K,V>)t.next;
        if (tb != null && tb.next != t)
            return false;
        if (tn != null && tn.prev != t)
            return false;
        if (tp != null && t != tp.left && t != tp.right)
            return false;
        if (tl != null && (tl.parent != t || tl.hash > t.hash))
            return false;
        if (tr != null && (tr.parent != t || tr.hash < t.hash))
            return false;
        if (t.red && tl != null && tl.red && tr != null && tr.red)
            return false;
        if (tl != null && !checkInvariants(tl))
            return false;
        if (tr != null && !checkInvariants(tr))
            return false;
        return true;
    }

到此，扩容时处理红黑树的分析完毕,下篇分析添加数据时putVal函数中处理红黑树的putTreeVal系列方法，敬请期待。

[Link 1]: https://blog.csdn.net/nandao158/article/details/115676126