HashMap(红黑树篇)（hashmap红黑树作用）

本篇文章只分析红黑树的那块，其他部分请看本人的另一篇文章。

TreeNodeUML图：

可以看到，TreeNode是Node的子类，所以TreeNode也拥有Node的next属性，记住这个，下面会讲到。

treeify(Node<K,V>[] tab)：

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    //this是头节点，从头开始遍历
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        //取当前节点的next
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        //判断根节点是否为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;;) {
                //dir是1代表插到右边，是-1代表插到左边
                //ph是当前节点的哈希值，这里的红黑树是以哈希值进行排序的。
                int dir, ph;
                K pk = p.key;
                //p是当前节点，h是要插入的节点的hash，判断p的hash是否大于当前节点的hash
                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;
                //根据dir判断左右，如果是null就可以插入，不为null就从当前节点的左边或者右边重新遍历
                //其实就是一个递归，不停的往左或者右遍历
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    //x是要插入的节点，xp是for里面的当前节点，把x.parent指向xp，插在xp的左或者右
                    x.parent = xp;
                    //根据dir判断把节点插到左还是右
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    //插入的修正
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    //把根节点挪到链表的头节点
    moveRootToFront(tab, root);
}

看上去一堆代码，其实不复杂，插入节点这一步可以看成一个简单的二叉树，小于就往左边插，大于就往右边插：

不过二叉树的缺点太明显了，某种情况下，会变成上图所示，活脱脱的就是一个链表。HashMap当前不会这么笨，HashMap用的红黑树，每次插入都会修正的。

真正讲修正之前，必须要先说清楚2个概念，左旋和右旋。

• 左旋：孩子节点S把父节点E替掉，E变成S的左节点，S的左节点变成E的右节点。左旋的顶端节点必须要有右子节点，也就是必须要有S节点。

看下红黑树里面的左旋，代码整合：

static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                      TreeNode<K,V> p) {
    //p相当于上面的E节点
    //r是S的右子节点，就是S节点，必须要有，因为左旋的顶端节点必须要有右子节点
    //pp是p的父节点，E的父亲，没有说明S就是根节点
    //rl相当于E的左子节点
    TreeNode<K,V> r, pp, rl;
    //左旋的顶端节点必须要有右子节点
    if (p != null && (r = p.right) != null) {
        //把l的left赋给p的right，想当于S的左子节点赋给E的右子节点
        if ((rl = p.right = r.left) != null)
            //不为null再把rl的parent指向p，这样就彻底替换成功
            rl.parent = p;
        //判断p.parent是否为null，相当于判断E是不是根节点
        if ((pp = r.parent = p.parent) == null)
            //为null说明S是根节点，把S变成新的根节点，且涂黑
            (root = r).red = false;
            //判断E在不在左边
        else if (pp.left == p)
            //在左边，就把pp的left指向r，相当于S把E顶掉了。
            pp.left = r;
        else
            //在右边，就把pp的right指向r，相当于S把E顶掉了。
            pp.right = r;
        //把r的left指向p，相当于E变成S的右节点
        r.left = p;
        //再把p的parent指向r，这个父子关系就成了
        p.parent = r;
    }
    return root;
}

一堆代码，仔细一看就是上面动图的步骤：

1：判断左旋的顶端节点必须要有右子节点

2：S有左节点就赋给E的right

3：然后S把E的位置顶掉。

下面看几个示意图：

S(4)有左子节点，p(2)是根节点的完整示意图：

S(2)没有左子节点，p(1)不是根节点，E(1)在整体的左边的完整示意图：

S(4)没有左子节点，p(3)不是根节点，E(3)在整体的右边的完整示意图：

其实右旋跟左旋意思差不多，左旋理解了，右旋就是反一下，这里在简单描述一下，不写那么详细了。还是先上代码：

