原创

JDK1.8 HashMap源码解析(五) 红黑树的具体实现方式?

[toc]

1、红黑树的特性

什么是红黑树

红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。

红黑树的特点

红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。

  • 特性

    • 性质1: 节点是红色或黑色。
    • 性质2:根节点是黑色。
    • 性质3:每个叶节点(NIL节点或空节点)是黑色的。
    • 性质4:每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
    • 性质5: 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
      注意:
      1、特性(3)中的叶子节点,是只为空(NIL或null)的节点。
      2、特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。
      

    红黑树示意图如下:
    hashmap-红黑树结构.png

2、为什么要引入红黑数(特殊的平衡二叉树)数据结构

在JDK1.7及之前,HashMap的数据结构为:数组 + 链表。数组相当于Array的数据结构, 用来确定key-value对所存储的位置。链表结构的作用是, hash冲突时的数据存储(如果按照hash值,通过hash函数来确认桶位,会存在一个问题,就是hash冲突的问题,也就是不同的key可能会产生不一样的hash值)。

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

由于两个值做异或,最终相同的可能性很大。所以引入了链表来存储hash值一样的key-value.

如果按照链表的方式存储,随着节点的增加数据会越来越多,这会导致查询节点的时间复杂度会逐渐增加,平均时间复杂度O(n)。 为了提高查询效率,故在JDK1.8中引入了改进方法红黑树。此数据结构的平均查询效率为O(long n) 。

引入红黑树HashMap做了哪些改造

当链表节点长度超过8时,将链表转换为二叉树。

参考文章 HashMap 测试「链表转红黑树以及扩容」JDK1.8 HashMap源码解析(三) 扩容机制和resize源码详解

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);
    }

    /**
     * Returns root of tree containing this node.
     */
    /**
     * 获取红黑树的根
     */
    final TreeNode<K, V> root() {
      for (TreeNode<K, V> r = this, p; ; ) {
        if ((p = r.parent) == null) {
          return r;
        }
        r = p;
      }
    }
    ......

3、红黑树的具体实现方式

转换为红黑树大致分为三个步骤。

  • 第一阶段:将链表转化为二叉树
  • 第二阶段:验证是否满足红黑树的五大特征
  • 第三阶段:对二叉树进行旋转操作
    • 旋转的目的是让树保持红黑树的特性。
    • 旋转包括两种:左旋 和 右旋。

第一阶段:将链表转化为二叉树

treeifyBin 方法

final void treeifyBin(Node<K, V>[] tab, int hash) {
    int n, index;
    Node<K, V> e;
    //如果桶数组table为空,或者桶数组table的长度小于MIN_TREEIFY_CAPACITY,不符合转化为红黑树的条件
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
      //扩容
      resize();
    } else
      // 如果符合转化为红黑树的条件,而且hash对应的桶不为null, 则重新计算 hash段位,及table的索引位,第一个节点
      if ((e = tab[index = (n - 1) & hash]) != null) {
           /************ 双向链表 start***************/
          // 红黑树的hd头节点, tl尾节点
          TreeNode<K, V> hd = null, tl = null;
          //遍历链表
          do {
            //替换链表node为树node,建立双向链表
            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);
          /************ 双向链表 end***************/


          // 前面仅仅转换为双向链表,treeify才是转换红黑树的处理方法入口 
          // 让桶的第一个元素指向新建的红黑树头结点,以后这个桶里的元素就是红黑树而不是链表了
          if ((tab[index] = hd) != null) {
            // 将二叉树转换为红黑树
            hd.treeify(tab);
          }
    }
  }

第二阶段:验证是否满足红黑树的五大特征

五大特征

final void treeify(Node<K, V>[] tab) {
      //root节点
      TreeNode<K, V> root = null;
      for (TreeNode<K, V> x = this, next; x != null; x = next) {
        //next 下一个节点
        next = (TreeNode<K, V>) x.next;
        //设置左右节点为空
        x.left = x.right = null;

        // 头回进入循环 root == null,确定头结点,为黑色
        if (root == null) {
          // 将根节点的父节点设置位空
          x.parent = null;
          // 将根节点设置为 black
          x.red = false;
          //将x 设置为根节点
          root = x;

        // 后面进入循环走的逻辑,x 指向树中的某个节点。 此处为非根节点
        } else {
          // 获取当前循环节点key
          K k = x.key;
          // 获取当前节点 hash
          int h = x.hash;
          Class<?> kc = null;

          // 从根节点开始验证,遍历所有节点跟当前节点 x 比较,调整位置,有点像冒泡排序
          for (TreeNode<K, V> p = root; ; ) {
            int dir, ph;
            // 每个节点的 key
            K pk = p.key;

            // 每个节点的hash 与 外层循环的x.hash做比较. 当比较节点的哈希值比 x 大时, dir 为 -1
            if ((ph = p.hash) > h) {
              // <0 ,沿左路径查找
              dir = -1;

            // >0, 沿右路径查找
            } else if (ph < h) {
              dir = 1;

            // 如果存在比较对象,则根据比较对象定义的comparable进行比较
            // 比较之后返回查询节点路径(左或右)
            } else if ((kc == null &&
                (kc = comparableClassFor(k)) == null) ||
                (dir = compareComparables(kc, k, pk)) == 0) {
              dir = tieBreakOrder(k, pk);
            }

            // 如果当前比较节点的哈希值比 x 大,x 就是左孩子,否则 x 是右孩子
            TreeNode<K, V> xp = p;

            // 如果父节点的左节点或右节点为空时,才进行插入操作
            if ((p = (dir <= 0) ? p.left : p.right) == null) {
              // 将px设置为x的父节点
              x.parent = xp;
              if (dir <= 0) {
                xp.left = x;
              } else {
                xp.right = x;
              }

              // 将二叉树转换位红黑树-正式转换红黑树
              root = balanceInsertion(root, x);
              break;
            }
          }
        }
      }
      moveRootToFront(tab, root);
    }

