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

约定不等于承诺〃 2024-04-20 08:17 61阅读 0赞

一、概述

TreeNode在增加或删除节点后，都需要对整个树重新进行平衡，平衡之后的根节点也许就会发生变化，此时为了保证：如果HashMap元素数组根据下标取得的元素是一个TreeNode类型，那么这个TreeNode节点一定要是这颗树的根节点，同时也要是整个链表的首节点。

二、方法解析

/**
     * 把红黑树的根节点设为  其所在的数组槽 的第一个元素
     * 首先明确：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); 
        }
    }