您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

看了两天HashMap源码,终于把红黑树插入平衡规则搞懂了

时间:2020-09-27 09:39:45  来源:  作者:

絮叨

学校短学期刚结束了,离学校开学还有很多天,一直呆在寝室玩游戏岂不是浪费了大好时光,于是心血来潮想看看HashMap的源码。虽然我没有经历过面试,但是JAVA程序员都知道,HashMap是面试官必问的知识点,而我现在只停留在对HashMap的基本使用层面,因此我觉得有必要深入了解一下HashMap的底层原理。在HashMap中,我觉得最难的应该是红黑树了吧,我结合代码和画图软件研究了两天,终于总结出规律,现在分享给大家

一、红黑树的特点

下面是红黑树的5条性质,现在大家要对这些性质有印象,后面我会结合图解的形式,多次提到这些性质来帮助大家记忆

  • 每个节点要么是红的,要么是黑色的
  • 跟节点一定是黑色的
  • 叶子节点一定是黑色的(叶节点一般不画,在末尾节点上,没有内容)
  • 红节点下的两个子节点一定是黑色的
  • 任意一条从根节点到叶子节点的路径中黑色节点的个数相等

红黑树插入节点后,若导致红黑树不平衡(整棵树不满足上面5条性质中的任意一条),就会进行变色、旋转操作,直到红黑树平衡,而学习红黑树的难点正是这些变色、旋转的规则

二、红黑树的优点

谈到红黑树的优点,就不得不拿出AVL树来进行比较。

AVL树是完全平衡的树,根的最大深度和最小深度相差不大于1,查找效率比较高,而红黑树不是完全平衡树,查找效率略低于AVL树

红黑树的插入和删除操作比AVL树快很多,因为红黑树保证插入删除时最多需要旋转三次就可以达到平衡,而AVL树每次插入删除会进行大量的平衡度计算,开销很大

因此,红黑树牺牲了一点点查找效率,使它有更快的插入删除操作,综合来说,红黑树性能高于AVL树

三、红黑树插入如何平衡

3.1 红黑树插入基本规则

  1. 新插入的节点是红的
  2. 父节点是黑的,或者父节点是根节点,直接插入
  3. 父节点是红的,需要变色、旋转(也就是出现两个连在一起的红节点失去平衡)
  4. 如果一次平衡后出现祖父节点和祖父节点的父亲是红的,那么把祖父节点当做新节点,继续变色翻转,知道整体平衡(递归思想)

3.2 红黑树变色规则

在基本规则中提到,出现两个连续的红节点需要变色,旋转,所以我们暂且先不管要不要旋转,先来看看红黑树的变色规则是怎么样的吧

3.2.1 新节点没有叔叔节点,或者叔叔节点是黑的

 

看了两天HashMap源码,终于把红黑树插入平衡规则搞懂了

 

这种情况只要把父节点变黑,祖父节点变红就ok了

看了两天HashMap源码,终于把红黑树插入平衡规则搞懂了

 

这种情况不但要把父节点变黑,祖父节点变红,还要考虑祖父节点是否是根节点,在红黑树插入基本规则第二条中写到,根节点一定是黑的,所以如果祖父节点是根节点,需要再次变色把根节点颜色变黑

 

3.2.2 新节点的叔叔节点是红的

看了两天HashMap源码,终于把红黑树插入平衡规则搞懂了

 

这种情况把叔叔节点和父节点颜色变黑,祖父节点变红,变完之后还要考虑祖父节点是否是根节点,根据情况再次变色

3.2.3 小结

  1. 因为新节点是红色的,所以当父节点是红色时,出现了连续的红节点,导致不平衡,要进行变色
  2. 要变色的情况下,叔叔节点和父节点一定要变黑,叔叔节点没有就不考虑它,祖父节点要变红
  3. 祖父节点变红以后,需要考虑它是否是根节点,如果是根节点,根节点要变黑

