Java集合源码:(五) HashMap 红黑树(JDK8)

集合整体架构文章:

罗政:JAVA 集合整体架构


本文是接着上篇HashMap原理讲的,文章如下:

罗政:Java集合源码:(四) HashMap 原理(JDK8)


HashMap在hash冲突后会形成链表,然后链表元素超过8时就会转换成红黑树。今天就是要来研究下红黑树的。

红黑树算法

红黑树也叫自平衡二叉查找树或者平衡二叉B树,时间复杂度为O(log n) ,高度h <= log2(n+1)。红黑树是建立在二叉查找树的基础之上的,二叉查找树又是建立在二叉树的基础之上。所以,我们需要从二叉树开始学习红黑树的发展脉络。

二叉树

二叉树(英语:Binary tree)是每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序,不能随意颠倒。

二叉查找树

二叉查找树(英语:Binary Search Tree),也称为二叉搜索树、有序二叉树(ordered binary tree)或排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:

  • 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  • 若任意节点的右子树不空,则右子树上所有节点的值均大于或等于它的根节点的值;
  • 任意节点的左、右子树也分别为二叉查找树;

一颗二叉查找树如下图所示:

但是我们如果插入有序的节点的话,就会变成一只链表

https://pic1.zhimg.com/v2-df4f8da1ce824d580f2dadf80120b11c_b.jpg

虽然二叉查找树退化为线性表之后,最坏效率降为 O(n)。但依旧有很多改进版的二叉查找树可以使树高为O(log n),从而将最坏效率降至O(log n),如AVL树、红黑树等。

AVL树

AVL 树是最早被发明的自平衡二叉查找树。在AVL树中,任一节点对应的两棵子树的最大高度差为 1 ,因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logn)。增加和删除元素的操作则可能需要借由一次或多次树旋转,以实现树的重新平衡。

在 AVL 树中,节点的 平衡因子 是它的左子树的高度减去它的右子树的高度(有时相反)。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的,并需要重新平衡这个树。平衡因子可以直接存储在每个节点中,或从可能存储在节点中的子树高度计算出来。

AVL 树自平衡的方式是做一次或多次所谓的"AVL旋转"。


红黑树

红黑树(英语:Red–black tree)也是一种自平衡二叉查找树。红黑树在二叉查找树的基础之上,对每个节点都增加了颜色属性,分为红色或黑色。在二叉查找树强制的一般要求以外,对于任何有效的红黑树增加了如下 5 条额外要求:

  • 节点是红色或黑色。
  • 根节点是黑色。
  • 所有叶子都是黑色(叶子是NIL节点)。
  • 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  • 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

下面是一个具体的红黑树的图例:


红黑树的这些特性,保证了红黑树 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长 ,造成的结果是红黑树大致上是平衡的。如上图所示,"nil叶子"或"空(null)叶子"不包含数据而只充当树在此结束的指示。

对于红黑树的读与写,因为每一个红黑树都是一个(特殊的)二叉查找树,因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而,在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量 O(log n) 的颜色变更(实际是非常快速的)和不超过三次的树旋转(对于插入操作是两次)。虽然插入和删除很复杂,但操作时间仍可以保持为 O(log n) 次。


HashMap中的红黑树实现


数据结构

 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        // HashMap 链表时Node结构变量
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

       // 红黑树特有的变量
        TreeNode<K,V> parent;  // 指向父亲节点
        TreeNode<K,V> left;   // 左孩子节点
        TreeNode<K,V> right;  // 右孩子节点
        TreeNode<K,V> prev;    // 初始化成链表用
        boolean red;  // 是否是红节点
}

开篇提到的文章里面写到了在下面方法转换成红黑树

    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) {
           // hd 指向链表头   tl指向链表尾部
            TreeNode<K,V> hd = null, tl = null;
           // while循环 是构造了一个链表,每个节点是TreeNode
            do {
                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);         // 转换成红黑树
        }
    }
    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        return new TreeNode<>(p.hash, p.key, p.value, next);
    }

先把原来的Node类型链表转换成TreeNode型链表,然后调用treeify组织成成红黑树结构:

  final void treeify(Node<K,V>[] tab) {
            TreeNode<K,V> root = null;
            for (TreeNode<K,V> x = this, next; x != null; x = next) { //遍历TreeNode链表
                next = (TreeNode<K,V>)x.next;
                x.left = x.right = null;
                if (root == null) {
                   //  构造黑色根节点
                    x.parent = null;
                    x.red = false;
                    root = x;
                }
                // 已经设置了根节点了
                else {
                    K k = x.key;
                    int h = x.hash;
                    Class<?> kc = null;
                    // 从根节点开始遍历 准备插入叶子节点
                    for (TreeNode<K,V> p = root;;) {
                        int dir, ph;
                        K pk = p.key;
                        if ((ph = p.hash) > h) // 父节点的hash值大于当前节点hash
                            dir = -1;  // 应该要插入到节点的左边
                        else if (ph < h)
                            dir = 1; // 应该要插入到节点的右边
                        // 若是新节点与当前节点的hash值相等    
                        else if ((kc == null &&
                                  // 如果新节点的key没有实现Comparable接口..
                                  (kc = comparableClassFor(k)) == null) ||
                                  // 或者实现了Comparable接口但是k.compareTo(pk)结果为0
                                 (dir = compareComparables(kc, k, pk)) == 0)
                            // 比较 System.identityHashCode 大小
                            dir = tieBreakOrder(k, pk);

                        TreeNode<K,V> xp = p;// 父节点
                        //如果是要插入到左边,且左边没有叶子结点则执行插入
                        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;
                        }
                    }
                }
            }
            // 确保给定的根节点是所在桶的第一个节点
            moveRootToFront(tab, root);
        }

