专栏首页格子的个人博客Java源码阅读之红黑树在HashMap中的应用 - JDK1.8

Java源码阅读之红黑树在HashMap中的应用 - JDK1.8

阅读优秀的源码是提升编程技巧的重要手段之一。 如有不对的地方,欢迎指正~ 转载请注明出处https://blog.lzoro.com

前言

基于JDK1.8

JDK1.8之前,HashMap并没有采用红黑树,所以哈希桶上的链表过长时,就会有效率问题。

JDK1.8,则在HashMap引入了红黑树,当链表长度超过指定阈值(默认为8),则进行树化并提供相关操作(增删查等),提高了操作效率。

之前阅读了HashMap的源码,但是由于篇幅关系,略过了链表树化后红黑树的相关操作,本着打破砂锅问到底的精神,来看下红黑树在HashMap中的应用。

打破沙锅问到底,是一个成语,拼音为:dǎ pò shā guō wèn dào dǐ,其 比喻追究事情的根底,其出处自 宋·黄庭坚《拙轩颂》。

红黑树

什么是红黑树?

是这样的吗(开个玩笑,不存在的)。

树?

是这样的,这才对吧,有红有黑。

红黑树

科普时间,it KePu's tims.

红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。 它是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees)。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。 红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。 它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。

以上科普信息由度娘提供。

性质

红黑树不仅是二叉查找树,它还必须满足5个性质

  • 1.节点非黑即红
  • 2.根节点是黑色
  • 3.每个叶节点(NIL节点,空节点)是黑色的
  • 4.每个红色节点的两个子节点都是黑色(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  • 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

满足了以上性质的二叉查找树的就是红黑树,如果是初次接触的话,是不是看完有点懵,不要慌,接着往下看。

红黑树的效率相对较高,所以它被用来存储相关数据,基本的操作有增加/删除/查找,在这些操作之后可能会破坏红黑树的性质,所以需要相关操作来维护以让红黑树符合上面的性质要求。

而这里提到的相关操作有

  • 变色
  • 左旋
  • 右旋

左旋右旋

是不是对红黑树的任意操作之后,它都还能满足上面的提交的条件呢。

答案是No。

所以也就有了旋转的存在。

旋转跳跃,我闭着眼,尘嚣看不见 你沉醉了没。(请不要唱,快拉回你的心思)

旋转跳跃

嗯,旋转分为左旋右旋

左旋

将x的右子树绕x逆时针旋转,使得x的右子树成为x的父亲,并修改相关引用。

左旋

右旋

是将x的左子树绕x顺时针旋转,使得x的左子树成为x的父亲,并修改相关的引用。

右旋

是不是还是有点迷糊,那么再来两张动图帮助下理解~

左旋

右旋

懒人自有妙计,不过要有版权意识。 动图来源:https://blog.csdn.net/sun_tttt/article/details/65445754

是不是明白一些了~~

基本的关于红黑树概念介绍完毕,需要深入了解的小伙伴请移步搜索引擎。

接下来,坐好了,将车门焊死,准备发车了。

发车

HashMap中的红黑树

先看下HashMap内部类TreeNode<K,V>的定义,它继承了LinkedHashMap.Entry<K,V>

类java.util.HashMap
第1791行起

/**
 * 二叉树实体. 继承 LinkedHashMap.Entry (顺序扩展节点)
 * 
 * linked node.
 */
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    //红黑树父节点(链)
    TreeNode<K,V> parent;  // red-black tree links
    //左节点
    TreeNode<K,V> left;
    //右节点
    TreeNode<K,V> right;
    //前置节点
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    //红黑标志
    boolean red;
    
    /**
     * 构造函数
     */
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

    /**
     * 返回根节点
     */
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
    
    //先略去部分功能代码
    ...    
}

在看相关的功能代码之前,先来看下HahsMap中红黑树左旋右旋的实现

HashMap中的红黑树 - 左旋

