HashMap中红黑树插入节点的调整过程 - daheww - JOYK Joy of Geek, Geek News, Link all geek

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

3 years ago

source link: https://www.cnblogs.com/daheww/p/16216250.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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

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

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

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

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

三、阅读HashMap源码的一些Tips

1. 代码风格

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

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

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

把p.parent赋值给r.parent
把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的左子节点节点的右子节点

Recommend

152

monkeysayhi.github.io 7 years ago
Cache

HashMap实现原理 | 程序猿说你好

HashMap是常考点，而一般不问List的几个实现类(偏简单)。以下基于JDK1.8.0_102分析。 JDK版本：oracle java 1.8.0_102 HashMap的内部存储是一个数组（bucket），数组的元素Node实现了是Map.Entry接口(hash, key, value, n...

掘金 juejin.im 7 years ago
Cache

漫画：什么是HashMap？

————————————众所周知，HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。HashMap数组每一个元素的初始值都是Null。

掘金 juejin.im 6 years ago
Cache

HashMap为何从头插入改为尾插入

微信公众号：I am CR7如有问题或建议，请在下方留言;最近更新：2018-09-21 前言      前面对于HashMap在jdk1.8中元素插入的实现原理，进行了详细分析，具体请看：HashMap之元

blog.51cto.com 4 years ago
Cache

kubernetes调整Node节点快速驱逐pod的时间-赵程的技术博客

在使用kubernetes的使用，不知道你有没有遇到或者关注到当你的Node节点挂掉，也就是kubelet无法提供工作的时候，你的pod是否自动的调度到其他的节点上去，而调度到节点上的时间有没有注意大概花了多长时间，我相信如果你仔细关注这件事，你对kubernetes项目也很熟...

blog.51cto.com 2 years ago
Cache

明细表1字符串拼接合并插入到明细表2SQL输出过程记录

需求描述：明细表1：formtable_main_46_dt1字段：id,mainid, bxmx1, jshj, kmbm, fyxm明细表4：formtable_main_46_dt4字段：id,mainid,zy,kmbm,jdbmbm,fyxmbm,yfxmbm,jfjefyxm 为福利费（56）的数据。bx...