Skip to main content

源码分析[6] HashMap之红黑树自平衡1

源码hashmap红黑树About 10 min

主要介绍一下红黑树的自平衡实现. hashmap中实现自平衡主要依靠balanceInsertion和 balanceDeletion 分别对应增加和删除时候的情况.
rotateLeft和rotateRight是左旋和右旋操作, 这一篇主要讲balanceInsertion, rotateLeft和rotateRight

balanceInsertion

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) {
    ...............
}

方法的参数有两个一个是根节点, 一个是新插入的节点.

x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
    .................
}

当有一个节点插入的时候这个节点默认是红色的. 因为红色不会导致红黑树路径上黑色节点不一致. 变色相对于改变节点要更容易. 这个我们在红黑树简介的那篇文章中就提到过. 这里不再表述.

节点设置

之后遍历红黑树, 确定新节点应该添加到什么位置上. 具体逻辑见下:

if ((xp = x.parent) == null) {
    x.red = false;
    return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
    return root;
  1. 如果最新的节点的父节点不存在, 则将该节点设置为父节点, 颜色为黑色. 直接返回.
  2. 如果当前节点存在父节点, 并且父节点为黑色或者爷爷节点(姑且就爷爷吧)不存在. 那么直接返回root. 为什么直接返回呢? 因为这种情况下不用调整树的结构, 其本身就是个红黑树. 可以参考下图的这种情况.
    2020-01-18-13-21-46

注意

这里要注意一下, x的父节点在进入这个方法之前会设置上的, 可以参考如下代码片段.

  1. 下面的这段代码是上篇文章我们介绍treeify中的代码, 可以看到是先树化, 这个时候生成的并不是个红黑树, 而只是一个BST树. 之后进行自平衡变成红黑树. 上次讲这个方法可能没提及.

    ..............
for (TreeNode<K,V> p = root;;) {
    int dir, ph;
    K pk = p.key;
    if ((ph = p.hash) > h)
        dir = -1;
    else if (ph < h)
        dir = 1;
    else if ((kc == null &&
                (kc = comparableClassFor(k)) == null) ||
                (dir = compareComparables(kc, k, pk)) == 0)
        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;
    }
}

  2. 还有另一个调用位置putTreeVal方法, 也是我们很久之前就介绍的方法了. 再提一句, 这个地方很明显就维护了链表和红黑树. 同样在调用balanceInsertion之前树也只是一个BST树. 红黑树也是在balanceInsertion之后才生成的. ok?

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

如果你忘了, 可以再看一下上面的两个方法. 继续balanceInsertion的介绍:

继续

排除了父节点为空 和 父节点为黑色或者爷爷节点为空两种情况之后, 下面就是通常情况下的处理.

下面情况出现的前提是父节点非空且父节点为红色且爷爷节点为非空. 这就是在一个红黑树上添加新节点的情形.

if (xp == (xppl = xpp.left)) {
    if ((xppr = xpp.right) != null && xppr.red) {
        xppr.red = false;
        xp.red = false;
        xpp.red = true;
        x = xpp;
    }
    else {
        .........
    }
}
else {
    .............

  1. 爷爷节点的左节点为当前节点的父节点, 即下图这种情况:
    2020-01-18-15-10-30
    这个时候要考虑两种情况:

    • (xppr = xpp.right) != null && xppr.red 当前节点的爷爷节点的右子节点非空, 且为红色. 此时进行的处理为:
      父节点, 叔叔节点变成黑色, 爷爷节点变成红色. 当前节点替换为爷爷节点.
      这种情况即: 在下图中插入节点1:
      2020-01-18-15-21-33
      处理步骤可以见下图:
      2020-01-18-17-33-322020-01-18-17-34-18
      x = xpp;这一步的作用是为了达成迭代. 当下次进入循环若出现:
      2020-01-18-17-50-16
      则红黑树自平衡结束. 我们举得这个例子就达成了退出条件. 即当前节点(x = xpp;执行之后的x)的父节点为空.

    • 当前节点的爷爷节点的右节点为空或者右节点存在但为黑色. 这个时候进行如下处理:

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

      如果当前节点为父节点的右子节点, 则进行左旋, 左旋之后重新设置当前节点的父节点xp变量和爷爷节点xpp变量. 如果当前的父节点为null则, 其爷爷也为null, 否则设置为xp的父节点.
      对父节点不为空我们还要进行处理. 首先父节点不能为红色否则和子节点红色冲突.
      如果爷爷节点不为空我们同样要进行处理, 将爷爷设置为红色, 因为红色不会增加路径上的黑色节点数. 之后进行右旋.

  2. 当xp == (xppl = xpp.left为否时的情形与上面有些类似但是一些左旋右旋操作是相反的. 这里就不再分析了.

为了更好地理解

想必你已经懵逼了, 因为如果我自己看我也会懵逼. 上面的结论都是我对照着程序在在线数据结构模拟过的. 之后给出的分析. 哈哈哈哈~

上一节红黑树的自平衡逻辑可以参考如下流程图, 这个终于是人人皆可看懂的了:
红黑树变换
这里我对当前节点为左父上的情况进行的一些举例. 而且留下了一些空白给愿意进行补充的同志.

图片的链接为: https://tech.nikolazhang.top/红黑树变换.bmpopen in new window
这张图片耗费了我一撮头发. 所以请善待她. 不要辱骂她过于丑陋 😦), 不要怪她太大,加载缓慢(大家不都喜欢高清大图吗? 😃).....
花Q

补充

这里我在说一下图中那个最大的红黑树从一开始到变成图中的形状的过程, 见下图:
2020-01-18-21-22-52
一开始在原来红黑树的基础上添加新节点5, 之后进行变色处理, 也就是走的图中最左边的那个流程逻辑. x=xpp之后当前节点就变为了0030, 顺势就开始了第二次循环. 这时候就是图中的x == xp.right为否的逻辑.

rotateLeft与rotateRight

轻松一下, 看一看rotateLeft与rotateRight这两个方法.

static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                        TreeNode<K,V> p) {
    TreeNode<K,V> r, pp, rl;
    if (p != null && (r = p.right) != null) {
        ..............
    }
    return root;
}