/**
 * 红黑树左旋操作
 */
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                      TreeNode<K,V> p) {
    TreeNode<K,V> r, pp, rl;
    //p不为null且p的右子树不为null
    if (p != null && (r = p.right) != null) {
        //将r(p的右子树)的左子树变成p的右子树
        //有点拗口 o(╥﹏╥)o
        //下面会用一个图示来说明
        if ((rl = p.right = r.left) != null)
            //修改父节点引用,rl是r(p的右子树)的左子树
            rl.parent = p;
        //将r(p的右子树)的父节点变成p的父节点(左旋过程,将右子树变成自己的父节点)
        if ((pp = r.parent = p.parent) == null)
            //如果p节点的父节点为null,证明p是根节点(子树的根节点)
            //将r变成根节点(子树的根节点),并变成黑色(符合性质)
            (root = r).red = false;
        //如果存在父节点且p是该节点的左子树
        else if (pp.left == p)
            //将r(p的右子树)变成该节点的左子树
            pp.left = r;
        //如果存在父节点且p节点是该节点的右子树
        else
            //将r(p的右子树)变成该节点的右子树
            pp.right = r;
        //将r(p的左子树)变成p(左旋中,将左子树变成自己的父节点)
        r.left = p;
        //r变成p的父节点
        p.parent = r;
    }
    return root;
}

下面用图示来说明上面的步骤,会比较简单明了不拗口

一、p没有父节点(可以理解为p是根节点)

左旋演示1

一、p有父节点

左旋演示2

HashMap中的红黑树 - 右旋

/**
 * 红黑树右旋操作
 */
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                       TreeNode<K,V> p) {
    TreeNode<K,V> l, pp, lr;
    //p不为null且p的左子树不为null
    if (p != null && (l = p.left) != null) {
        //将l(p的左子树)的右子树变成p的左子树
        if ((lr = p.left = l.right) != null)
            //修改父节点引用,lr是l(p的左子树)的右子树
            lr.parent = p;
        //将l(p的右子树)的父节点变成p的父节点(右旋过程,将左子树变成自己的父节点)
        if ((pp = l.parent = p.parent) == null)
            //将l变成根节点(子树的根节点),并变成黑色(符合性质)
            (root = l).red = false;
        //如果存在父节点且p是该节点的右子树
        else if (pp.right == p)
            pp.right = l;
        //如果存在父节点且p是该节点的左子树
        else
            pp.left = l;
        //将l(p的右子树)变成p(右旋中,将右子树变成自己的父节点)
        l.right = p;
        p.parent = l;
    }
    return root;
}

类似的下面用图演示过程

一、p没有父节点(可以理解为p是根节点)

右旋演示1

一、p有父节点

右旋演示2

右旋


理解了HashMap中红黑树的左旋和右旋,下面看一下几个比较重要的方法

treeify

顾名思义:树化。当哈希桶中的链表长度超过阈值(默认8)的话,就会对链表进行树化,具体来看一下实现。

调用链如下

1、HashMap第643行treeifyBin(tab, hash);,判断阈值,超过则进行树化

2、HashMap第754行,treeifyBin实现,第771行调用TreeNode的树化实现

