Java源码阅读之TreeMap(红黑树) - JDK1.8

文章目录
  1. 1. 前言
  2. 2. 基础
    1. 2.1. 成员变量
    2. 2.2. 构造函数
    3. 2.3. 红黑树
  3. 3. 功能方法
    1. 3.1. put
    2. 3.2. remove
    3. 3.3. get
    4. 3.4. containsKey/containsValue
    5. 3.5. forEach
    6. 3.6. entrySet
  4. 4. 总结

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

前言

开门见山,山外有山,山外有山…

先简单介绍下TreeMap,来看下类关系图。

怎么说了,TreeMap就是一个有序的键值对集合(这介绍有够简单的)。

TreeMap实现了NavigableMap接口, 而NavigableMap则是通过sortedMap间接继承了Map接口,它定义了一系列导航方法,这些Map之外的方法算是和HashMap的不同,另外的不同点还在于顺序性。

关于TreeMapHashMap的异同点,在接下来的每个章节都可能会提到。

如果还未了解过HashMap的,可以移步这里Java源码阅读之HashMap - JDK1.8和这里Java源码阅读之红黑树在HashMap中的应用 - JDK1.8

接下来,请坐好,准备发车了。

基础

老规矩,不想上来就整一大堆复杂晦涩的方法,还是先从变量了解起。

成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* comparator用来保持treemap的顺序性
* 如果是null,则采取自然顺序
*
* @serial
*/
private final Comparator<? super K> comparator;

/**
* 红黑树根节点
*/
private transient Entry<K,V> root;

/**
* 键值对数量
*/
private transient int size = 0;

/**
* 结构修改次数
*/
private transient int modCount = 0;

从变量可以简单看出treemapHashMap有点类似,而不同点在于

  • HashMap
    1、基于哈希桶+链表/红黑树实现
    2、无序的
  • TreeMap
    1、基于红黑树实现
    2、有序的,通过指定的comparator或者自然顺序

接下来看下构造函数

构造函数

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
/**
* 空参构造,利用自然排序构造一个空的tree map
* 所有的key,必须实现Comparable接口
* 与此同时,所以的key必须具备可比性,{@code k1.compareTo(k2)}不能抛出{@code ClassCastException}
* 假如你试图放一个违反约束的key到map里面,如:放一个string类型的key到原先存储interger类型key的map里面,将会抛出{@code
*/
public TreeMap() {
comparator = null;
}

/**
* 根据给定的comparator构造一个空的/新的map
* 所有插入到map的key通过comparator比较器必须具备可比性
*(因为提供了comparator比较器,所以key可以不用实现Comparable接口)
*
*
* @param comparator comparator如果为null,则使用自然顺序
*/
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}


/**
* 根据给定个的map和key的自然顺序构造一个空的treemap
*
* 关于key的约束同上。
*
* 方法的时间复杂度为n*log(n)
*
* @param m 要放到treemap中的map
* @throws ClassCastException key不具备可比/排序性则抛此异常
* @throws NullPointerException 指定的map是null则抛NPE
*/
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
//调用putAll存放m,后续分析
putAll(m);
}

/**
* 根据给定是sortedMap,利用相同的排序方式构造一个新的treemap
*
* 方法以限行时间运行
*
* @param m sortedmap
* @throws NullPointerException 指定的map是null则抛NPE
*/
public TreeMap(SortedMap<K, ? extends V> m) {
//获取sortedmap的comparator
comparator = m.comparator();
try {
//调用buildFromSorted来存放m
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}

看完了上面几个构造函数,让人印象比较深刻的是对于key的约束说明

不指定comparator时,存放到map里的key必须实现Comparable接口

这里约束目的就是为了利用可比性来维护treemap的顺序性。

上面构造函数中putAllbuildFromSorted没有跟进做具体分析,放置在功能方法里一并介绍。

红黑树

看完变量和构造函数,本来想直接分析功能方法,但是仔细一看,虽然TreeMap里红黑树的代码跟HashMap本质上是一样的,但是代码的结构还是有较大区别,所以先拿来来赏析。(我觉得TreeMap的红黑树代码可读性比HashMap来的高多了)

节点定义

依然是利用一个静态内部类来定义树节点,这里跟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
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
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;

/**
* 根据给定的key/value/parent创建一个新的单元节点(黑)
* 子树为null
*
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}

/**
* 返回key
*
* @return the key
*/
public K getKey() {
return key;
}

/**
* 返回跟key关联的value
*
* @return the value associated with the key
*/
public V getValue() {
return value;
}

/**
* 替换跟key关联的value
*
* @return 返回旧值
*/
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}

