看了两天HashMap源码，终于把红黑树插入平衡规则搞懂了
絮叨
学校短学期刚结束了，离学校开学还有很多天，一直呆在寝室玩游戏岂不是浪费了大好时光，于是心血来潮想看看HashMap的源码。虽然我没有经历过面试，但是JAVA程序员都知道，HashMap是面试官必问的知识点，而我现在只停留在对HashMap的基本使用层面，因此我觉得有必要深入了解一下HashMap的底层原理。在HashMap中，我觉得最难的应该是红黑树了吧，我结合代码和画图软件研究了两天，终于总结出规律，现在分享给大家
一、红黑树的特点
下面是红黑树的5条性质，现在大家要对这些性质有印象，后面我会结合图解的形式，多次提到这些性质来帮助大家记忆
- 每个节点要么是红的，要么是黑色的
- 跟节点一定是黑色的
- 叶子节点一定是黑色的（叶节点一般不画，在末尾节点上，没有内容）
- 红节点下的两个子节点一定是黑色的
- 任意一条从根节点到叶子节点的路径中黑色节点的个数相等
红黑树插入节点后，若导致红黑树不平衡（整棵树不满足上面5条性质中的任意一条），就会进行变色、旋转操作，直到红黑树平衡，而学习红黑树的难点正是这些变色、旋转的规则
二、红黑树的优点
谈到红黑树的优点，就不得不拿出AVL树来进行比较。
AVL树是完全平衡的树，根的最大深度和最小深度相差不大于1，查找效率比较高，而红黑树不是完全平衡树，查找效率略低于AVL树
红黑树的插入和删除操作比AVL树快很多，因为红黑树保证插入删除时最多需要旋转三次就可以达到平衡，而AVL树每次插入删除会进行大量的平衡度计算，开销很大
因此，红黑树牺牲了一点点查找效率，使它有更快的插入删除操作，综合来说，红黑树性能高于AVL树
三、红黑树插入如何平衡
3.1 红黑树插入基本规则
- 新插入的节点是红的
- 父节点是黑的，或者父节点是根节点，直接插入
- 父节点是红的，需要变色、旋转（也就是出现两个连在一起的红节点失去平衡）
- 如果一次平衡后出现祖父节点和祖父节点的父亲是红的，那么把祖父节点当做新节点，继续变色翻转，知道整体平衡（递归思想）
3.2 红黑树变色规则
在基本规则中提到，出现两个连续的红节点需要变色，旋转，所以我们暂且先不管要不要旋转，先来看看红黑树的变色规则是怎么样的吧
3.2.1 新节点没有叔叔节点，或者叔叔节点是黑的
这种情况只要把父节点变黑，祖父节点变红就ok了
这种情况不但要把父节点变黑，祖父节点变红，还要考虑祖父节点是否是根节点，在红黑树插入基本规则第二条中写到，根节点一定是黑的，所以如果祖父节点是根节点，需要再次变色把根节点颜色变黑
3.2.2 新节点的叔叔节点是红的
这种情况把叔叔节点和父节点颜色变黑，祖父节点变红，变完之后还要考虑祖父节点是否是根节点，根据情况再次变色
3.2.3 小结
- 因为新节点是红色的，所以当父节点是红色时，出现了连续的红节点，导致不平衡，要进行变色
- 要变色的情况下，叔叔节点和父节点一定要变黑，叔叔节点没有就不考虑它，祖父节点要变红
- 祖父节点变红以后，需要考虑它是否是根节点，如果是根节点，根节点要变黑
3.3 红黑树旋转规则
在上一节我们搞明白了红黑树是如何变色的，现在来看看红黑树的旋转规则，在这一环节，变色的过程就不再具体描述了，我只描述红黑树如何旋转
红黑树旋转有四种情况：
- 左旋
- 右旋
- 先左旋，再右旋
- 先右旋，再左旋
左旋和右旋其实是差不多的，只是方向换了，如果看完左旋你能想到右旋是如何进行的，那么说明我写的还是很通俗易懂的
3.3.1 左旋
首先有两种情况下会进行左旋操作
- 新节点、父节点都在右
- 父节点在左，新节点在右
第二种情况比较复杂，等我写完左旋和右旋操作后，再来考虑这种情况，因为他要涉及到左旋和右旋两步操作
这里先来看一下新节点、父节点都在右的情况下是如何左旋的
图解1
这种情况下左旋的节点都是祖父节点，祖父节往左转成为了父节点左孩子（因为在左边自然而然成为左孩子啦）
图解2
这种情况稍微有点复杂，也是祖父节点往左旋转，成为父节点的左孩子
可是原来父节点是有左孩子的（也就是兄弟节点），那么这个兄弟节点就成了祖父节点的右孩子（可以这么想，祖父节点左旋转后，兄弟节点在右边，因此成了他的右孩子）。
还有一点是原来祖父节点是有父亲的（这里我们叫做祖先节点），如果祖先节点的左孩子是祖父节点，那么旋转后祖先节点的左孩子变成了父节点；如果祖先节点的右孩子是祖父节点，那么旋转后祖先节点的右孩子变成了父节点（可以这么想，父节点移到了祖父节点的位置）
3.3.2 右旋
这里也有两种情况下会进行右旋操作
- 新节点、父节点都在左
- 父节点在右，新节点在左
右旋的操作根左旋很相似，只是方向换了一下，我这里就不再详细的解释了，大家看图自己领悟，最好是把左旋看明白，在自己想想对应的情况下右旋应该怎么操作，想到了再和我下面的图对照一下看是否正确
图解1
图解2
3.3.3 先左旋，再右旋
这种情况比较复杂，不多逼逼，直接上图
如何理解？
可以看到，新节点、父节点、祖父节点不在同一条直线上，从图中可以看出这种情况的操作思想是先把这三个节点旋转到一条直线上，再应用我们上面所讲的左旋和右旋，来达到平衡，所以就有两步旋转操作了
第一步旋转
第一步旋转的旋转节点和上面小节的节点不一样，上面小节里旋转的是祖父节点，而这里旋转的是父节点（父节点左旋下来，子节点左旋上去）
第二步旋转
第二步旋转就是上面讲到的右旋，自己慢慢体会
如何记忆？
这里我们怎么看的图就想到先左旋还是先右旋呢，教你一个方法，看父节点在哪边，父节点在左边，左旋，父节点在右边，右旋，这样是不是就很简单了呢
变色过程
之前变色过程都是在第一步做的，但这种情况是在第二步做的，所以我们看到这种图时就要这样想，左旋+变色+右旋，这样就很容易记住了
3.3.4 先右旋，再左旋
这种情况也是和先左旋再右旋差不多的，只是方向变了一下，这里不过多赘述，大家看图慢慢体会
3.3.5 小节
- 当祖父节点、父节点、新节点在一条直线上，发生左旋和右旋，父节点和子节点在左，右旋；父节点和子节点在右，左旋
- 当祖父节点、父节点、新节点不在一条直线上，先旋转父节点，使它与子节点都在左或都在右，再变色，再旋转。父在左，左旋+变色+右旋，父在右，右旋+变色+左旋
四 红黑树左旋规则详细总结
五 红黑树插入规则详细总结
六、心得体会
HashMap的源码在1.7和1.8两个版本变化很大，建议大家如果看的话先看1.7的源码，再看1.8的源码。说实话，刚开始我1.7的源码都看不懂，后来找了个讲jdk1.7中HashMap源码视频，讲的很不错，看完视频后，再自己看一遍源码，就很有感觉了。之后看1.8源码我没有看过视频，自己就能看懂了
所以说实话，对于红黑树的平衡规则我没有参考其他任何人写的文章，我也尝试看看别人写的关于红黑树的文章，但是我还是觉得这些节点变色旋转过程太复杂，要通过文章看懂并且记住很有难度，所以我选择了看源码自己总结规律
后来把这些过程全部搞懂了，并且也记下了，是通过理解+技巧结合记下的，这个技巧在我这个文章中也要提到，不是死记硬背的
最后一定要像我一样把自己学到的记录下来，方便自己看，也分享给需要的人看，这是一举两得的事情。
七、写给读者的话
接下来，我会总结HashMap红黑树删除时的平衡规则，到时候也会分享出来，希望大家多多关注哦
如何文章中哪里有错误，或者有疑问，大家一定要在评论区写下来，我会及时答复大家和修改错误的，谢谢啦
作者：myboy
链接：https://juejin.im/post/6876350595305996301
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