/**
 * 替换哈希桶中给定哈希索引的元素
 * 如果哈希桶太小,则resize
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //判断哈希桶
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        //调整扩容
        resize();
    //在哈希桶中获取指定位置的元素
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        //替换成树节点
        do {
            //这里的replacementTreeNode调用了TreeNode的构造函数进行构造
            TreeNode<K,V> p = replacementTreeNode(e, null);
            //维护顺序
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        //修改哈希桶中对应下标的指向为树的头结点
        if ((tab[index] = hd) != null)
            //执行红黑树化
            hd.treeify(tab);
    }
}

3、HashMap第1897行,treeify实现

/**
 * 红黑树化
 * @return 树的根节点
 */
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    //循环整理
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        //取出下一个链表节点
        next = (TreeNode<K,V>)x.next;
        //将x节点的左右节点设置为null
        x.left = x.right = null;
        //判断当前红黑树是否有根节点
        if (root == null) {
            //如果没有根节点
            //当前节点的父节点设置为null
            x.parent = null;
            //设置颜色为黑色(根节点为黑色)
            x.red = false;
            //将x节点设置为根节点
            root = x;
        }
        //当前红黑树存在根节点
        else {
            //获取x节点的key
            K k = x.key;
            //获取x节点的hash
            int h = x.hash;
            //key的class
            Class<?> kc = null;
            //从根节点遍历,将x节点插入到红黑树中
            for (TreeNode<K,V> p = root;;) {
                //定义dir(方向),ph(节点hash)
                int dir, ph;
                //取出p节点的key
                K pk = p.key;
                //当p节点的hash大于x节点的hash时
                if ((ph = p.hash) > h)
                    //左侧
                    dir = -1;
                else if (ph < h)
                    //右侧
                    dir = 1;
                 
                //如果上面的if分支没走,则证明两个节点key的hash值相等,需要通过其他方式进行比较
                //如果当前节点(x)的key的类实现了comparable接口,且当前循环节点(p)是相同Class的实例
                //那么就通过comparable进行比较
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    //若还是相等,就通过tieBreakOrder比较     
                    dir = tieBreakOrder(k, pk);

                //先缓存p节点
                TreeNode<K,V> xp = p;
                //根据dir方向,来选择在左侧还是右侧插入
                //并判断是否为null
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    //选择的左/右子树为null
                    
                    //将原来的p节点(现xp)设置为x的父节点
                    x.parent = xp;
                    //如果dir 小于等于0
                    //将x节点放置在原p(现xp)节点的左侧
                    if (dir <= 0)
                        xp.left = x;
                    //如果dir 大于0
                    //将x节点放置在原p(现xp)节点的右侧
                        xp.right = x;
                    //调用balanceInsertion进行插入平衡
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    //确保哈希桶指定位置存储的节点是红黑树的根节点
    moveRootToFront(tab, root);
}

/**
 * 确保哈希桶指定位置存储的节点是红黑树的根节点
 */
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
    int n;
    if (root != null && tab != null && (n = tab.length) > 0) {
        //索引位置
        int index = (n - 1) & root.hash;
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
        //如果不是红黑树的根节点
        if (root != first) {
            Node<K,V> rn;
            //指向红黑树的根节点
            tab[index] = root;
            TreeNode<K,V> rp = root.prev;
            //整理节点顺序
            if ((rn = root.next) != null)
                ((TreeNode<K,V>)rn).prev = rp;
            if (rp != null)
                rp.next = rn;
            if (first != null)
                first.prev = root;
            root.next = first;
            root.prev = null;
        }
        //递归做一个恒定校验
        assert checkInvariants(root);
    }
}

4、HashMap第2206行,balanceInsertion实现

这个方法实现了红黑树插入节点后的平衡(为了满足平衡性),方法的分支较多,如果没有很透彻理解红黑树的相关概念和操作,一时间会容易迷惑,下面代码对整体流程进行了注释,但是仍然比较晦涩,后面会带上图示,加深理解。