3.3 红黑树旋转规则

在上一节我们搞明白了红黑树是如何变色的,现在来看看红黑树的旋转规则,在这一环节,变色的过程就不再具体描述了,我只描述红黑树如何旋转

红黑树旋转有四种情况:

  1. 左旋
  2. 右旋
  3. 先左旋,再右旋
  4. 先右旋,再左旋

左旋和右旋其实是差不多的,只是方向换了,如果看完左旋你能想到右旋是如何进行的,那么说明我写的还是很通俗易懂的

3.3.1 左旋

首先有两种情况下会进行左旋操作

  • 新节点、父节点都在右
  • 父节点在左,新节点在右

第二种情况比较复杂,等我写完左旋和右旋操作后,再来考虑这种情况,因为他要涉及到左旋和右旋两步操作

这里先来看一下新节点、父节点都在右的情况下是如何左旋的

图解1

看了两天HashMap源码,终于把红黑树插入平衡规则搞懂了

 

这种情况下左旋的节点都是祖父节点,祖父节往左转成为了父节点左孩子(因为在左边自然而然成为左孩子啦)

图解2

看了两天HashMap源码,终于把红黑树插入平衡规则搞懂了

 

这种情况稍微有点复杂,也是祖父节点往左旋转,成为父节点的左孩子

可是原来父节点是有左孩子的(也就是兄弟节点),那么这个兄弟节点就成了祖父节点的右孩子(可以这么想,祖父节点左旋转后,兄弟节点在右边,因此成了他的右孩子)。

还有一点是原来祖父节点是有父亲的(这里我们叫做祖先节点),如果祖先节点的左孩子是祖父节点,那么旋转后祖先节点的左孩子变成了父节点;如果祖先节点的右孩子是祖父节点,那么旋转后祖先节点的右孩子变成了父节点(可以这么想,父节点移到了祖父节点的位置)

3.3.2 右旋

这里也有两种情况下会进行右旋操作

  • 新节点、父节点都在左
  • 父节点在右,新节点在左

右旋的操作根左旋很相似,只是方向换了一下,我这里就不再详细的解释了,大家看图自己领悟,最好是把左旋看明白,在自己想想对应的情况下右旋应该怎么操作,想到了再和我下面的图对照一下看是否正确

图解1

看了两天HashMap源码,终于把红黑树插入平衡规则搞懂了

 

图解2

看了两天HashMap源码,终于把红黑树插入平衡规则搞懂了

 

3.3.3 先左旋,再右旋

这种情况比较复杂,不多逼逼,直接上图

看了两天HashMap源码,终于把红黑树插入平衡规则搞懂了

 

如何理解?

可以看到,新节点、父节点、祖父节点不在同一条直线上,从图中可以看出这种情况的操作思想是先把这三个节点旋转到一条直线上,再应用我们上面所讲的左旋和右旋,来达到平衡,所以就有两步旋转操作了

第一步旋转

第一步旋转的旋转节点和上面小节的节点不一样,上面小节里旋转的是祖父节点,而这里旋转的是父节点(父节点左旋下来,子节点左旋上去)

第二步旋转

第二步旋转就是上面讲到的右旋,自己慢慢体会

如何记忆?

这里我们怎么看的图就想到先左旋还是先右旋呢,教你一个方法,看父节点在哪边,父节点在左边,左旋,父节点在右边,右旋,这样是不是就很简单了呢

变色过程

之前变色过程都是在第一步做的,但这种情况是在第二步做的,所以我们看到这种图时就要这样想,左旋+变色+右旋,这样就很容易记住了

3.3.4 先右旋,再左旋

这种情况也是和先左旋再右旋差不多的,只是方向变了一下,这里不过多赘述,大家看图慢慢体会

看了两天HashMap源码,终于把红黑树插入平衡规则搞懂了

 