毋庸置疑p传入空我们肯定不用进行处理, 直接返回root就可以了.
我们仔细看下(r = p.right) != null. 要知道左旋之后左子节点是要变到父节点的右子节点上去. 因此如果没有右子节点那么这个树就不再是个平衡二叉树了. 可以参考下图:
2020-01-18-23-07-05

明白了这个条件的含义, 继续分析代码块里面的逻辑:

if ((rl = p.right = r.left) != null)
    rl.parent = p;
if ((pp = r.parent = p.parent) == null)
    (root = r).red = false;
else if (pp.left == p)
    pp.left = r;
else
    pp.right = r;
r.left = p;
p.parent = r;

这时候再把我之前画的那个左旋的图贴上:
2020-01-18-22-16-07

之前这个方法里定义了几个局部变量TreeNode<K,V> r, pp, rl; 对应我们图中的节点 r=R, p=H, rl=RL, pp是H的父节点我们就称其为爷爷节点吧(图中没有画出, 不过你也能想到)

  1. r = p.right 将右子节点提取出来, 设置变量r. 这是在这一节开始的if中进行操作的.
  2. rl = p.right = r.left 将右子节点的左子节点提取作为父节点的右子节点, 并设置变量rl. 这个时候将H和RL联系了起来.
  3. 如果rl存在, 则rl父节点设置为p, 这个时候切换了图中RL和R的关系.
  4. pp = r.parent = p.parent, 原先父节点的父节点设置为其右子节点的父节点, 并设置变量pp. 这个时候将图中的R节点和没画出的那个节点连接了起来. 也就是第三个图中的爷爷节点的子节点指向到R
  5. 如果pp为null, 就说明r节点已经变成了根节点. 这个时候就重新设置根节点(root = r), 并涂黑.
  6. 之后打断pp和p的关系. 并将pp和r的关系建立起来, 虽然我们在第4步已经明确了pp和r的父子关系, 但是究竟是左子还是右子这个关系没有明确, 甚至pp和p还秘密的保持着父子(左子or右子)关系.
  7. 在r和p之间建立左子和父子关系.

至此左旋的整个过程介绍完毕, 总的来说很有味道, 父亲变孙子, 兄弟变孙子.....
我已经笑得不行了.

右旋就不说了.

get

好像还有get这个比较重要的方法没提及, 总不能光知道怎么put, 不知道怎么get吧.

从hashmap中获取键对应的值的方法如下:

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

你可以猜一猜getNode这个方法会是什么样子的.
以下是我的设想:

  1. 首先看一下方法的传入参数, hash(key), key. 我们知道通过hash & (length - 1), 我们可以获取到目标存在于table中的位置.
  2. 有了这个位置就要取出这个节点即: table[hash & (length - 1)]
  3. 之后判断当前节点为链表还是TreeNode, 之后只需要根据不同的类型进行遍历, 通过key进行比较(有可能有涉及到我们之前看到那一堆if), 即可获取到节点.

感觉没什么问题(我可以发誓, 写到这行的时候, 我没有看源码中的getNode方法), 好的, ctrl + left click进入方法:

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

额, 好像没有用那一堆恶心的if, 有点打脸啊. 😦
但是.............
当你进去看到getTreeNode中的find方法的时候是不是很熟悉? 哦, 这该死的if, 这熟悉的味道. (局势逆转 😃 )

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

此时某人已经飘飘然了~~~~

end

下一篇我们介绍一下hashmap节点删除的逻辑, 以及红黑树在删除节点时自平衡的方法.

What do you think?
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
0  Words
Comments
  • Latest
  • Oldest
  • Hottest
Powered by Waline v3.0.0-alpha.10
nikola | 鲁ICP备20000559号-1
Copyright © 2024 我小叮当、