/**
* 比较
*/
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;

return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}

/**
* hashcode
*/
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}

/**
* toString
*/
public String toString() {
return key + "=" + value;
}
}

左旋

这里的左旋跟HashMap还是比较相近的,不同点在于HashMap的入参多了一个root来用以指向根节点,而在TreeMap中,root是一个成员变量。

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
private void rotateLeft(Entry<K,V> p) {
//null节点忽略
if (p != null) {
//取出p的右子树
Entry<K,V> r = p.right;
//用r的左子树替换p的右子树
p.right = r.left;
//如果r的左子树存在的话
//则将r的左子树的父节点指向p
if (r.left != null)
r.left.parent = p;
//r的父节点指向p的父节点
//实质上,就是r替换了p的位置
r.parent = p.parent;
//如果p节点不存在父节点
if (p.parent == null)
//那么替换了p节点后的r就是根节点
root = r;
else if (p.parent.left == p)
//如果p的父节点存在且p是左子树
//则将替换p后的r设置为左子树
p.parent.left = r;
else
//否则设置为右子树
p.parent.right = r;
//p变成r的左子树
r.left = p;
//修改引用
p.parent = r;
}
}

右旋

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
private void rotateRight(Entry<K,V> p) {
//null节点忽略
if (p != null) {
//取出p的左子树l
Entry<K,V> l = p.left;
//用l的右子树替换p的左子树
p.left = l.right;
//如果l人右子树存在
//则将l的右子树的父节点指向p
if (l.right != null) l.right.parent = p;
//交换l和p的位置
l.parent = p.parent;
//如果p的父节点不存在
if (p.parent == null)
//那么替换了p节点后的l就是根节点
root = l;
else if (p.parent.right == p)
//如果p的父节点存在,且p是原右子树
//则将替换p后的l设置为右子树
p.parent.right = l;
//否则设置为左子树
else p.parent.left = l;
//修改引用
l.right = p;
p.parent = l;
}
}

插入平衡

插入平衡方法的实现就是我所说的,我觉得比HashMap可读性强的方法。TreeMap把节点的关系操作封装成独立方法了,比如获取父节点、左子树、右子树等,会让含义很清晰,如果类似于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
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
/** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {
//新节点都为红色
x.color = RED;
//x存在且c不是根节点且x的父节点为红色
while (x != null && x != root && x.parent.color == RED) {
//如果x的父节点是祖父节点的左子树的话
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//取出祖父节点的右子树
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//判断祖父节点右子树是否为红色
if (colorOf(y) == RED) {
//红色
//将父节点变成黑色
setColor(parentOf(x), BLACK);
//祖父节点的右子树变成黑色
setColor(y, BLACK);
//祖父节点变成红色
setColor(parentOf(parentOf(x)), RED);
//将x的引用指向祖父节点
x = parentOf(parentOf(x));
} else {
//祖父节点右子树为黑色
//x节点是父节点的右子树
if (x == rightOf(parentOf(x))) {
//x引用指向父节点
x = parentOf(x);
//左旋
rotateLeft(x);
}
//将x的父节点变成黑色
setColor(parentOf(x), BLACK);
//x的祖父节点变成红色
setColor(parentOf(parentOf(x)), RED);
//右旋
rotateRight(parentOf(parentOf(x)));
}
} else {
//如果x的父节点是祖父节点的右子树的话
//取出祖父节点的左子树
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
//祖父节点左子树为红色
if (colorOf(y) == RED) {
//相关变色操作
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
//祖父节点左子树为红色
//入股x是父节点的左子树
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
//右旋
rotateRight(x);
}
//相关变色操作
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
//左旋
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}

删除平衡

删除平衡也是类似的,代码书写比较规范,为了凸显我懒,就不添加注释了,把代码贴出来,有缘人自行参悟。

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
/** From CLR */
private void fixAfterDeletion(Entry<K,V> x) {
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
Entry<K,V> sib = rightOf(parentOf(x));

if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}