static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                       TreeNode<K,V> p) {
    //p相当于上面的S节点
    //l是S的左子节点，就是E节点，必须要有，因为右旋的顶端节点必须要有左子节点
    //pp是p的父节点，S的父亲，没有说明S就是根节点
    //lr相当于E的右子节点
    TreeNode<K,V> l, pp, lr;
    //右旋的顶端节点必须要有左子节点
    if (p != null && (l = p.left) != null) {
        //把l的right赋给p的left，想当于E的右子节点赋给S的左子节点
        if ((lr = p.left = l.right) != null)
            //不为null再把lr的parent指向p，这样就彻底替换成功
            lr.parent = p;
        //判断p.parent是否为null，相当于判断S是不是根节点
        if ((pp = l.parent = p.parent) == null)
            //为null说明S是根节点，把E变成新的根节点，且涂黑
            (root = l).red = false;
            //判断S在不在右边
        else if (pp.right == p)
            //在右边，就把pp的right指向l，相当于E把S顶掉了。
            pp.right = l;
        else
            //在左边，就把pp的left指向l，相当于E把S顶掉了。
            pp.left = l;
        //把l的right指向p，相当于S变成E的右节点
        l.right = p;
        //p的parent指向l，父子关系成了
        p.parent = l;
    }
    return root;
}

大概注释都有了，这里就不行详细拆分看了，直接看几个完整的示意图吧。

E(2)没有右子节点，p(3)不是根节点，E在整体的右边的完整示意图：

E(4)有右子节点，p(6)是根节点的完整示意图：

建议大家自己动手画几幅图，基本上就能理解了，现在我们回到插入的修正。

插入的修正，balanceInsertion()，拆开说：

1：修正成功的两种情况：

//默认是插入的节点是红色的，所以先涂成红色
x.red = true;
//xp是新插入的节点的父节点，xpp是祖父节点
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
    //判断下插入的节点的parent是否为null，相当于判断是不是根节点
    if ((xp = x.parent) == null) {
        x.red = false;
        return x;
  }
  //如果父节点是黑色的，或者父节点是根节点，不需要修正，完美插入
  else if (!xp.red || (xpp = xp.parent) == null)
      return root;

不停的循环，直至满足条件：当前是根节点、父节点是黑色的、或者父节点是根节点才跳出循环。

2：如果父节点在左边：

//判断新插入节点的父节点是否等于祖父节点的左节点，判断是不是在树的左边
if (xp == (xppl = xpp.left)) {

• 父节点在左边，右叔父节点不为null，且是红色：

//在左边，并且右叔父节点不为null，且是红色
if ((xppr = xpp.right) != null && xppr.red) {
    //把祖父节点的右节点涂黑
    xppr.red = false;
    //把父节点涂黑
    xp.red = false;
    //把祖父节点涂红
    xpp.red = true;
    //把祖父节点赋给x，继续往上追溯修正
    //因为要判断此时的xpp的父节点是不是红的，或者xpp是root呢？
    x = xpp;
}

父节点在左边，右叔父节点不为null，且是红色的示意图：

涂完之后，用祖父节点2重新循环，因为此时的祖父2是红色的。

• 父节点在左边，右叔父节点为null：

else {
  //右叔父节点为null，自己在右边
  if (x == xp.right) {
      //在右边，左旋
      root = rotateLeft(root, x = xp);
      //左旋之后父节点不为null，就把新的祖父节点重新赋给xpp
      xpp = (xp = x.parent) == null ? null : xp.parent;
  }
  //判断父节点不为null
  if (xp != null) {
      //父节点涂黑
      xp.red = false;
      //判断是否有祖父节点
      if (xpp != null) {
          //祖父节点涂黑
          xpp.red = true;
          //右旋
          root = rotateRight(root, xpp);
    }
  }
}

父节点在左边，右叔父节点为null，插入的节点在左边的示意图：

右旋的图大家可以自己画一下，就是2上去，3下来。

3：父节点在右边：

else {
    //插入的父节点在右边，判断左叔父节点是否为null，是否是红色
    if (xppl != null && xppl.red) {
        //左叔父节点涂黑
        xppl.red = false;
        //父节点涂黑
        xp.red = false;
        //祖父节点涂红
        xpp.red = true;
        //把祖父节点赋给x，继续往上追溯修正
        //因为要判断此时的xpp的父节点是不是红的，或者xpp是root呢？
        x = xpp;
  }

父节点在右边，左叔父节点不为null，且是红色示意图：

• 父节点在右边，左叔父节点为null：

else {
    //左叔父节点为null，自己在左边
    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);
      }
    }
}

