HashMap中红黑树插入节点的调整过程

目录

• 一、引言
• 二、HashMap源码中红黑树插入节点的调整过程
• 三、阅读HashMap源码的一些Tips
  • 1. 代码风格
  • 2. 变量名
    • balanceInsertion方法中的变量名
    • rotateLeft、rotateRight方法中的变量名

一、引言

如果有对红黑树的定义及调整过程有过研究，其实很容易理解HashMap中的红黑树插入节点的调整过程。

“红黑树定义及调整过程”的参考文章：《红黑树原理、查找效率、插入及变化规则分析》

下面的流程图就是HashMap源码中，红黑树插入节点的调整过程。这个过程要是写文章讲的话，感觉也没什么意思，其实关键还是需要你要清楚红黑树的定义及调整过程，然后知道数据结构里二叉树左旋、右旋调整的过程。接下来需要做的，就是慢慢啃这段不长的源码。

你看到最后会发现，这个过程中的判断、步骤，都是基于我上面说的：红黑树的定义、红黑树的调整过程、二叉树左旋/右旋调整的过程，然后就是一些指针操作。

二、HashMap源码中红黑树插入节点的调整过程

三、阅读HashMap源码的一些Tips

1. 代码风格

HashMap源码中特别喜欢在判断语句中加赋值语句，形如：if ((xp = x.parent) == null)。它这一行代码做了两件事：

1. 把x.parent赋值给xp
2. 判断xp是否为null

还喜欢使用连等号，形如：pp = r.parent = p.parent。它这一行代码也做了两件事：

1. 把p.parent赋值给r.parent
2. 把r.parent赋值给pp

这种代码风格我看着很不习惯，但是看多了后，也就习惯了。

2. 变量名

源码中的树指针的变量命名其实很有规律：r对应右子树，l对应左子树，p对应父节点，pp对应爷爷节点。
举个例子：变量名pr的含义是，父节点的右子树。

balanceInsertion方法中的变量名

root x所在树的根节点
x    要插入的节点
xp   x的parent节点
xpp  x的parent的parent -> 爷爷节点
xppl x的爷爷节点的左子树
xppr x的爷爷节点的右子树
 
                  +-----+
             +----+     +----+
             |    +-----+    |
             |      xpp      |
          +--v--+         +--v--+
   +------+     |         |     |
   |      +-----+         +-----+
   |        xppl            xppr
+--v--+      xp
|     |
+-----+
   x
 

rotateLeft、rotateRight方法中的变量名

p    旋转的关键点
pp   p的parent节点
r    p的右子节点节点
l    p的左子节点节点
rl   p的右子节点节点的左子节点
lr   p的左子节点节点的右子节点