java8集合框架(五)-Map的实现类(TreeMap)

java8集合框架(五)-Map的实现类(TreeMap)

前篇提到ConcurrentSkipListMap的线程安全的有序的Map实现,本篇接着分析非线程安全的有序的TreeMap

Note:本篇源码分析基于jdk1.8版本

TreeMap

数据结构

TreeMap的核心数据结构是红黑树。在分析HashMapConcurrentHashMap的时候已经提到红黑树。它有一个非常好的性质:在最坏条件下它的搜索,插入,删除的时间复杂度都是O(lgn)。要理解红黑树算法,建议从2-3树入手,因为它就是2-3树算法的改进版。本篇不准备在红黑树的算法上作过多的解读,假定大家都了解红黑树的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//比较器
private final Comparator<? super K> comparator;
//红黑树根节点
private transient Entry<K,V> root;
//节点类型定义
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;
Entry(K key, V value, Entry<K,V> parent) { ... }
...
}

关键操作-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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
public V put(K key, V value) {
Entry<K,V> t = root;
//如果是空树,初始化
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
//根据比较器的不同,分为两个分支。如果key相等则更新,否则找到该插入的双亲节点
//优先使用构造函数传入的比较器
Comparator<? super K> cpr = 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
return t.setValue(value);
} while (t != null);
}
else {
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);
}
//没有相同的key,构造节点插入
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//维持红黑树性质
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
private void fixAfterInsertion(Entry<K,V> x) {
//插入的节点都默认设置为红色
x.color = RED;
//三种情况任一满足,结束检查。
//1.当前节点为空,2当前节点是root 3.当前节点的父节点是黑色
while (x != null && x != root && x.parent.color == RED) {
//父节点是左儿子
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//y是祖父节点的右儿子
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//情况1:父节点和叔叔节点都是红色的
//处理方案:父亲和叔叔节点变黑色,祖父父节点变红色
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
//祖父节点成为当前节点
x = parentOf(parentOf(x));
} else {
//情况2:当前节点是右儿子,且和父节点都是红色的,叔叔节点是黑色的
//处理方案:左旋
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
//情况3:当前节点是左儿子,且和父节点都是红色的,叔叔节点是黑色的
//处理方案:右旋(右旋结束后出现情况1)
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {//父节点是右儿子,对称操作
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 {
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;
}

说明:仅插入动作来说,红黑树的插入与普通二叉树的插入没什么不同。很简单也很容易理解。复杂就复杂在插入后,需要通过一系列的变换保持红黑树的性质。也就是这里的fixAfterInsertion。总结来说情况有三:

描述 处理
父节点和叔叔节点都是红色 父亲和叔叔节点变黑色,祖父父节点变红色。祖父节点成为当前节点
当前节点是右儿子,且和父节点都是红色的,叔叔节点是黑色的 以父节点为支点左旋。父节点成为当前节点
当前节点是左儿子,且和父节点都是红色的,叔叔节点是黑色的 以父节点为支点右旋。

插入后红黑树性质维护示意图

图片引用自http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html

关键操作-get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
final Entry<K,V> getEntry(Object key) {
//使用构造函数传入的比较器
if (comparator != null)
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;
}

说明:红黑树本质上也是二叉树,所以它的查找效率很好,在任何情况下都是O(lgn)。

关键操作-remove

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
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
if (p.left != null && p.right != null) {
//s是右子树作左边的节点,也是p中序遍历的后继节点
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
//后继节点变成要删除的节点
p = s;
}
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// 将p的儿子节点连上p的父节点
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
// 删除p节点
p.left = p.right = p.parent = null;
// 维护红黑树性质,如果删除的是红色节点,不影响红黑树的性质
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { //P是唯一节点,删除后成为空树
root = null;
} else { //p没有孩子节点,即是叶子节点
if (p.color == BLACK)
fixAfterDeletion(p);
//设置p的父节点的左右儿子为null,删除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;
}
}
}
/** From CLR */
private void fixAfterDeletion(Entry<K,V> x) {
while (x != root && colorOf(x) == BLACK) {
//x是父节点的左儿子
if (x == leftOf(parentOf(x))) {
//sib是父节点的右儿子
Entry<K,V> sib = rightOf(parentOf(x));
//情况1:当前节点的兄弟节点是红色
//处理方案:右旋
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
//情况2:当前节点的兄弟节点和兄弟节点的两个儿子节点均为黑色
//处理方案:兄弟节点设为红色
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
//情况3:当前节点的兄弟节点是黑色的,兄弟节点的左儿子是红色
//处理方案:以兄弟节点为支点右旋
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
//情况4:当前节点的兄弟节点是黑色的,兄弟节点的右儿子是红色
//处理方案:以父节点左旋,右儿子变黑
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // 对称操作
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);
}

说明:同二叉树的的删除动作,当有左右儿子的时候,删除稍微会麻烦一点,需要先寻找后继节点,将后继节点的key/value赋值给当前节点,将问题转化为删除后继节点。需要注意的还是删除节点后红黑树性质维护fixAfterDeletion。如果删除的节点时红色的,无影响。如果是黑色的,那么有下面四种情况。

描述 处理
当前节点的兄弟节点是红色 以父节点为支点右旋
当前节点的兄弟节点和兄弟节点的两个儿子节点均为黑色 兄弟节点设为红色,父节点成为当前节点
当前节点的兄弟节点是黑色的,兄弟节点的左儿子是红色 以兄弟节点为支点右旋
当前节点的兄弟节点是黑色的,兄弟节点的右儿子是红色 以父节点为支点左旋,右儿子变黑

删除红黑树性质维护示意图

图片引用自http://blog.csdn.net/v_JULY_v/article/details/6109153

遍历

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
//Map的entrySet
public Set<Map.Entry<K,V>> entrySet() {
EntrySet es = entrySet;
return (es != null) ? es : (entrySet = new EntrySet());
}
//由EntrySet内部类实现
class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator(getFirstEntry());
}
...
}
//EntrySet的iterator由EntryIterator内部类实现
final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
EntryIterator(Entry<K,V> first) {
super(first);
}
public Map.Entry<K,V> next() {
return nextEntry();
}
}
//EntryIterator的next方法
final Entry<K,V> nextEntry() {
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//寻找后继节点
next = successor(e);
lastReturned = e;
return e;
}