父节点在右边，左叔父节点为null，自己在左边示意图：

左旋之后大家可以自己画。

moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root)：

static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                       TreeNode<K,V> p) {
    //p相当于上面的S节点
    //l是S的左子节点，就是E节点，必须要有，因为右旋的顶端节点必须要有左子节点
    //pp是p的父节点，S的父亲，没有说明S就是根节点
    //lr相当于E的右子节点
    TreeNode<K,V> l, pp, lr;
    //右旋的顶端节点必须要有左子节点
    if (p != null && (l = p.left) != null) {
        //把l的right赋给p的left，想当于E的右子节点赋给S的左子节点
        if ((lr = p.left = l.right) != null)
            //不为null再把lr的parent指向p，这样就彻底替换成功
            lr.parent = p;
        //判断p.parent是否为null，相当于判断S是不是根节点
        if ((pp = l.parent = p.parent) == null)
            //为null说明S是根节点，把E变成新的根节点，且涂黑
            (root = l).red = false;
            //判断S在不在右边
        else if (pp.right == p)
            //在右边，就把pp的right指向l，相当于E把S顶掉了。
            pp.right = l;
        else
            //在左边，就把pp的left指向l，相当于E把S顶掉了。
            pp.left = l;
        //把l的right指向p，相当于S变成E的右节点
        l.right = p;
        //p的parent指向l，父子关系成了
        p.parent = l;
    }
    return root;
}

其实很简单，相当于链表的删除，把root删掉，挪到链表的头部，链表的删除另一篇文章有详细示意图。

putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v)：

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;
    //跟上面的treeify几乎一样，除了这里。
    //因为treeify是链表转红黑树，已经是链表了。
    //这是红黑树的新增，所以加了next和prev，额外维护了一个双向链表。
    xp.next = x;
    x.parent = x.prev = xp;
    if (xpn != null)
        ((TreeNode<K,V>)xpn).prev = x;
         moveRootToFront(tab, balanceInsertion(root, x));
    return null;
}

跟上面的treeify几乎一样，除了上面注释的那2行。比treeify多维护了一个双向链表，而treeify已经是双向链表了。可以看得出，HashMap真的占空间，next、parent、left、right、prev，为了新增、删除、遍历的平衡，不容易。

treeifyBin(Node<K,V>[] tab, int hash)：

   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)
            //小于MIN_TREEIFY_CAPACITY优先进行扩容而不是树化
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                //把节点改成树结构的节点，由Node变成TreeNode
                TreeNode<K,V> p = replacementTreeNode(e, null);
                //判断tl是否为null，相当于判断是不是第一次进循环，取头结点
                if (tl == null)
                    //是第一次就把p赋给hd
                    hd = p;
                else {
                    //把p的prev指向tl，此时的p是当前节点，最后的tl = p是最后一步，此时还是上个节点。
                    p.prev = tl;
                    //把tl的next指向p，此时的tl是上个节点，
                  	//当前节点的prev指向上个节点，上个节点的next指向当前节点，组成了一个双向的链表
                    tl.next = p;
                }
                //每次记住当前节点
                tl = p;
                //刚开始的e其实是此下标的第一个节点，这里相当于从头开始遍历
            } while ((e = e.next) != null);
            //再说一下，此时还是链表，双向的，只不过每个节点从Node变成了TreeNode
            if ((tab[index] = hd) != null)
                //真正开始转树结构
                hd.treeify(tab);
        }
    }

很简单，把Node变成TreeNode，并且TreeNode还补上了next跟prev，相当于一个双向链表，图就不画了，另一篇文章的复制节点那里画过了。

getTreeNode(int h, Object k)：