if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // symmetric
Entry<K,V> sib = leftOf(parentOf(x));

if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}

if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}

setColor(x, BLACK);
}

罗列TreeMap的红黑树相关代码,是想说明TreeMap里面的实现比起HashMap可读性更为强一些,但是其实质都是一样的,所以上面关于插入平衡和删除平衡的过程这里不再细说,之前格子的Java源码阅读之红黑树在HashMap中的应用 - JDK1.8这篇博客里面有过步骤的相关描述,也有一些图解,有兴趣的可以了解一下。

功能方法

接下来看下相关功能方法,看下我们平时所使用的方法内部是怎么实现的。

put

将指定的键值对存放到TreeMap,不同于HashMap将元素通过HashCode分散到哈希桶里面,TreeMap是通过比较器/自然顺序的形式将元素存放到红黑树中来保证有序性。

下面开始分析put方法。

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
/**
* 存放指定的键值对
* 如果指定的key存在,旧的value将会被新的替换
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
*
* @return 旧的value值{@code key}, 如果之前不存在,则返回null
* (返回null也有可能key对应的值是null)
* @throws ClassCastException 指定的key不具备可比性的话则抛此异常
* @throws NullPointerException 使用自然排序时指定的key为null/comparator不允许null的key,则抛NPE
*
*/
public V put(K key, V value) {
//根节点
Entry<K,V> t = root;
//如果根节点还不存在(TreeMap是空的)
if (t == null) {
//这里的比较做一个类型检查
//可能null
compare(key, key); // type (and possibly null) check
//初始化一个节点
root = new Entry<>(key, value, null);
//size + 1
size = 1;
//修改计数 + 1
modCount++;
//返回null
return null;
}
//如果TreeMap不为空
//定义比较值
int cmp;
//定义父节点
Entry<K,V> parent;
// 分离Comparator和比较路径
Comparator<? super K> cpr = comparator;
//如果存在Comparator
if (cpr != null) {
//通过循环找到合适的节点
//通过二叉查找树的性质进行查找
//知道找到合适的节点
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
//如果找到相同的key,则替换值后返回
return t.setValue(value);
} while (t != null);
}
//不存在比较器,则采用自然顺序比较
else {
//自然顺序比较不允许key为null
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
//同样采用循环来查找插入位置
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
//新建节点
Entry<K,V> e = new Entry<>(key, value, parent);
//根据比较结果,来决定将节点放置在左边还是右边
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//插入平衡
fixAfterInsertion(e);
//size + 1
size++;
//修改计数 + 1
modCount++;
//返回null(执行到这一步,证明未找到相同的key,如果有,则在上面就return了)
return null;
}

