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

阅读优秀的源码是提升编程技巧的重要手段之一。
如有不对的地方,欢迎指正~
转载请注明出处https://blog.lzoro.com

前言

基于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的父亲,并修改相关的引用。

右旋

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

左旋

右旋

懒人自有妙计,不过要有版权意识。
动图来源:https://blog.csdn.net/sun_tttt/article/details/65445754

是不是明白一些了~~

基本的关于红黑树概念介绍完毕,需要深入了解的小伙伴请移步搜索引擎。

接下来,坐好了,将车门焊死,准备发车了。

发车

HashMap中的红黑树

先看下HashMap内部类TreeNode<K,V>的定义,它继承了LinkedHashMap.Entry<K,V>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
类java.util.HashMap
第1791行起

/**
* 二叉树实体. 继承 LinkedHashMap.Entry (顺序扩展节点)
*
* linked node.
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//红黑树父节点(链)
TreeNode<K,V> parent; // red-black tree links
//左节点
TreeNode<K,V> left;
//右节点
TreeNode<K,V> right;
//前置节点
TreeNode<K,V> prev; // needed to unlink next upon deletion
//红黑标志
boolean red;

/**
* 构造函数
*/
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}

/**
* 返回根节点
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}

//先略去部分功能代码
...
}

在看相关的功能代码之前,先来看下HahsMap中红黑树左旋右旋的实现

HashMap中的红黑树 - 左旋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* 红黑树左旋操作
*/
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
//p不为null且p的右子树不为null
if (p != null && (r = p.right) != null) {
//将r(p的右子树)的左子树变成p的右子树
//有点拗口 o(╥﹏╥)o
//下面会用一个图示来说明
if ((rl = p.right = r.left) != null)
//修改父节点引用,rl是r(p的右子树)的左子树
rl.parent = p;
//将r(p的右子树)的父节点变成p的父节点(左旋过程,将右子树变成自己的父节点)
if ((pp = r.parent = p.parent) == null)
//如果p节点的父节点为null,证明p是根节点(子树的根节点)
//将r变成根节点(子树的根节点),并变成黑色(符合性质)
(root = r).red = false;
//如果存在父节点且p是该节点的左子树
else if (pp.left == p)
//将r(p的右子树)变成该节点的左子树
pp.left = r;
//如果存在父节点且p节点是该节点的右子树
else
//将r(p的右子树)变成该节点的右子树
pp.right = r;
//将r(p的左子树)变成p(左旋中,将左子树变成自己的父节点)
r.left = p;
//r变成p的父节点
p.parent = r;
}
return root;
}

下面用图示来说明上面的步骤,会比较简单明了不拗口

一、p没有父节点(可以理解为p是根节点)
左旋演示1

一、p有父节点
左旋演示2

HashMap中的红黑树 - 右旋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* 红黑树右旋操作
*/
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
//p不为null且p的左子树不为null
if (p != null && (l = p.left) != null) {
//将l(p的左子树)的右子树变成p的左子树
if ((lr = p.left = l.right) != null)
//修改父节点引用,lr是l(p的左子树)的右子树
lr.parent = p;
//将l(p的右子树)的父节点变成p的父节点(右旋过程,将左子树变成自己的父节点)
if ((pp = l.parent = p.parent) == null)
//将l变成根节点(子树的根节点),并变成黑色(符合性质)
(root = l).red = false;
//如果存在父节点且p是该节点的右子树
else if (pp.right == p)
pp.right = l;
//如果存在父节点且p是该节点的左子树
else
pp.left = l;
//将l(p的右子树)变成p(右旋中,将右子树变成自己的父节点)
l.right = p;
p.parent = l;
}
return root;
}

类似的下面用图演示过程

一、p没有父节点(可以理解为p是根节点)
右旋演示1

一、p有父节点
右旋演示2
右旋


理解了HashMap中红黑树的左旋和右旋,下面看一下几个比较重要的方法

treeify

顾名思义:树化。当哈希桶中的链表长度超过阈值(默认8)的话,就会对链表进行树化,具体来看一下实现。

调用链如下

1、HashMap第643行treeifyBin(tab, hash);,判断阈值,超过则进行树化

2、HashMap第754行,treeifyBin实现,第771行调用TreeNode的树化实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* 替换哈希桶中给定哈希索引的元素
* 如果哈希桶太小,则resize
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//判断哈希桶
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//调整扩容
resize();
//在哈希桶中获取指定位置的元素
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
//替换成树节点
do {
//这里的replacementTreeNode调用了TreeNode的构造函数进行构造
TreeNode<K,V> p = replacementTreeNode(e, null);
//维护顺序
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//修改哈希桶中对应下标的指向为树的头结点
if ((tab[index] = hd) != null)
//执行红黑树化
hd.treeify(tab);
}
}