第三阶段:对二叉树进行旋转操作

static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root,
                                                  TreeNode<K, V> x) {
      // 默认x节点为红色节点
      x.red = true;

      /**
       * xp:   x的父节点
       * xpp:  x父节点的父节点
       * xppl: x父节点的父节点左子节点
       * xppr: x父节点的父节点右子节点
       */
      for (TreeNode<K, V> xp, xpp, xppl, xppr; ; ) {
        // xp = x.parent
        // 如果x存在父节点,则说明目前只有一个节点,即root.根据红黑树的五大特征,根节点只能为黑色节点
        if ((xp = x.parent) == null) {
          x.red = false;
          return x;

        //xpp = xp.parent, 直接查询的是根节点
        } else if (!xp.red || (xpp = xp.parent) == null) {
          return root;
        }

        // xppl = xpp.left.  x的父节点是左节点时
        if (xp == (xppl = xpp.left)) {

          // 验证是否需要旋转
          // xppr = xpp.right 存在右节点 且 右节点为红色
          if ((xppr = xpp.right) != null && xppr.red) {
            xppr.red = false;// xppr 设置位black
            xp.red = false;  // xp 设置位black
            xpp.red = true;  // xpp 设置位red

            // 将x赋值为父节点的父节点
            x = xpp;
          } 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 {
          // 验证是否需要旋转
          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);
              }
            }
          }
        }
      }
    }

左旋

对x进行左旋,意味着"将x变成一个左节点"。

hashmap-左旋.jpg

在《算法导论》中,左旋的伪代码的描述如下:

LEFT-ROTATE(T, x)  
 y ← right[x]            // 前提:这里假设x的右孩子为y。下面开始正式操作
 right[x] ← left[y]      // 将 “y的左孩子” 设为 “x的右孩子”,即 将β设为x的右孩子
 p[left[y]] ← x          // 将 “x” 设为 “y的左孩子的父亲”,即 将β的父亲设为x
 p[y] ← p[x]             // 将 “x的父亲” 设为 “y的父亲”
 if p[x] = nil[T]       
 then root[T] ← y                 // 情况1:如果 “x的父亲” 是空节点,则将y设为根节点
 else if x = left[p[x]]  
           then left[p[x]] ← y    // 情况2:如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子”
           else right[p[x]] ← y   // 情况3:(x是它父节点的右孩子) 将y设为“x的父节点的右孩子”
 left[y] ← x             // 将 “x” 设为 “y的左孩子”
 p[x] ← y                // 将 “x的父节点” 设为 “y”

左旋结果如下:
hashmap-左旋-rs.jpg

右旋

对x进行右旋,意味着"将x变成一个右节点"。

hashmap-右旋.jpg

在《算法导论》中,右旋的伪代码的描述如下:

RIGHT-ROTATE(T, y)  
 x ← left[y]             // 前提:这里假设y的左孩子为x。下面开始正式操作
 left[y] ← right[x]      // 将 “x的右孩子” 设为 “y的左孩子”,即 将β设为y的左孩子
 p[right[x]] ← y         // 将 “y” 设为 “x的右孩子的父亲”,即 将β的父亲设为y
 p[x] ← p[y]             // 将 “y的父亲” 设为 “x的父亲”
 if p[y] = nil[T]       
 then root[T] ← x                 // 情况1:如果 “y的父亲” 是空节点,则将x设为根节点
 else if y = right[p[y]]  
           then right[p[y]] ← x   // 情况2:如果 y是它父节点的右孩子,则将x设为“y的父节点的左孩子”
           else left[p[y]] ← x    // 情况3:(y是它父节点的左孩子) 将x设为“y的父节点的左孩子”
 right[x] ← y            // 将 “y” 设为 “x的右孩子”
 p[y] ← x                // 将 “y的父节点” 设为 “x”

hashmap-右旋-rs.jpg

左旋和右旋的区别

无论是左旋还是右旋,被旋转的树,在旋转前是二叉查找树,并且旋转之后仍然是一颗二叉查找树。
hashmap-左旋右旋的区别.jpg

左旋示例图(以x为节点进行左旋):

                               z
   x                          /                  
  / \      --(左旋)-->       x
 y   z                      /
                           y

对x进行左旋,意味着,将“x的右孩子”设为“x的父亲节点”;即,将 x变成了一个左节点(x成了为z的左孩子)!。 因此,左旋中的“左”,意味着“被旋转的节点将变成一个左节点”。

右旋示例图(以x为节点进行右旋):

                               y
   x                            \                 
  / \      --(右旋)-->           x
 y   z                            \
                                   z

对x进行右旋,意味着,将“x的左孩子”设为“x的父亲节点”;即,将 x变成了一个右节点(x成了为y的右孩子)! 因此,右旋中的“右”,意味着“被旋转的节点将变成一个右节点”。

参考文献:

这里click可以动态演示红黑树和AVL树以及其他数据结构和算法,强烈推荐:
RedBlack

explan1.png

AVLtree
explan2.png

最后,附源代码如下:JDK1.8 HashMap源码解析

正文到此结束
广告是为了更好的提供数据服务
本文目录