<返回更多

一文看懂 HashMap 中的红黑树实现原理

2021-01-18    
加入收藏

前言

本文咱们了解一下红黑树的设计,相比 jdk1.7 的 HashMap 而言,jdk1.8 最重要的就是引入了红黑树的设计,当冲突的链表长度超过 8 个的时候,链表结构就会转为红黑树结构。

01、故事的起因

JDK1.8 最重要的就是引入了红黑树的设计(当冲突的链表长度超过 8 个的时候),为什么要这样设计呢?好处就是避免在最极端的情况下冲突链表变得很长很长,在查询的时候,效率会非常慢。

 

一文看懂 HashMap 中的红黑树实现原理

 

本文主要是讲解红黑树的实现,只有充分理解了红黑树,对于之前的分析才会更加理解。

简单的说,红黑树是一种近似平衡的二叉查找树,其主要的优点就是“平衡“,即左右子树高度几乎一致,以此来防止树退化为链表,通过这种方式来保障查找的时间复杂度为 log(n)。

一文看懂 HashMap 中的红黑树实现原理

 

关于红黑树的内容,网上给出的内容非常多,主要有以下几个特性:

在树的结构发生改变时(插入或者删除操作),往往会破坏上述条件 3 或条件 4,需要通过调整使得查找树重新满足红黑树的条件。

02、调整方式

上面已经说到当树的结构发生改变时,红黑树的条件可能被破坏,需要通过调整使得查找树重新满足红黑树的条件。

调整可以分为两类:一类是颜色调整,即改变某个节点的颜色,这种比较简单,直接将节点颜色进行转换即可;另一类是结构调整,改变检索树的结构关系。结构调整主要包含两个基本操作:左旋(Rotate Left),右旋(RotateRight)

2.1、左旋

左旋的过程是将 p 的右子树绕 p 逆时针旋转,使得 p 的右子树成为 p 的父亲,同时修改相关节点的引用,使左子树的深度加 1,右子树的深度减 1,通过这种做法来调整树的稳定性。过程如下:

一文看懂 HashMap 中的红黑树实现原理

 

以 jdk1.8 为例,打开 HashMap 的源码部分,红黑树内部类 TreeNode 属性分析:

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
		//指向父节点的指针
		TreeNode<K,V> parent;
		//指向左孩子的指针
 TreeNode<K,V> left;
		//指向右孩子的指针
 TreeNode<K,V> right;
		//前驱指针,跟next属性相反的指向
 TreeNode<K,V> prev;
		//是否为红色节点
 boolean red;
		......
}

左旋方法 rotateLeft 如下:

/*
 * 左旋逻辑
 */
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
 TreeNode<K,V> p) {
			//root:表示根节点
			//p:表示要调整的节点
			//r:表示p的右节点
			//pp:表示p的parent节点
			//rl:表示p的右孩子的左孩子节点
 TreeNode<K,V> r, pp, rl;
			//r判断,如果r为空则旋转没有意义
 if (p != null && (r = p.right) != null) {
				//多个等号的连接操作从右往左看,设置rl的父亲为p
 if ((rl = p.right = r.left) != null)
 rl.parent = p;
				//判断p的父亲,为空,为根节点,根节点的话就设置为黑色
 if ((pp = r.parent = p.parent) == null)
 (root = r).red = false;
				//判断p节点是左儿子还是右儿子
 else if (pp.left == p)
 pp.left = r;
 else
 pp.right = r;
 r.left = p;
 p.parent = r;
 }
 return root;
}

2.2、右旋

了解了左旋转之后,相应的就会有右旋,逻辑基本也是一样,只是方向变了。右旋的过程是将 p 的左子树绕 p 顺时针旋转,使得 p 的左子树成为 p 的父亲,同时修改相关节点的引用,使右子树的深度加 1,左子树的深度减 1,通过这种做法来调整树的稳定性。实现过程如下:

一文看懂 HashMap 中的红黑树实现原理

 

同样的,右旋方法 rotateRight 如下:

/*
 * 右旋逻辑
 */
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
 TreeNode<K,V> p) {
			//root:表示根节点
			//p:表示要调整的节点
			//l:表示p的左节点
			//pp:表示p的parent节点
			//lr:表示p的左孩子的右孩子节点
 TreeNode<K,V> l, pp, lr;
			//l判断,如果l为空则旋转没有意义
 if (p != null && (l = p.left) != null) {
				//多个等号的连接操作从右往左看,设置lr的父亲为p
 if ((lr = p.left = l.right) != null)
 lr.parent = p;
				//判断p的父亲,为空,为根节点,根节点的话就设置为黑色
 if ((pp = l.parent = p.parent) == null)
 (root = l).red = false;
				//判断p节点是右儿子还是左儿子
 else if (pp.right == p)
 pp.right = l;
 else
 pp.left = l;
 l.right = p;
 p.parent = l;
 }
 return root;
}

03、操作示例介绍

3.1、插入调整过程图解

一文看懂 HashMap 中的红黑树实现原理

 

3.2、删除调整过程图解

一文看懂 HashMap 中的红黑树实现原理

 

3.3、查询过程图解

一文看懂 HashMap 中的红黑树实现原理

 

04、总结

至此,红黑树的实现就基本完成了,关于红黑树的结构,有很多种情况,情况也比较复杂,但是整体调整流程,基本都是先调整结构然后调整颜色,直到最后满足红黑树特性要求为止。

声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍相关推荐
更多资讯 >>>