3、HashMap第1897行,treeify实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/**
* 红黑树化
* @return 树的根节点
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//循环整理
for (TreeNode<K,V> x = this, next; x != null; x = next) {
//取出下一个链表节点
next = (TreeNode<K,V>)x.next;
//将x节点的左右节点设置为null
x.left = x.right = null;
//判断当前红黑树是否有根节点
if (root == null) {
//如果没有根节点
//当前节点的父节点设置为null
x.parent = null;
//设置颜色为黑色(根节点为黑色)
x.red = false;
//将x节点设置为根节点
root = x;
}
//当前红黑树存在根节点
else {
//获取x节点的key
K k = x.key;
//获取x节点的hash
int h = x.hash;
//key的class
Class<?> kc = null;
//从根节点遍历,将x节点插入到红黑树中
for (TreeNode<K,V> p = root;;) {
//定义dir(方向),ph(节点hash)
int dir, ph;
//取出p节点的key
K pk = p.key;
//当p节点的hash大于x节点的hash时
if ((ph = p.hash) > h)
//左侧
dir = -1;
else if (ph < h)
//右侧
dir = 1;

//如果上面的if分支没走,则证明两个节点key的hash值相等,需要通过其他方式进行比较
//如果当前节点(x)的key的类实现了comparable接口,且当前循环节点(p)是相同Class的实例
//那么就通过comparable进行比较
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
//若还是相等,就通过tieBreakOrder比较
dir = tieBreakOrder(k, pk);

//先缓存p节点
TreeNode<K,V> xp = p;
//根据dir方向,来选择在左侧还是右侧插入
//并判断是否为null
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//选择的左/右子树为null

//将原来的p节点(现xp)设置为x的父节点
x.parent = xp;
//如果dir 小于等于0
//将x节点放置在原p(现xp)节点的左侧
if (dir <= 0)
xp.left = x;
//如果dir 大于0
//将x节点放置在原p(现xp)节点的右侧
xp.right = x;
//调用balanceInsertion进行插入平衡
root = balanceInsertion(root, x);
break;
}
}
}
}
//确保哈希桶指定位置存储的节点是红黑树的根节点
moveRootToFront(tab, root);
}

/**
* 确保哈希桶指定位置存储的节点是红黑树的根节点
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
//索引位置
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
//如果不是红黑树的根节点
if (root != first) {
Node<K,V> rn;
//指向红黑树的根节点
tab[index] = root;
TreeNode<K,V> rp = root.prev;
//整理节点顺序
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
//递归做一个恒定校验
assert checkInvariants(root);
}
}

4、HashMap第2206行,balanceInsertion实现

这个方法实现了红黑树插入节点后的平衡(为了满足平衡性),方法的分支较多,如果没有很透彻理解红黑树的相关概念和操作,一时间会容易迷惑,下面代码对整体流程进行了注释,但是仍然比较晦涩,后面会带上图示,加深理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
* 插入平衡
*/
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
//将x节点设为红色(新插入节点一开始为红色)
x.red = true;
//一个没有边界的循环(需要内部跳出)
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//取出x的父节点并判断是否为null
if ((xp = x.parent) == null) {
//x没有父节点
x.red = false;//变色(黑色)
return x;//x为根节点发那会
}
//如果x存在父节点且x的父节点为黑色或x的父父节点不存在
else if (!xp.red || (xpp = xp.parent) == null)
//返回root
return root;
//如果x的父节点是父父节点的左孩子
if (xp == (xppl = xpp.left)) {
//父父节点的右孩子不为null且为红色
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;//变色(黑)
xp.red = false;//变色(黑)
xpp.red = true;//变色(红)
x = xpp;
}
else {
//x是父节点的右孩子
if (x == xp.right) {
//左旋
root = rotateLeft(root, x = xp);
//处理x的父父节点
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//x的父节点存在
if (xp != null) {
xp.red = false;//变色
//x的父父节点存在
if (xpp != null) {
xpp.red = true;//变色
//右旋
root = rotateRight(root, xpp);
}
}
}
}
//如果x的父节点是父父节点的右孩子
else {
//x的父父节点的左孩子存在且为红色
if (xppl != null && xppl.red) {
xppl.red = false;//变色(黑)
xp.red = false;//变色(黑)
xpp.red = true;//变色(红)
x = xpp;
}
else {
//如果x是父节点的左孩子
if (x == xp.left) {
//右旋
root = rotateRight(root, x = xp);
//处理x的父父节点
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//如果x的父节点存在
if (xp != null) {
xp.red = false;//变色(黑)
//如果x的父父节点存在
if (xpp != null) {
xpp.red = true;//变色(红)
//左旋
root = rotateLeft(root, xpp);
}
}
}
}
}
}