final TreeNode<K,V> getTreeNode(int h, Object k) {
  	return ((parent != null) ? root() : this).find(h, k, null);
}
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    //h是要找的hash
    //p是每次遍历的节点
    //ph是遍历的节点的hash
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        //取遍历的节点的左右
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        //判断当前节点的hash是否大于要找的hash
        if ((ph = p.hash) > h)
            //大于就把左节点赋给p重新循环
            p = pl;
        else if (ph < h)
            //小于就把右节点赋给p重新循环
            p = pr;
        //不是大于也不是小于，就判断key是否相等或者hash是否相等相等
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            //相等就返回，找到了
            return p;
        else if (pl == null)
            //左边的为null就把右节点赋给p重新循环
            p = pr;
        else if (pr == null)
            //右边的为null就把左节点赋给p重新循环
            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(HashMap<K,V> map, Node<K,V>[] tab, boolean movable)：

分两步：

第一步：先删除链表：

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;
    //取当前节点的next，prev
    //此时是TreeNode调的removeTreeNode方法
    //removeTreeNode继承于Node，所以可以直接调next
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
                          //判断前驱是否为null
                          if (pred == null)
    //为null说明是头节点，就把后驱赋给first
    tab[index] = first = succ;
    else
        //把前驱的next指向后驱
        pred.next = succ;
    //判断后驱是否不为null
    if (succ != null)
        //不为null说明不是最后一个，就把后驱的前驱指向删除节点的前驱，相当于跳过了要删除的节点
        succ.prev = pred;
    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;
}

链表的删除比较简单，图在另一篇文章也画过了。

第二步：红黑树的删除：

删除也可以大概分成两种情况（下面以字母p代替需要删除的节点，以replacement代替真正被删掉的节点，代码里也是这2个字母）：

• 第一种：replacement就是p本身，有两种可能，此时是先修正后删除：

可能1：p没有子节点，示意图：

p没有子节点，代码整合：

else
    //左右都为null，被删除的节点就是自己
    replacement = p;

这个时候是最简单的，p就是自己，先修正颜色，后删除。（修正balanceDeletion后面说）

可能2：p有左右子节点，p的右子节点的最下面一层有左节点，示意图：

p有左右子节点，p的右子节点的最下面一层有左节点，代码整合：