3.3.5 小节

  1. 当祖父节点、父节点、新节点在一条直线上,发生左旋和右旋,父节点和子节点在左,右旋;父节点和子节点在右,左旋
  2. 当祖父节点、父节点、新节点不在一条直线上,先旋转父节点,使它与子节点都在左或都在右,再变色,再旋转。父在左,左旋+变色+右旋,父在右,右旋+变色+左旋

四 红黑树左旋规则详细总结

看了两天HashMap源码,终于把红黑树插入平衡规则搞懂了

 

五 红黑树插入规则详细总结

看了两天HashMap源码,终于把红黑树插入平衡规则搞懂了

 

六、心得体会

HashMap的源码在1.7和1.8两个版本变化很大,建议大家如果看的话先看1.7的源码,再看1.8的源码。说实话,刚开始我1.7的源码都看不懂,后来找了个讲jdk1.7中HashMap源码视频,讲的很不错,看完视频后,再自己看一遍源码,就很有感觉了。之后看1.8源码我没有看过视频,自己就能看懂了

所以说实话,对于红黑树的平衡规则我没有参考其他任何人写的文章,我也尝试看看别人写的关于红黑树的文章,但是我还是觉得这些节点变色旋转过程太复杂,要通过文章看懂并且记住很有难度,所以我选择了看源码自己总结规律

后来把这些过程全部搞懂了,并且也记下了,是通过理解+技巧结合记下的,这个技巧在我这个文章中也要提到,不是死记硬背的

最后一定要像我一样把自己学到的记录下来,方便自己看,也分享给需要的人看,这是一举两得的事情。

七、写给读者的话

接下来,我会总结HashMap红黑树删除时的平衡规则,到时候也会分享出来,希望大家多多关注哦

如何文章中哪里有错误,或者有疑问,大家一定要在评论区写下来,我会及时答复大家和修改错误的,谢谢啦


作者:myboy
链接:https://juejin.im/post/6876350595305996301
来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



Tags:红黑树   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
1. 红黑树1.1 红黑树概述红黑树和我们以前学过的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。不过自从红黑树出来后,AVL...【详细内容】
2021-06-24  Tags: 红黑树  点击:(119)  评论:(0)  加入收藏
前言本文咱们了解一下红黑树的设计,相比 jdk1.7 的 HashMap 而言,jdk1.8 最重要的就是引入了红黑树的设计,当冲突的链表长度超过 8 个的时候,链表结构就会转为红黑树结构。01、...【详细内容】
2021-01-18  Tags: 红黑树  点击:(173)  评论:(0)  加入收藏
絮叨学校短学期刚结束了,离学校开学还有很多天,一直呆在寝室玩游戏岂不是浪费了大好时光,于是心血来潮想看看HashMap的源码。虽然我没有经历过面试,但是java程序员都知道,HashMap...【详细内容】
2020-09-27  Tags: 红黑树  点击:(59)  评论:(0)  加入收藏
本文将通过图文的方式讲解红黑树的知识点,并且不会涉及到任何代码,相信我,在懂得红黑树实现原理前,看代码会一头雾水的,当原理懂了,代码也就按部就班写而已,没任何难度。 阅读本文...【详细内容】
2020-03-18  Tags: 红黑树  点击:(38)  评论:(0)  加入收藏
红黑树是二叉搜索树的增强版,我们知道优化二叉搜索树的核心是优化二叉搜索树的高度,也就是使树尽可能地平衡,红黑树就是解决这个问题的,它能够尽可能地平衡二叉搜索树的高度,保证...【详细内容】
2020-01-03  Tags: 红黑树  点击:(44)  评论:(0)  加入收藏
整篇文章的思路是这样的,红黑树其实就是一种数据结构,设计它的目的就是为了高效地进行增删改查,所以我们文章的顺序也会按照这个思路来进行。我们先从二叉查找树逐渐引入到红黑...【详细内容】
2019-09-23  Tags: 红黑树  点击:(90)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(9)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(19)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(13)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条