看完了put的,再把之前构造函数中的未加分析的putAll一并阅读(完全无违和感)。

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
/**
* 将指定map中的元素都存放到当前treemap
*
* @param map map
* @throws ClassCastException key不合法(参照构造函数章节)
* @throws NullPointerException 指定的map为null/或者存在null的key且treemap不允许null-key的情况下抛出NPE
*/
public void putAll(Map<? extends K, ? extends V> map) {
//获取大小
int mapSize = map.size();
//treemap为空且指定的map不为空并且map是可排序的map
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
//获取Comparator
Comparator<?> c = ((SortedMap<?,?>)map).comparator();
//判断Comparator是否跟当前的一致
if (c == comparator || (c != null && c.equals(comparator))) {
//操作计数 + 1
++modCount;
try {
//调用buildFromSorted进行处理
buildFromSorted(mapSize, map.entrySet().iterator(),
null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
//调用父类的putAll
super.putAll(map);
}

通过分析以上的代码,可以看出putAll里面的逻辑还是比较简单的,一是判断当前treemap是否为空,且给定map的大小合法,并且是给定的map是SortedMap的实例if (size==0 && mapSize!=0 && map instanceof SortedMap)
如果是,则取出比较器判断后调用buildFromSorted进行处理
如果不是,则调用父类的putAll进行处理。

这里留有两个疑问,buildFromSorted和父类的putAll究竟做了哪些处理来完成集合元素的存放呢?

下面一步步分析,先从父类的putAll看起 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* {@inheritDoc}
* 嗯,懒得翻译了,反正我翻译水平也比较差。
*
* @implSpec
* This implementation iterates over the specified map's
* <tt>entrySet()</tt> collection, and calls this map's <tt>put</tt>
* operation once for each entry returned by the iteration.
*
* <p>Note that this implementation throws an
* <tt>UnsupportedOperationException</tt> if this map does not support
* the <tt>put</tt> operation and the specified map is nonempty.
*
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
*/
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}

是不是一目了然了。如果上面提到的判断if (size==0 && mapSize!=0 && map instanceof SortedMap)不成立,则调用父类的putAll方法:通过循环,将元素一个个放到treemap当中,这里的放置put就是在本章节开头分析的put方法。

那么,还剩下一个疑问,如果上面的判断成立,buildFromSorted又做了哪些操作呢?

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
139
140
141
142
143
144
145
146
/**
*
* 线性时间的树构造算法(根据排序数据)
* 可以从迭代器/流当中接受键值对
* 有很多方法入参,但是似乎还是比其他选择更好(PS:我也不知道其他选择是什么)
*
* 该方法接受的4种格式说明:
*
* 1) Map.Entries迭代器. (it != null, defaultVal == null).
* 2) key的迭代器. (it != null, defaultVal != null).
* 3) 交替序列化的键值对流.(it == null, defaultVal == null).
* 4) 序列化的键流. (it == null, defaultVal != null).
*
* 假设调用此方法前comparator已经被设置
*
* @param size 键/或者键值对的数量
* @param it 不为null的话, 新的entries通过这个迭代器创建
* @param str 不为null的话, 新的entries通过序列化流来创建
* 准确点说,it和str必须一个不为null
* @param defaultVal 不为null的话, 会作为默认值
* @throws java.io.IOException 读取流时可能会抛出NPE,如果str为null则不会发生这种情况
* @throws ClassNotFoundException 读取对象是可能抛此异常.如果str为null则不会发生这种情况
*/
private void buildFromSorted(int size, Iterator<?> it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
//设置size
this.size = size;
//调用buildFromSorted来确定root
//分割线之后继续分析
//这里有个小插曲computeRedLevel
//computeRedLevel是根据节点数量来计算完全二叉树的层级
//其实从名字看来,可以理解为计算红色节点的层级
root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
it, str, defaultVal);
}

---------------------------------------------------

/**
* 计算红色节点所在层级
* (完全二叉树的层级)
* 从0开始
*
*/
private static int computeRedLevel(int sz) {
int level = 0;
for (int m = sz - 1; m >= 0; m = m / 2 - 1)
level++;
return level;
}


---------------------------------------------------
//个是buildFromSorted的实际实现方法

/**
* 递归的、真正的实现方法(之前是帮助方法).
* 跟之前的方法比较,相同的参数命名具有相同的意义

* 增加的参数说明在下方
*
* 假定在调用此方法之前已经设置了树图的比较器和大小字段。(它忽略了这两个字段)。
*
* @param level 当前树的层级. 初始化调用应该为0.
* @param lo 子树的首个节点索引. 初始化应该为0.
* @param hi 子树的尾节点索引. 初始化应该为size - 1
* @param redLevel 节点该为红色的层级,必须以size和computeRedLevel计算出来的相等
*/
@SuppressWarnings("unchecked")
private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
int redLevel,
Iterator<?> it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
/*
* 策略: 根节点是最接近中间节点的元素. 为了得到它,首先我们必须递归构建完整的左子树,以便抓取所有的元素
* 然后我们可以继续处理右子树
*
* lo和li参数是为当前子树提取迭代器/流的最小和最大指标,
* 它们实际上没有索引,我们只是按顺序处理,确保items被按相应的顺序处理。
*
*/

//如果hi小于lo,
if (hi < lo) return null;

//mid=(lo+hi)/2; - 无符号右移
int mid = (lo + hi) >>> 1;

//左子树
Entry<K,V> left = null;
//如果lo小于mid
//递归构造左子树
if (lo < mid)
left = buildFromSorted(level+1, lo, mid - 1, redLevel,
it, str, defaultVal);

// extract key and/or value from iterator or stream
//从迭代器/流中获取键值对
K key;
V value;
//使用迭代器
if (it != null) {
//没有有默认值
if (defaultVal==null) {
Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();
key = (K)entry.getKey();
value = (V)entry.getValue();
} else {
//有默认值
key = (K)it.next();
value = defaultVal;
}
} else { // use stream
//使用流
key = (K) str.readObject();
value = (defaultVal != null ? defaultVal : (V) str.readObject());
}
//创建节点
Entry<K,V> middle = new Entry<>(key, value, null);

// color nodes in non-full bottommost level red
//非null节点且是红色层级的,染色成红色
if (level == redLevel)
middle.color = RED;
//判断左子树是否为null
if (left != null) {
//指向左子树
middle.left = left;
//修改引用
left.parent = middle;
}
//递归构造右子树
if (mid < hi) {

Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
it, str, defaultVal);
middle.right = right;
right.parent = middle;
}
//到递归的最外层的话这里的middle就是最终的根节点
return middle;
}