说明:遍历entryset的实现使用了很多内部类,最终来说就是提供合适的Iterator的实现。hasNextNext接口的实现落实在nextEntry,后者每次会调用二叉树的后继节点查找。

关键操作-navigate

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
//初始化一个AscendingSubMap内部类
public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive) {
return new AscendingSubMap<>(this,
false, fromKey, fromInclusive,
false, toKey, toInclusive);
}
static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
private static final long serialVersionUID = 912986545866124060L;
//AscendingSubMap的首尾节点
AscendingSubMap(TreeMap<K,V> m,
boolean fromStart, K lo, boolean loInclusive,
boolean toEnd, K hi, boolean hiInclusive) {
super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
}
//entrySet由内部类AscendingEntrySetView实现
public Set<Map.Entry<K,V>> entrySet() {
EntrySetView es = entrySetView;
return (es != null) ? es : (entrySetView = new AscendingEntrySetView());
}
final class AscendingEntrySetView extends EntrySetView {
public Iterator<Map.Entry<K,V>> iterator() {
return new SubMapEntryIterator(absLowest(), absHighFence());
}
}
//实际处理的类
final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
SubMapEntryIterator(TreeMap.Entry<K,V> first,
TreeMap.Entry<K,V> fence) {
//当前首尾节点
super(first, fence);
}
//还是这个遍历算法,相对于上面的例子,只是首尾节点变化了
public Map.Entry<K,V> next() {
return nextEntry();
}
public void remove() {
removeAscending();
}
}
}

说明:如同遍历entryset的实现使用了很多内部类,通过设置合适的首尾节点(用来跟nextEntry比较是否到达尾部),所以实现的原理没有什么区别。

思考

现在我们想想,为什么TreeMap是非线程安全的?

拿最简单的例子来说,当根节点为空时,两个线程同时进入if的判断。这时后put的线程会覆盖前一个的设置,导致前一个线程下次查找时找不到它put进去的元素。

1
2
3
4
5
6
7
8
9
10
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
...

总结

TreeMap的实现原理是红黑树。很多操作跟二叉树的基础算法无异,很简单也容易理解。困难的地方在于理解红黑树的算法。需要在”破坏性”操作的基础上,去维护红黑树的性质。TreeMap的查找、更新,插入在最坏情况下均能保证O(lgn)的时间复杂度,是非常实用的排序算法。前篇也说过HashMapConcurrentHashMap也看中了这种性质,在链表的长度大于8时,将链表转化为红黑树。至此,对于有序,多线程有ConcurrentSkipListMap,单线程有TreeMap,皆大欢喜。

参考

作者: wuzhaoyang(John)
出处: http://wuzhaoyang.me/
因为作者水平有限,无法保证每句话都是对的,但能保证不复制粘贴,每句话经过推敲。希望能表达自己对于技术的态度,做一名优秀的软件工程师。