下面用图示,举个栗子~

栗子在这里

举个栗子

假如有如下一个链表,里面的数字代表hash值(先不考虑hash分布)

链表

然后按照链表顺序取出节点进行红黑树插入,以及插入后平衡操作(左旋右旋/变色),来看一下整个过程

插入节点过程1

插入节点过程2

综合上面的描述和图示,大概可以把链表转红黑树的操作总结如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1、将链表的首节点当做临时的红黑树根节点,左右孩子置为null
2、循环按顺序取出链表的节点,进行红黑树插入,和插入后平衡
2.1、取出链表节点,经过hash比较,插入到红黑树合适的位置(保证平衡性)
2.2、由于插入的节点会破坏红黑树的性质,所以需要进行插入后平衡
2.2.1、新插入的节点置为红色
2.2.2、父节点和父父节点的null判断和颜色判断
2.2.2.1、判断新插入节点的父节点是否存在,不存在则返回
2.2.2.1、如果父节点是黑色的,或者父父节点不存在着,则返回

2.2.3、父节点是父父节点的左孩子还是右孩子判断
2.2.3.1、是左孩子且兄弟节点存在并且是红色,则执行相应的变色,然后进行下一轮判断。
2.2.3.2、是左孩子当兄弟节点不存在(或者是黑色),则执行相应的左旋/右旋。

2.2.3.3、是右孩子且兄弟节点存在并且是红色,则执行相应的变色,然后进行下一轮判断。
2.2.3.4、是右孩子当兄弟节点不存在(或者是黑色),则执行相应的左旋/右旋。
3、链表循环完毕后,确保哈希桶指定位置存储的是红黑树的根节点


嗯,没了。细节请看源码和图示,如果觉得迷糊,可以自己动手画画图,或者Debug。

untreeify

有了树化,肯定也有非树化。

有起有落,月缺月圆,凡事要有平衡。一本正经地胡说八道。

举个栗子

突然就斗起了表情。

没错,这个方法就是将红黑树退化成链表,俗称链表化。

入口有几个地方

  • 节点删除时,红黑树的大小低于阈值,退化成链表。2035行tab[index] = first.untreeify(map); // too small
  • 扩容/调整容量时,调用split方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 红黑树链表化
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
//循环,将红黑树转成链表
for (Node<K,V> q = this; q != null; q = q.next) {
//构造一个普通链表节点
Node<K,V> p = map.replacementNode(q, null);
//维护顺序
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}

putTreeVal

嗯,没什么好说的,红黑树的节点插入。

对应上篇博客的链表节点插入,但相比链表来说会比较复杂。不过流程与之前提到过的树化当中的单一节点插入没有太大区别,也是从红黑树的根节点进行遍历,寻找合适的位置插入,并进行插入后的平衡(变色/左旋/右旋),待插入平衡后,确保存储在哈希桶指定位置的节点是红黑树的根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
* 红黑树版本的节点插入
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
//取出根节点
TreeNode<K,V> root = (parent != null) ? root() : this;
//从根节点进行遍历,选择合适的位置插入节点(无边界遍历,需要内部跳出)
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
//判断方向
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
//先缓存当前遍历的树节点
TreeNode<K,V> xp = p;
//判断该树节点下是否有子节点
//如果没有,则根据之前判断的方向(左侧/右侧)进行插入
//如果已有,则向下遍历继续上面的步骤,直到插入合适的位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
//插入到合适的位置和,可能破坏红黑树的性质,所以需要进行插入平衡
//插入平衡后,需要确保哈希桶下标位置上存储的节点是红黑树的节点
//这些在上面的树化过程都有提到,此处不再赘述
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}

getTreeNode

红黑树中的节点查找。

对应链表的节点查找,在链表树化后,节点的查找就是红黑树实现的。查找的逻辑还是比较清晰的,因为红黑树是自平衡二叉查找树,节点左子树都比自己小,右子树都比自己大,所以根据给定的hash,可以确定从左子树还是右子树查找,然后循环进行定位,知道最终找到节点或者不存在该节点时,结束查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* 红黑树节点查找的入口方法
*/
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}