到这里,关于TreeMapput相关方法就分析完毕了,有几个要点梳理一下

  • 1、put方法根据比较器/自然顺序将元素放置到红黑树特定位置后,进行插入平衡
  • 2、putAll实际上有两种情况,一个是迭代取出元素调用父类的put,另外是调用buildFromSorted完成TreeMap构造
  • 3、调用buildFromSorted的前提是,入参必须是SortedMap的实例(还有其他限制,详见上面的if条件)
  • 4、buildFromSorted里面有一个computeRedLevel,是用来计算红色节点层级(也可以理解为计算完全二叉树层级)
  • 5、实际实现buildFromSorted的方法,是一个递归调用的过程,通过middle,递归构造左右子树来完成整棵树的构建。

Go On,下面是remove的方法。

remove

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 如果存在的话,根据指定的key从treemap中移除指定的键值对
*
* @param key 要移除的键值对的key
* @return 和{@code key}相关联的旧值
* 如果{@code key}.没有映射的话为{@code null},返回null的时候也有可能和key相关联的是null
* @throws ClassCastException 指定的key无法和map中的key进行比较,则抛此异常
* @throws NullPointerException 指定的key是null且该treemap采取自然排序/comparator不允许null的key时,抛NPE
*/
public V remove(Object key) {
//根据key获取指定元素节点
Entry<K,V> p = getEntry(key);
//为null则返回
if (p == null)
return null;
//取出旧节点的值
V oldValue = p.value;
//删除元素
deleteEntry(p);
//返回旧值
return oldValue;
}