if (pl != null && pr != null) {
    //s就是p的右子节点的最小的值
    TreeNode<K,V> s = pr, sl;
    while ((sl = s.left) != null)
        //一直找到最下面的左子节点，就是最小值，把sl赋给s
        s = sl;
    //把s和p的颜色互换
    boolean c = s.red; s.red = p.red; p.red = c; 
    TreeNode<K,V> sr = s.right;
    TreeNode<K,V> pp = p.parent;
    if (s == pr) {
          //如果没有孙子节点，把p挪到s的位置
          p.parent = s;
          s.right = p;
      }
    else {
        TreeNode<K,V> sp = s.parent;
        if ((p.parent = sp) != null) {
            //s是最下面的左节点，sp是parent
            if (s == sp.left)
                //把p挪下来，挪到s的位置
                sp.left = p;
            else
                //按1.8的源码这里是永远走不到的
                //如果上面的s取的左子节点最下面的右节点就会进这里
                //可能别的版本改了，这里为了兼容
                sp.right = p;
        }
        if ((s.right = pr) != null)
            //把s挪上去，挪到p的位置
            pr.parent = s;
      }
  		p.left = null;
      if ((p.right = sr) != null)
        	//sr是s的right，不为null代表最后一层只有右节点
        	//最小值s在倒数第二层
        	//把sr赋给p的right，因为p会换到s的位置
          sr.parent = p;
      if ((s.left = pl) != null)
          //原来的left赋给挪上去的s
          pl.parent = s;
      if ((s.parent = pp) == null)
          //删除的节点的父亲是根节点，就把root指向s
          root = s;
      else if (p == pp.left)
          //把原来父亲的left指向挪上去的s，这样就完全替换掉了。
          pp.left = s;
      else
          //把原来父亲的right指向挪上去的s
          pp.right = s;
      if (sr != null)
        	//把最下面一层的右节点赋给replacement
          replacement = sr;
      else
          replacement = p;

一堆代码，总结一下步骤：

1：找到p的右边的最小值s，把p和s的颜色互换，位置互换。

2：s如果有右子节点，就把p的right指向这个右子节点，因为p挪到s的位置了。

3：把p以前的left赋给s，因为s挪到p位置了。

4：再把s指向p以前的parent，p是左边就是left指向s，是右边就是left指向s。要是parent是根节点，就把s赋给根节点。

总结起来就是一句话：要删除的节点和右边最小值（左边最大值也行）颜色互换，位置互换。

因为右边最大值和要删除节点互换位置，必定大于左边，小于右边的，不影响二叉查找树的性质。而要删除的节点最后会删除的，所以可以忽略。

p有左右子节点，p的右子节点的最下面一层有左节点的完整示意图：

可能一和二：p只有左子节点或者右子节点，示意图：

p只有左子节点或者右子节点，代码整合：

//默认是插入的节点是红色的，所以先涂成红色
x.red = true;
//xp是新插入的节点的父节点，xpp是祖父节点

for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
    //判断下插入的节点的parent是否为null，相当于判断是不是根节点
    if ((xp = x.parent) == null) {
        x.red = false;
        return x;
  }
  //如果父节点是黑色的，或者父节点是根节点，不需要修正，完美插入
  else if (!xp.red || (xpp = xp.parent) == null)
      return root;

可能三：p有左右子节点，p的右子节点的最后的左节点下面还有且仅有一个右节点，示意图：

p有左右子节点，p的右子节点的最后的左节点下面还有且仅有一个右节点，代码整合：

代码上面已经贴过了，步骤是一样的，下面贴个完整示意图：

看完了各种情况，就做了一件事：要删除的节点和右边最小值（左边最大值也行）颜色互换，位置互换。

换完了之后，两种可能，一个是要删除的节点在最后一层，此时就先修正后删除，一个要删除的节点不在最后一层，此时就先删除后修正。

节点换完位置以后，其实都一样的了。

在最后一层的示意图：

不在最后一层的示意图：

一模一样，就这2种情况，看下删除的代码：

//判断新插入节点的父节点是否等于祖父节点的左节点，判断是不是在树的左边
if (xp == (xppl = xpp.left)) {

就是把要删除的节点替掉，没啥好说的，看下示意图：

接着看修正：balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x)：

//p是红的就不需要修正
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);

这时候的p已经是跟右边最小值s互换颜色了，不管先删还是后删，实际删除的都是s。而删掉的s是红色的话，是不影响黑高的，只有黑的才会。

删除很复杂，讲代码太绕，我这里只分析一下最复杂的情况，保证看得懂。而且可以跟HashMap的源码不一样的方法，因为修正不是固定的，只要修正之后满足规则就行。

只能说HashMap的源码是满足所有情况的，并且综合来讲肯定是修正的步骤最少的，性能最高的。这是大佬的心血，我们直接抄过来就行，但是抄之前得先理解。

最复杂的情况：

我们不看代码，就看上面这个情况，要删除9该怎么办?

此时的9肯定自己这一边的最后一层，因为如果9还有右子节点，会先删除的，保证9在最后一层。

而9的兄弟节点14有值，且是红色，说明14的左右子节点有且必须是黑色，至于在下面的红的不管。

9马上会被删除，所以必须想办法从14那边挪一个过来，但是14那边全是大于9的父亲11，不能挪，怎么遍？左旋呗，把9的父亲变大点。好，我们先左旋：

这个时候，二叉平衡树的特性是满足的，但是不满足红黑树的规则，所以我们需要继续修正，可以继续左旋：

这个时候，一通乱涂：

这样也算修正成功了，下面看下红黑树的修正步骤：

其实跟我们自己瞎想的也差不多，所以具体怎么修正的代码我们可以不理解，但是意思一定要知道，是为了满足规则。为什么满足规则？因为这样的规则也是大佬的心血，遵循就行，但是要先理解意思。

好了，删除就不细说代码，大家可以去看，主要是代码太难懂了（我也不会......），直接搬过来用吧。

终于结束了，写了好久好久，写不下去了，水平还是不够啊。