/**
 * 插入平衡
 */
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> x) {
    //将x节点设为红色(新插入节点一开始为红色)
    x.red = true;
    //一个没有边界的循环(需要内部跳出)
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        //取出x的父节点并判断是否为null
        if ((xp = x.parent) == null) {
            //x没有父节点
            x.red = false;//变色(黑色)
            return x;//x为根节点发那会
        }
        //如果x存在父节点且x的父节点为黑色或x的父父节点不存在
        else if (!xp.red || (xpp = xp.parent) == null)
            //返回root
            return root;
        //如果x的父节点是父父节点的左孩子
        if (xp == (xppl = xpp.left)) {
            //父父节点的右孩子不为null且为红色
            if ((xppr = xpp.right) != null && xppr.red) {
                xppr.red = false;//变色(黑)
                xp.red = false;//变色(黑)
                xpp.red = true;//变色(红)
                x = xpp;
            }
            else {
                //x是父节点的右孩子
                if (x == xp.right) {
                    //左旋
                    root = rotateLeft(root, x = xp);
                    //处理x的父父节点
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                //x的父节点存在
                if (xp != null) {
                    xp.red = false;//变色
                    //x的父父节点存在
                    if (xpp != null) {
                        xpp.red = true;//变色
                        //右旋
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        //如果x的父节点是父父节点的右孩子
        else {
            //x的父父节点的左孩子存在且为红色
            if (xppl != null && xppl.red) {
                xppl.red = false;//变色(黑)
                xp.red = false;//变色(黑)
                xpp.red = true;//变色(红)
                x = xpp;
            }
            else {
                //如果x是父节点的左孩子
                if (x == xp.left) {
                    //右旋
                    root = rotateRight(root, x = xp);
                    //处理x的父父节点
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                //如果x的父节点存在
                if (xp != null) {
                    xp.red = false;//变色(黑)
                    //如果x的父父节点存在
                    if (xpp != null) {
                        xpp.red = true;//变色(红)
                        //左旋
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}

下面用图示,举个栗子~

栗子在这里

举个栗子

假如有如下一个链表,里面的数字代表hash值(先不考虑hash分布)

链表

然后按照链表顺序取出节点进行红黑树插入,以及插入后平衡操作(左旋右旋/变色),来看一下整个过程

插入节点过程1

插入节点过程2

综合上面的描述和图示,大概可以把链表转红黑树的操作总结如下

1、将链表的首节点当做临时的红黑树根节点,左右孩子置为null
2、循环按顺序取出链表的节点,进行红黑树插入,和插入后平衡
    2.1、取出链表节点,经过hash比较,插入到红黑树合适的位置(保证平衡性)
    2.2、由于插入的节点会破坏红黑树的性质,所以需要进行插入后平衡
       2.2.1、新插入的节点置为红色
       2.2.2、父节点和父父节点的null判断和颜色判断
           2.2.2.1、判断新插入节点的父节点是否存在,不存在则返回
           2.2.2.1、如果父节点是黑色的,或者父父节点不存在着,则返回
       
       2.2.3、父节点是父父节点的左孩子还是右孩子判断
           2.2.3.1、是左孩子且兄弟节点存在并且是红色,则执行相应的变色,然后进行下一轮判断。
           2.2.3.2、是左孩子当兄弟节点不存在(或者是黑色),则执行相应的左旋/右旋。
           
           2.2.3.3、是右孩子且兄弟节点存在并且是红色,则执行相应的变色,然后进行下一轮判断。
           2.2.3.4、是右孩子当兄弟节点不存在(或者是黑色),则执行相应的左旋/右旋。
3、链表循环完毕后,确保哈希桶指定位置存储的是红黑树的根节点


嗯,没了。细节请看源码和图示,如果觉得迷糊,可以自己动手画画图,或者Debug。

untreeify

有了树化,肯定也有非树化。

有起有落,月缺月圆,凡事要有平衡。一本正经地胡说八道。

举个栗子

突然就斗起了表情。

没错,这个方法就是将红黑树退化成链表,俗称链表化。

入口有几个地方

  • 节点删除时,红黑树的大小低于阈值,退化成链表。2035行tab[index] = first.untreeify(map); // too small
  • 扩容/调整容量时,调用split方法
/**
 * 红黑树链表化
 */
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;
}

putTreeVal

嗯,没什么好说的,红黑树的节点插入。

对应上篇博客的链表节点插入,但相比链表来说会比较复杂。不过流程与之前提到过的树化当中的单一节点插入没有太大区别,也是从红黑树的根节点进行遍历,寻找合适的位置插入,并进行插入后的平衡(变色/左旋/右旋),待插入平衡后,确保存储在哈希桶指定位置的节点是红黑树的根节点。

/**
 * 红黑树版本的节点插入
 */
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                               int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    //取出根节点
    TreeNode<K,V> root = (parent != null) ? root() : this;
    //从根节点进行遍历,选择合适的位置插入节点(无边界遍历,需要内部跳出)
    for (TreeNode<K,V> p = root;;) {
        int dir, ph; K pk;
        //判断方向
        if ((ph = p.hash) > h)
            dir = -1;
        else if (ph < h)
            dir = 1;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            if (!searched) {
                TreeNode<K,V> q, ch;
                searched = true;
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    return q;
            }
            dir = tieBreakOrder(k, pk);
        }
        //先缓存当前遍历的树节点
        TreeNode<K,V> xp = p;
        //判断该树节点下是否有子节点
        //如果没有,则根据之前判断的方向(左侧/右侧)进行插入
        //如果已有,则向下遍历继续上面的步骤,直到插入合适的位置
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            Node<K,V> xpn = xp.next;
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            //插入到合适的位置和,可能破坏红黑树的性质,所以需要进行插入平衡
            //插入平衡后,需要确保哈希桶下标位置上存储的节点是红黑树的节点
            //这些在上面的树化过程都有提到,此处不再赘述
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

getTreeNode

红黑树中的节点查找。

对应链表的节点查找,在链表树化后,节点的查找就是红黑树实现的。查找的逻辑还是比较清晰的,因为红黑树是自平衡二叉查找树,节点左子树都比自己小,右子树都比自己大,所以根据给定的hash,可以确定从左子树还是右子树查找,然后循环进行定位,知道最终找到节点或者不存在该节点时,结束查找。

/**
 * 红黑树节点查找的入口方法
 */
final TreeNode<K,V> getTreeNode(int h, Object k) {
    return ((parent != null) ? root() : this).find(h, k, null);
}

/**
 * 根据给定的hash和key,从红黑树的根节点开始进行查找
 */
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        //取出左子树和右子树,根据hash和key进行查找
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        //根据hash大小决定取左子树还是右子树
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h)
            p = pr;
        //如果在节点相等,就返回
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            p = pl;
    } while (p != null);
    return null;
}

removeTreeNode

移除红黑树节点。

对应链表节点的移除,红黑树版本的节点移除相比链表会复杂一些,因为涉及到维护红黑树的平衡性和相关性质。

/**
 * 移除给定节点, 调用该方法时要确保节点存在.
 * 因为无法交换存在叶子节点的内部节点内容,所以这会比典型的红黑树节点删除来得复杂
 * 遍历过程中"next"指针指向的继任节点是可访问的,所以我们交换了树的连接.
 * 如果当前树节点太少,则将二叉树替换成简单形式
 * (2-6节点测试触发,取决于树的结构)
 */
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                          boolean movable) {
    int n;
    //判断哈希桶
    if (tab == null || (n = tab.length) == 0)
        return;
    //下标
    int index = (n - 1) & hash;
    //取出指定下标的根节点
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
    //继任节点和前置节点
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
    //前置节点不存在,则证明要移除的节点是根节点
    if (pred == null)
        //将继任节点往前移
        tab[index] = first = succ;
    else
        //前置节点存在,则将继任节点连接到前置节点(移除本节点)
        pred.next = succ;
    //判断继任节点是否存在
    if (succ != null)
        //存在的话,修改前置引用
        succ.prev = pred;
    //这个时候first为null,则表示哈希桶指定位置可能只有一个节点
    if (first == null)
        //返回
        return;
    //获取根节点
    if (root.parent != null)
        root = root.root();
    //根节点不存在或者根节点的左子树/右子树不存在或者左左子树不存在
    //该判断是作为链表化的阈值
    if (root == null || root.right == null ||
        (rl = root.left) == null || rl.left == null) {
        //红黑树太小,进行链表化
        tab[index] = first.untreeify(map);  // too small
        return;
    }
    //取得要移除的节点,左子树,右子树
    TreeNode<K,V> p = this, pl = left, pr = right, replacement;
    //左右子树同时存在
    if (pl != null && pr != null) {
        TreeNode<K,V> s = pr, sl;
        //循环查找继任节点
        while ((sl = s.left) != null) // find successor
            s = sl;
        //交换p和s的颜色
        boolean c = s.red; s.red = p.red; p.red = c; // swap colors
        TreeNode<K,V> sr = s.right;
        TreeNode<K,V> pp = p.parent;
        //相等则证明p是s的直接父节点(只有一个层级)
        if (s == pr) { // p was s's direct parent
            //交换位置
            p.parent = s;
            s.right = p;
        }
        //如果是多个层级
        else {
            //取出s的父节点
            TreeNode<K,V> sp = s.parent;
            //下面操作仍然是交换p和s的位置
            if ((p.parent = sp) != null) {
                if (s == sp.left)
                    sp.left = p;
                else
                    sp.right = p;
            }
            if ((s.right = pr) != null)
                pr.parent = s;
        }
        //清空p的右子树引用
        p.left = null;
        //调整相关引用
        if ((p.right = sr) != null)
            sr.parent = p;
        if ((s.left = pl) != null)
            pl.parent = s;
        if ((s.parent = pp) == null)
            root = s;
        else if (p == pp.left)
            pp.left = s;
        else
            pp.right = s;
        //确定替换节点
        if (sr != null)
            replacement = sr;
        else
            replacement = p;
    }
    //只有左子树存在
    else if (pl != null)
        replacement = pl;
    //只有右子树存在
    else if (pr != null)
        replacement = pr;
    //左右子树都不存在
    else
        replacement = p;
    //判断替换的节点是不是自身
    if (replacement != p) {
        //不是自身的话,则执行相关替换操作
        TreeNode<K,V> pp = replacement.parent = p.parent;
        if (pp == null)
            root = replacement;
        else if (p == pp.left)
            pp.left = replacement;
        else
            pp.right = replacement;
        p.left = p.right = p.parent = null;
    }
    //判断p的颜色
    //如果p是红色节点,则将根节点赋值给r
    //如果p是黑色节点,则进行删除平衡(类似于插入平衡)
    //这里的r要存储红黑树的根节点
    TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
    //如果替换节点是自身的话
    if (replacement == p) {  // detach
        //进行分离操作
        TreeNode<K,V> pp = p.parent;
        p.parent = null;
        if (pp != null) {
            if (p == pp.left)
                pp.left = null;
            else if (p == pp.right)
                pp.right = null;
        }
    }
    if (movable)
        //确保哈希桶下标指定位置存储的是红黑树根节点
        moveRootToFront(tab, r);
}

split

只有在resize的时候被调用,作用是在哈希桶扩容/调整容量时,将红黑树拆分成两颗树,在红黑树太小时进行链表化等操作。

具体看源码注释。

/**
 * Splits nodes in a tree bin into lower and upper tree bins,
 * or untreeifies if now too small. Called only from resize;
 * see above discussion about split bits and indices.
 *
 * @param map the map
 * @param tab the table for recording bin heads
 * @param index the index of the table being split
 * @param bit the bit of hash to split on
 */
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引用置空,目的是从e断开
        e.next = null;
        //将e的hash和bit(其实就是oldCap)相与(是不是很熟悉,其实跟链表的操作类似)
        //为0的放到lower树
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        //不为0放到upper树
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }
    //判断lower树是否为null
    if (loHead != null) {
        //判断是否需要链表化
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    //判断upper树是否为null
    if (hiHead != null) {
    //判断是否需要链表化
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

到这里,关于HashMap中的红黑树相关内容基本上都介绍完毕了,篇幅有点长,没法面面俱到,呼~~(放松一下)。

后话

本来想着每个方法和每个操作流程都画图解释比较直观。

但是后面花现,画图,真的是他喵了太耗费精力了。

我花4,除了动图之外,其他的图都是我自己画的。对了,开头的那棵树除外。当然,表情包也不是。

其他图示留待后面时间充裕了补上吧。

溜了溜了,有帮助的话给格子点个赞呗。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java源码阅读之TreeMap(红黑树) - JDK1.8

    TreeMap实现了NavigableMap接口, 而NavigableMap则是通过sortedMap间接继承了Map接口,它定义了一系列导航方法,这些Map...

    格子Lin
  • 这几道Java集合框架面试题在面试中几乎必问

    本文会同步更新在我开源的Java学习指南仓库 Java-Guide (一份涵盖大部分Java程序员所需要掌握的核心知识,正在一步一步慢慢完善,期待您的参与)中,...

    用户2164320
  • HashMap 底层是怎么样的

    JDK1.8 前,HashMap 底层是 数组+链表,也就是 链表散列。 HashMap 通过 key 先计算 hashCode,再经过 扰动函数 处理后得到 ...

    happyJared
  • 这几道Java集合框架面试题在面试中几乎必问

    本文会同步更新在我开源的Java学习指南仓库 Java-Guide (一份涵盖大部分Java程序员所需要掌握的核心知识,正在一步一步慢慢完善,期待您的参与)中,...

    Java知音
  • 这几道Java集合框架面试题在面试中几乎必问

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结...

    Java技术江湖
  • HashMap源码分析(一)(超级详细)

    HashMap基于哈希表的Map接口实现,是以key-value存储形式存在。(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable ...

    乱敲代码
  • HashMap源码分析(一)(超级详细)

    HashMap基于哈希表的Map接口实现,是以key-value存储形式存在。(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable ...

    用户4172423
  • HashMap源码分析(一)(超级详细)

    HashMap基于哈希表的Map接口实现,是以key-value存储形式存在。(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable ...

    码农小胖哥
  • 一文解读JDK8中HashMap的源码

    HashMap是平时开发中非常常用的一个集合框架类,了解其内部构造及运行原理可以说是每一个Java程序员必不可少的,接下来就从源码一探究竟HashMap到底是什...

    beifengtz

扫码关注云+社区

领取腾讯云代金券