从源码可以看出,remove方法体里面有两个关键调用,getEntrydeleteEntry,深入了解一下。

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
/**
* 根据给定给定key,返回元素,如果没存在,则返回null
*
* @throws ClassCastException 指定的key无法与map中的比较时,抛出此异常
* @throws NullPointerException 指定的key是null且该treemap采取自然排序/comparator不允许null的key时,抛NPE
*/
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
// 判断是否存在comparator
if (comparator != null)
//如果comparator存在的话,调用getEntryUsingComparator
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
//利用二叉树性质,进行循环搜索
while (p != null) {
//自然比较
int cmp = k.compareTo(p.key);
//根据比较结果,决定取左子树还是右子树
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
//如果比较结果相等,则返回该元素
return p;
}
return null;
}

//继续看getEntryUsingComparator方法

/**
* 通过comparator获取元素的版本.从genEntry分离出来(整洁美观性能beautiful~)
* (对于大多数方法来说它是不值得的,因为大多数方法较少依赖于比较器性能,但是在这里它就是酱紫的呀,它是值得的)
*/
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
//取出比较器
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K,V> p = root;
//从根节点循环
while (p != null) {
//通过比较器获取比较结果
int cmp = cpr.compare(k, p.key);
//根据比较结果,决定取左子树还是右子树
//嗯,其他的就跟上面自然顺序处理是一样样儿的
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
}

查找元素的方法还是比较简单易懂的,但是不能漏掉deleteEntry这个查找后删除的方法,其实这里的deleteEntry就是红黑树的节点删除操作了,之前也貌似也分析过,这里还是把代码和注释贴来,也许你跟我一样也是小懒蛋呢(科普一下:优秀的懒人会有创新的,因为不想重复劳动)


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
/**
* 删除p节点,然后处理删除平衡
*/
private void deleteEntry(Entry<K,V> p) {
//首先,现实相关计数处理
modCount++;
size--;

// If strictly internal, copy successor's element to p and then make p
// point to successor.
//内部严谨的话,拷贝p的后置节点给p,然后将p指向后置节点
//左右子树都存在的情况
if (p.left != null && p.right != null) {
//获取后置节点
Entry<K,V> s = successor(p);
//后置节点的相关值赋值给p
p.key = s.key;
p.value = s.value;
//p指向s
p = s;
} // p has 2 children

// Start fixup at replacement node, if it exists.
//开始在替换节点进行修正
//如果p的左右子树都存在一个的话,则p在上面的条件分支里已经指向s了
//取出替换节点
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
//判断替换节点是否存在
if (replacement != null) {
// Link replacement to parent
//修改父节点引用
replacement.parent = p.parent;
//如果p不存在父节点,那么替换p的replacement节点就是根节点了
//很好,登基了(朕一日不死,你们就都是太子)
if (p.parent == null)
root = replacement;
//如果p是父节点的左子树
else if (p == p.parent.left)
//那么修改父节点的左子树引用为新的替换节点
p.parent.left = replacement;
else
//否则修改右子树引用
p.parent.right = replacement;

// Null out links so they are OK to use by fixAfterDeletion.
//p节点的相关引用置为null,以便后面的删除平衡处理
p.left = p.right = p.parent = null;

// Fix replacement
//如果p节点是黑色节点的话,则进行删除平衡
if (p.color == BLACK)
fixAfterDeletion(replacement);//这个方法在开头的红黑树说明有,或者可以参考我的另外一篇hashmap红黑树博客
//如果替换节点不存在,且p的父节点也不存在
} else if (p.parent == null) { // return if we are the only node.
//则证明p的唯一的节点,返回null
root = null;
} else { // No children. Use self as phantom replacement and unlink.
//p有父节点,但是没有子节点了
//判断p的颜色是否为黑
if (p.color == BLACK)
//如果是,进行删除平衡
fixAfterDeletion(p);
//p的父节点存在
//判断p是父节点的左子树还是右子树
//并进行相关引用修改
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}

//获取后置节点

/**
* 返回后置节点如果存在的话,如果不存在,返回null
*/
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
//t为null,则直接返回null
if (t == null)
return null;
//右子树存在
else if (t.right != null) {
//取出右子树
Entry<K,V> p = t.right;
//循环,遍历并循环取左子树,取出最后一个
while (p.left != null)
p = p.left;
return p;
} else {
//左子树存在
//取出父节点
Entry<K,V> p = t.parent;
//ch指向t
Entry<K,V> ch = t;
//现在的ch(t)是p的子树

//循环(只要父节点存在,且ch(t)节点是父节点的右子树的话)
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
//可以看出来,取出后置节点是这么处理的:
1、如果t的右子树存在的话,就一路向左下遍历,直到null
2、如果t的左子树存在的话,就一路向向上遍历(t必须是父节点的右子树),直到不符合情况

get

(⊙o⊙)…

如果仔细看了remove章节的话,其实这个章节可以略过了。

因为get属于门面方法,实际实现也是由getEntry提供的。

1
2
3
4
5

public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}

containsKey/containsValue

判断TreeMap是否存在对应的key或者对应的value。

判断key比较简单,跟上面get章节是相同道理的,根据key去获取元素,并判断元素是否为null。

判断value跟判断key不一样,但是逻辑也很清晰,首先取出首个元素,然后循环迭代,用指定value和每个元素的value做比较,相同则返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15


public boolean containsKey(Object key) {
return getEntry(key) != null;
}

--------------------------------------------------

public boolean containsValue(Object value) {
//迭代判断
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
if (valEquals(value, e.value))
return true;
return false;
}

forEach

循环迭代,并对每个元素做指定的操作(action)。

这里的循环迭代跟上面的containsValue是一样的,不通点在于containsValue是对每个元素执行判断,而forEach是对每个元素执行相应的action。

1
2
3
4
5
6
7
8
9
10
11
12
@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
int expectedModCount = modCount;
for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
action.accept(e.key, e.value);

if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
}
}