/**
* 根据给定的hash和key,从红黑树的根节点开始进行查找
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
//取出左子树和右子树,根据hash和key进行查找
TreeNode<K,V> pl = p.left, pr = p.right, q;
//根据hash大小决定取左子树还是右子树
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
//如果在节点相等,就返回
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}

removeTreeNode

移除红黑树节点。

对应链表节点的移除,红黑树版本的节点移除相比链表会复杂一些,因为涉及到维护红黑树的平衡性和相关性质。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
/**
* 移除给定节点, 调用该方法时要确保节点存在.
* 因为无法交换存在叶子节点的内部节点内容,所以这会比典型的红黑树节点删除来得复杂
* 遍历过程中"next"指针指向的继任节点是可访问的,所以我们交换了树的连接.
* 如果当前树节点太少,则将二叉树替换成简单形式
* (2-6节点测试触发,取决于树的结构)
*/
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
//判断哈希桶
if (tab == null || (n = tab.length) == 0)
return;
//下标
int index = (n - 1) & hash;
//取出指定下标的根节点
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
//继任节点和前置节点
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
//前置节点不存在,则证明要移除的节点是根节点
if (pred == null)
//将继任节点往前移
tab[index] = first = succ;
else
//前置节点存在,则将继任节点连接到前置节点(移除本节点)
pred.next = succ;
//判断继任节点是否存在
if (succ != null)
//存在的话,修改前置引用
succ.prev = pred;
//这个时候first为null,则表示哈希桶指定位置可能只有一个节点
if (first == null)
//返回
return;
//获取根节点
if (root.parent != null)
root = root.root();
//根节点不存在或者根节点的左子树/右子树不存在或者左左子树不存在
//该判断是作为链表化的阈值
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
//红黑树太小,进行链表化
tab[index] = first.untreeify(map); // too small
return;
}
//取得要移除的节点,左子树,右子树
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
//左右子树同时存在
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
//循环查找继任节点
while ((sl = s.left) != null) // find successor
s = sl;
//交换p和s的颜色
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
//相等则证明p是s的直接父节点(只有一个层级)
if (s == pr) { // p was s's direct parent
//交换位置
p.parent = s;
s.right = p;
}
//如果是多个层级
else {
//取出s的父节点
TreeNode<K,V> sp = s.parent;
//下面操作仍然是交换p和s的位置
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
pr.parent = s;
}
//清空p的右子树引用
p.left = null;
//调整相关引用
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
//确定替换节点
if (sr != null)
replacement = sr;
else
replacement = p;
}
//只有左子树存在
else if (pl != null)
replacement = pl;
//只有右子树存在
else if (pr != null)
replacement = pr;
//左右子树都不存在
else
replacement = p;
//判断替换的节点是不是自身
if (replacement != p) {
//不是自身的话,则执行相关替换操作
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}
//判断p的颜色
//如果p是红色节点,则将根节点赋值给r
//如果p是黑色节点,则进行删除平衡(类似于插入平衡)
//这里的r要存储红黑树的根节点
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
//如果替换节点是自身的话
if (replacement == p) { // detach
//进行分离操作
TreeNode<K,V> pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
//确保哈希桶下标指定位置存储的是红黑树根节点
moveRootToFront(tab, r);
}

split

只有在resize的时候被调用,作用是在哈希桶扩容/调整容量时,将红黑树拆分成两颗树,在红黑树太小时进行链表化等操作。

具体看源码注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
* Splits nodes in a tree bin into lower and upper tree bins,
* or untreeifies if now too small. Called only from resize;
* see above discussion about split bits and indices.
*
* @param map the map
* @param tab the table for recording bin heads
* @param index the index of the table being split
* @param bit the bit of hash to split on
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
//拆分成两棵树
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
//遍历节点
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
//将e的next引用置空,目的是从e断开
e.next = null;
//将e的hash和bit(其实就是oldCap)相与(是不是很熟悉,其实跟链表的操作类似)
//为0的放到lower树
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
//不为0放到upper树
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
//判断lower树是否为null
if (loHead != null) {
//判断是否需要链表化
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
//判断upper树是否为null
if (hiHead != null) {
//判断是否需要链表化
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}

到这里,关于HashMap中的红黑树相关内容基本上都介绍完毕了,篇幅有点长,没法面面俱到,呼~~(放松一下)。

后话

本来想着每个方法和每个操作流程都画图解释比较直观。

但是后面花现,画图,真的是他喵了太耗费精力了。

我花4,除了动图之外,其他的图都是我自己画的。对了,开头的那棵树除外。当然,表情包也不是。

其他图示留待后面时间充裕了补上吧。

溜了溜了,有帮助的话给格子点个赞呗。

分享到