JDK8：HashMap源码解析：TreeNode类的treeify方法

冷不防 2024-04-20 08:13 58阅读 0赞

一、概述

treeify方法是TreeNode类的一个实例方法，通过TreeNode对象调用，实现该对象打头的链表转换为树结构。

二、方法解析

/**
     * 参数为HashMap的元素数组
     */
    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;;) { // 从根节点开始遍历，此遍历没有设置边界，只能从内部跳出
                    // GOTO1
                    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)
                        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); // 单独解析
    }