entrySet

本来不打算把这个拿出来分析的,因为完整的分析篇幅实在是太长了。

但是既然都这么长了,还在乎差这一截吗~

这个方法我们用的也是相对比较频繁的,单看entrySet方法根本没什么好看的,很简单,内部有一个entrySet变量,如果未初始化,则new一个,如果已初始化,则返回。

1
2
3
4
public Set<Map.Entry<K,V>> entrySet() {
EntrySet es = entrySet;
return (es != null) ? es : (entrySet = new EntrySet());
}

来看一下EntrySet的数据结构,它是TreeMap的内部类,并且继承了AbstractSet,并实现了相关方法,用过Set的小伙伴应该相熟悉。

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
// TreeMap.java 1057行

//Entry定义
class EntrySet extends AbstractSet<Map.Entry<K,V>> {
/**
* 返回迭代器
*/
public Iterator<Map.Entry<K,V>> iterator() {
//这里调用的getFirstEntry方法,之前分析过
//获取了首节点元素后,创建一个EntryIterator
//这里迭代器相关代码不贴了,有兴趣的可以自行了解
//TreeMap 1238行
return new EntryIterator(getFirstEntry());
}

/**
* 判断是否包含元素o
*/
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
Object value = entry.getValue();
Entry<K,V> p = getEntry(entry.getKey());
return p != null && valEquals(p.getValue(), value);
}

/**
* 移除元素o
*/
public boolean remove(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
Object value = entry.getValue();
Entry<K,V> p = getEntry(entry.getKey());
if (p != null && valEquals(p.getValue(), value)) {
deleteEntry(p);
return true;
}
return false;
}

public int size() {
return TreeMap.this.size();
}

public void clear() {
TreeMap.this.clear();
}

public Spliterator<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
}
}

单从上面的源码看来,entrySet其实也没什么好分析的,不过Set里面还是有很多方法在平时会用到的,之后找个时间,专门开一篇分析Set好了。

天色已晚,各位小伙伴下车洗洗睡吧。

总结

嗯,没有总结,都在上面了。

溜了溜了。给个赞呗。

分享到