根据key的hash值大小来构造成一个二叉树。为了保证hash值不同,则进行:如果hash相同且实现的Comparable比较接口也相同,则 执行System.identityHashCode 。二叉树构造好后,进行平衡操作,即红黑树的左旋和右旋。

红黑树的左旋和右旋

红黑树的左旋和右旋其实很简单,所谓的左旋是把要平衡的节点向左下旋转成一个叶子节点,如下图所示:

所谓的右旋是把要平衡的节点向右下旋转成一个叶子节点。如下图所示:

我们来看下balanceInsertion方法

       static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
            x.red = true;// 父节点是黑色,当前节点置为红色
            /**
             * xp:   x的父节点
             * xpp:  x父节点的父节点
             * xppl: x父节点的父节点左子节点
             * xppr: x父节点的父节点右子节点
             */
            for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
                if ((xp = x.parent) == null) {// 插入的i  是根节点 ,直接是黑色
                    x.red = false; 
                    return x;
                }
               //插入节点的父节点是黑色或者父节点是根节点,红黑树没有被破坏,不需要调整
                else if (!xp.red || (xpp = xp.parent) == null)
                    return root;
                // x的父节点是 左节点时
                if (xp == (xppl = xpp.left)) {
                     // 验证是否需要旋转
                    // xppr = xpp.right 存在右节点 且 右节点为红色
                    if ((xppr = xpp.right) != null && xppr.red) {
                        xppr.red = false; //xppr 设置为 黑色
                        xp.red = false;   // xp 设置为 黑色
                        xpp.red = true;  // xpp 设置为 红色
                        x = xpp;         // 将x赋值为父节点的父节点
                    }
                    else {
                       //当前节点的父节点是红色,且叔叔节点是黑色,当前节点是其父右子节点
                        if (x == xp.right) {
                          // 左旋转
                            root = rotateLeft(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                               //右旋转
                                root = rotateRight(root, xpp);
                            }
                        }
                    }
                }
                else {
               // x的父节点右节点时
                    if (xppl != null && xppl.red) {
                        // 验证是否需要旋转
                        xppl.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        if (x == xp.left) {
                        //右旋转
                            root = rotateRight(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                 // 左旋转
                                root = rotateLeft(root, xpp);
                            }
                        }
                    }
                }
            }
        }

左旋转

static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                      TreeNode<K,V> p) {
    // p: 当前节点
    // r: 当前节点的右儿子
    // rl: 当前节点的右儿子的左儿子
    TreeNode<K,V> r, pp, rl;
    // 如果当前节点和当前节点的右儿子不为空,就左旋
    if (p != null && (r = p.right) != null) {
        // 当前节点的右儿子的左儿子成为当前节点的右儿子
        if ((rl = p.right = r.left) != null)
            rl.parent = p;
        // 当前节点的右儿子成为当前节点的父节点
        if ((pp = r.parent = p.parent) == null)
            // 如果当前节点是根节点,那么r的颜色必须是黑色
            (root = r).red = false;
        else if (pp.left == p)
            pp.left = r;
        else
            pp.right = r;
        r.left = p;
        p.parent = r;
    }
    return root;
}

右旋转

static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                       TreeNode<K,V> p) {
    // p: 当前节点
    // l: 当前节点的左儿子
    // lr: 当前节点的左儿子的右儿子
    TreeNode<K,V> l, pp, lr;
    // 如果当前节点和当前节点的左儿子不为空,就右旋
    if (p != null && (l = p.left) != null) {
        // 步骤①:当前节点的左儿子的右儿子成为当前节点的左儿子
        if ((lr = p.left = l.right) != null)
            lr.parent = p;
        // 步骤②:当前节点的左儿子成为当前节点的父节点
        if ((pp = l.parent = p.parent) == null)
            // 如果当前节点是根节点,那么r的颜色必须是黑色
            (root = l).red = false;
        else if (pp.right == p)
            pp.right = l;
        else
            pp.left = l;
        l.right = p;
        p.parent = l;
    }
    return root;
}

HashMap中的红黑树的查找

        final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
            TreeNode<K,V> p = this;
            do {
                int ph, dir; K pk;
                TreeNode<K,V> pl = p.left, pr = p.right, q;
                if ((ph = p.hash) > h)// 要查到的key的hash小,则从树的左边找
                    p = pl;
                else if (ph < h)
                    p = pr;// 要查到的key的hash小,则从树的右边找
                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;
        }

查找还是很简单,hash值小就在左边找,然后递归遍历树,直到找到相同的hash为止。


强烈推荐一篇 干货,精华 博客:


Java架构师修炼

本文完~

支付宝打赏 微信打赏

如果文章对您有帮助,您可以鼓励一下作者