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
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>{
//外置比较器
private final Comparator<? super K> comparator;
//根节点
private transient Entry<K,V> root;//null
//元素个数
private transient int size = 0;
//外部操作数
private transient int modCount = 0;

public TreeMap() {
comparator = null;
}

public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}

//key - new Student("水菜丽", '女', 27, "2301", "003")
//value - "吃马赛克
public V put(K key, V value) {
Entry<K,V> t = root;//t - 0x001
//第一次添加元素时进入的判断
if (t == null) {
compare(key, key); // key自己判断自己的目的:检查key是否为null

root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
//比较结果
int cmp;
//父节点
Entry<K,V> parent;

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;

//t - null
do {
//parent - 0x001
parent = t;
//cmp - 2
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);
}
//e - 0x003
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;
}

//k1 - new Student("麻生希", '女', 25, "2301", "001")
//k2 - new Student("麻生希", '女', 25, "2301", "001")
@SuppressWarnings("unchecked")
final int compare(Object k1, Object k2) {
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}

//节点类
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; -- 红黑树

/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
}
1
2
3
4
5
6
场景一:
TreeMap<Student,String> map = new TreeMap<>();

map.put(new Student("麻生希", '女', 25, "2301", "001"),"写代码");
map.put(new Student("椎名空", '女', 20, "2301", "002"),"打游戏");
map.put(new Student("水菜丽", '女', 27, "2301", "003"),"吃马赛克");
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
场景二:
TreeMap<Student,String> map = new TreeMap<>(new Comparator<Student>() {
//排序规则 - 按照名字排序,名字长度一致按照年龄排序
@Override
public int compare(Student o1, Student o2) {
if(o1.equals(o2)){
return 0;
}

int nameLen1 = o1.getName().length();
int nameLen2 = o2.getName().length();
if(nameLen1 != nameLen2){
return nameLen1 - nameLen2;
}

int age1 = o1.getAge();
int age2 = o2.getAge();
if(age1 != age2){
return age1 - age2;
}
return 1;
}
});

map.put(new Student("麻生希", '女', 25, "2301", "001"),"写代码");
map.put(new Student("椎名空", '女', 20, "2301", "002"),"打游戏");
map.put(new Student("水菜丽", '女', 27, "2301", "003"),"吃马赛克");

TreeMap底层数据结构是:红黑树