手记

Java源码阅读之红黑树在HashMap中的应用 - JDK1.8

前言

基于JDK1.8

JDK1.8之前,HashMap并没有采用红黑树,所以哈希桶上的链表过长时,就会有效率问题。

JDK1.8,则在HashMap引入了红黑树,当链表长度超过指定阈值(默认为8),则进行树化并提供相关操作(增删查等),提高了操作效率。

之前阅读了HashMap的源码,但是由于篇幅关系,略过了链表树化后红黑树的相关操作,本着打破砂锅问到底的精神,来看下红黑树在HashMap中的应用。

打破沙锅问到底,是一个成语,拼音为:dǎ pò shā guō wèn dào dǐ,其 比喻追究事情的根底,其出处自 宋·黄庭坚《拙轩颂》。

红黑树

什么是红黑树?

是这样的吗(开个玩笑,不存在的)。

树?

是这样的,这才对吧,有红有黑。

红黑树

科普时间,it KePu's tims.

红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。
它是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees)。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。
它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。

以上科普信息由度娘提供。

性质

红黑树不仅是二叉查找树,它还必须满足5个性质

  • 1.节点非黑即红

  • 2.根节点是黑色

  • 3.每个叶节点(NIL节点,空节点)是黑色的

  • 4.每个红色节点的两个子节点都是黑色(从每个叶子到根的所有路径上不能有两个连续的红色节点)

  • 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

满足了以上性质的二叉查找树的就是红黑树,如果是初次接触的话,是不是看完有点懵,不要慌,接着往下看。

红黑树的效率相对较高,所以它被用来存储相关数据,基本的操作有增加/删除/查找,在这些操作之后可能会破坏红黑树的性质,所以需要相关操作来维护以让红黑树符合上面的性质要求。

而这里提到的相关操作有

  • 变色

  • 左旋

  • 右旋

左旋右旋

是不是对红黑树的任意操作之后,它都还能满足上面的提交的条件呢。

答案是No。

所以也就有了旋转的存在。

旋转跳跃,我闭着眼,尘嚣看不见 你沉醉了没。(请不要唱,快拉回你的心思)

旋转跳跃

嗯,旋转分为左旋右旋

左旋

将x的右子树绕x逆时针旋转,使得x的右子树成为x的父亲,并修改相关引用。

左旋

右旋

是将x的左子树绕x顺时针旋转,使得x的左子树成为x的父亲,并修改相关的引用。

右旋

是不是还是有点迷糊,那么再来两张动图帮助下理解~

左旋

右旋



作者:格子Lin
链接:https://www.jianshu.com/p/38a20925a08c


0人推荐
随时随地看视频
慕课网APP