java集合（6）：TreeMap源码分析（jdk1.8）
前言
TreeMap的基本概念：
TreeMap集合是基于紅黑樹（Red-Black tree）的 NavigableMap實現。該集合最重要的特點就是可排序，該映射根據其鍵的自然順序進行排序，或者根據創建映射時提供的 Comparator 進行排序，具體取決于使用的構造方法。這句話是什么意思呢？就是說TreeMap可以對添加進來的元素進行排序，可以按照默認的排序方式，也可以自己指定排序方式。
根據上一條，我們要想使用TreeMap存儲并排序我們自定義的類（如User類），那么必須自己定義比較機制：一種方式是User類去實現java.lang.Comparable接口，并實現其compareTo()方法。另一種方式是寫一個類（如MyCompatator）去實現java.util.Comparator接口，并實現compare()方法，然后將MyCompatator類實例對象作為TreeMap的構造方法參數進行傳參（當然也可以使用匿名內部類），這些比較方法是怎么被調用的將在源碼中講解。
下圖是Map集合體系類圖。
正文
TreeMap源碼分析
1，類名及類成員變量
public class TreeMap<K,V>
? ? extends AbstractMap<K,V>
? ? implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
? ? // 比較器對象
? ? private final Comparator<? super K> comparator;
? ? // 根節點
? ? private transient Entry<K,V> root;
? ? // 集合大小
? ? private transient int size = 0;
? ? // 樹結構被修改的次數
? ? private transient int modCount = 0;
? ? // 靜態內部類用來表示節點類型
? ? 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; //?
? ? }
}
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
2，類構造方法
? ? public TreeMap() { ? // 1,無參構造方法
? ? ? ? comparator = null; // 默認比較機制
? ? }
? ? public TreeMap(Comparator<? super K> comparator) { // 2，自定義比較器的構造方法
? ? ? ? this.comparator = comparator;
? ? }
? ? public TreeMap(Map<? extends K, ? extends V> m) { ?// 3，構造已知Map對象為TreeMap
? ? ? ? comparator = null; // 默認比較機制
? ? ? ? putAll(m);
? ? }
? ? public TreeMap(SortedMap<K, ? extends V> m) { // 4，構造已知的SortedMap對象為TreeMap
? ? ? ? comparator = m.comparator(); // 使用已知對象的構造器
? ? ? ? try {
? ? ? ? ? ? buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
? ? ? ? } catch (java.io.IOException cannotHappen) {
? ? ? ? } catch (ClassNotFoundException cannotHappen) {
? ? ? ? }
? ? }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
3，put()方法詳解
? ? 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; ? ?// 集合大小為1
? ? ? ? ? ? modCount++; ?// 結構修改次數自增
? ? ? ? ? ? return null;
? ? ? ? }
? ? ? ? int cmp;
? ? ? ? Entry<K,V> parent;
? ? ? ? Comparator<? super K> cpr = comparator; ?// 比較器對象
? ? ? ? // 如果比較器對象不為空，也就是自定義了比較器
? ? ? ? if (cpr != null) { ??
? ? ? ? ? ? do { // 循環比較并確定元素應插入的位置(也就是找到該元素的父節點)
? ? ? ? ? ? ? ? parent = t; ?// t就是root
? ? ? ? ? ? ? ? // 調用比較器對象的compare()方法，該方法返回一個整數
? ? ? ? ? ? ? ? cmp = cpr.compare(key, t.key);?
? ? ? ? ? ? ? ? if (cmp < 0) ? ? ?// 待插入元素的key"小于"當前位置元素的key，則查詢左子樹
? ? ? ? ? ? ? ? ? ? t = t.left;
? ? ? ? ? ? ? ? else if (cmp > 0) // 待插入元素的key"大于"當前位置元素的key，則查詢右子樹
? ? ? ? ? ? ? ? ? ? t = t.right;
? ? ? ? ? ? ? ? else ? ? ? ? ? ? ?// "相等"則替換其value。
? ? ? ? ? ? ? ? ? ? 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) ? ? ? // 待插入元素的key"小于"當前位置元素的key，則查詢左子樹
? ? ? ? ? ? ? ? ? ? t = t.left;
? ? ? ? ? ? ? ? else if (cmp > 0) ?// 待插入元素的key"大于"當前位置元素的key，則查詢右子樹
? ? ? ? ? ? ? ? ? ? t = t.right;
? ? ? ? ? ? ? ? else ? ? ? ? ? ? ? // "相等"則替換其value。
? ? ? ? ? ? ? ? ? ? return t.setValue(value);
? ? ? ? ? ? } while (t != null);
? ? ? ? }
? ? ? ? Entry<K,V> e = new Entry<>(key, value, parent); ?// 根據key找到父節點后新建一個節點
? ? ? ? if (cmp < 0) ?// 根據比較的結果來確定放在左子樹還是右子樹
? ? ? ? ? ? parent.left = e;
? ? ? ? else
? ? ? ? ? ? parent.right = e;
? ? ? ? fixAfterInsertion(e);
? ? ? ? size++; ? ? ?// 集合大小+1
? ? ? ? modCount++; ?// 集合結構被修改次數+1
? ? ? ? return null;
? ? }
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
3.1，自定義比較器的使用。說了這么多關于比較器的內容，不上手試試這么能行？
先來看下面這段代碼
package com.jimmy.map;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;
public class TreeMapDemo2 {
? ? public static void main(String[] args) {
? ? ? ? Map<String, String> map = new TreeMap<>();
? ? ? ? map.put("ddd", "444");
? ? ? ? map.put("ccc", "333");
? ? ? ? map.put("bbb", "222");
? ? ? ? map.put("aaa", "111");
? ? ? ? Set<Entry<String, String>> entrySet = map.entrySet();
? ? ? ? for (Entry<String, String> each : entrySet) {
? ? ? ? ? ? System.out.println(each.getKey()+"::"+each.getValue());
? ? ? ? }
? ? }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
輸出結果如下，結果是排序過的，為什么呢？那是因為String類實現了Comparable接口并實現了compareTo()方法，該方法按字典順序比較兩個字符串，請自行查看其實現。
aaa::111
bbb::222
ccc::333
ddd::444
1
2
3
4
下面我們寫個自定義User類，使用2種方式將類對象按照age字段從小到大排序。
方式1，User實現Comparable接口并實現了compareTo()方法
User類
package com.jimmy.domain;
public class User implements Comparable<User>{
? ? private String username;
? ? private int age;
? ? public User(String username, int age) {
? ? ? ? this.username = username;
? ? ? ? this.age = age;
? ? }
? ? @Override
? ? public String toString() {
? ? ? ? return "User [username=" + username + ", age=" + age + "]";
? ? }
? ? @Override
? ? public int compareTo(User user) {
? ? ? ? int temp = this.age - user.age;
? ? ? ? return temp == 0 ? this.username.compareTo(user.username) : temp;
? ? } ??
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
測試代碼
package com.jimmy.map;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;
import com.jimmy.domain.User;
public class TreeMapDemo1 {
? ? public static void main(String[] args) {
? ? ? ? Map<User, String> map = new TreeMap<>();
? ? ? ? map.put(new User("jimmy1", 30), "hello");
? ? ? ? map.put(new User("jimmy2", 30), "hello");
? ? ? ? map.put(new User("jimmy", 22), "hello");
? ? ? ? map.put(new User("jimmy", 20), "hello");
? ? ? ? Set<Entry<User, String>> entrySet = map.entrySet();
? ? ? ? for (Entry<User, String> each : entrySet) {
? ? ? ? ? ? System.out.println(each.getKey()+"::"+each.getValue());
? ? ? ? }
? ? }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
輸出結果如下，首先按age排序，若年齡相等則再按username的字母表順序排序。
User [username=jimmy, age=20]::hello
User [username=jimmy, age=22]::hello
User [username=jimmy1, age=30]::hello
User [username=jimmy2, age=30]::hello
1
2
3
4
方式2，寫一個類實現java.util.Comparator接口，并將該類對象傳遞給TreeMap的構造方法。這種方式將實體類和比較機制解耦合，可以寫很多個不同的比較器對象。
實體類
package com.jimmy.domain;
public class User3 { ?// User對象不再實現任何接口
? ? private String username;
? ? private int age;
? ? public User3(String username, int age) {
? ? ? ? super();
? ? ? ? this.username = username;
? ? ? ? this.age = age;
? ? }
? ? public String getUsername() {
? ? ? ? return username;
? ? }
? ? public void setUsername(String username) {
? ? ? ? this.username = username;
? ? }
? ? public int getAge() {
? ? ? ? return age;
? ? }
? ? public void setAge(int age) {
? ? ? ? this.age = age;
? ? }
? ? @Override
? ? public String toString() {
? ? ? ? return "User3 [username=" + username + ", age=" + age + "]";
? ? }
}
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
比較器類
package com.jimmy.map;
import java.util.Comparator;
import com.jimmy.domain.User3;
public class TreeMapComparator implements Comparator<User3>{ ?// 比較器類
? ? @Override
? ? public int compare(User3 o1, User3 o2) {
? ? ? ? int temp = o1.getAge() - o2.getAge();
? ? ? ? return temp == 0 ? o1.getUsername().compareTo(o2.getUsername()) : temp;
? ? }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
測試代碼
package com.jimmy.map;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.Map.Entry;
import com.jimmy.domain.User3;
public class TreeMapDemo3 {
? ? public static void main(String[] args) {
? ? ? ? Map<User3, String> map = new TreeMap<>(new TreeMapComparator());
? ? ? ? map.put(new User3("jimmy1", 30), "hello");
? ? ? ? map.put(new User3("jimmy2", 30), "hello");
? ? ? ? map.put(new User3("jimmy", 22), "hello");
? ? ? ? map.put(new User3("jimmy", 20), "hello");
? ? ? ? Set<Entry<User3, String>> entrySet = map.entrySet();
? ? ? ? for (Entry<User3, String> each : entrySet) {
? ? ? ? ? ? System.out.println(each.getKey()+"::"+each.getValue());
? ? ? ? }
? ? }
}
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
輸出結果如下，跟上面的相同。
User3 [username=jimmy, age=20]::hello
User3 [username=jimmy, age=22]::hello
User3 [username=jimmy1, age=30]::hello
User3 [username=jimmy2, age=30]::hello
1
2
3
4
當然，我們還可以不寫比較器類，而是使用匿名內部類的形式來寫比較器。
package com.jimmy.map;
import java.util.Comparator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.Map.Entry;
import com.jimmy.domain.User3;
public class TreeMapDemo4 {
? ? public static void main(String[] args) {
? ? ? ? Map<User3, String> map = new TreeMap<>(new Comparator<User3>() {
? ? ? ? ? ? @Override
? ? ? ? ? ? public int compare(User3 o1, User3 o2) {
? ? ? ? ? ? ? ? int temp = o1.getAge() - o2.getAge();
? ? ? ? ? ? ? ? return temp == 0 ? o1.getUsername().compareTo(o2.getUsername()) : temp;
? ? ? ? ? ? }
? ? ? ? });
? ? ? ? map.put(new User3("jimmy1", 30), "hello");
? ? ? ? map.put(new User3("jimmy2", 30), "hello");
? ? ? ? map.put(new User3("jimmy", 22), "hello");
? ? ? ? map.put(new User3("jimmy", 20), "hello");
? ? ? ? Set<Entry<User3, String>> entrySet = map.entrySet();
? ? ? ? for (Entry<User3, String> each : entrySet) {
? ? ? ? ? ? System.out.println(each.getKey()+"::"+each.getValue());
? ? ? ? }
? ? }
}
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
4，一幫以getEntry()方法為基礎的獲取元素的方法，其中包括containsKey()，get()，remove()等。
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;
? ? }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
5，一幫以getFirstEntry()，getLastEntry()為基礎的獲取頭和尾元素的方法，其中包括：firstKey()，lastKey()；firstEntry()，lastEntry()；pollFirstEntry()，pollLastEntry()；
? ? final Entry<K,V> getFirstEntry() { // 獲取第一個元素也就是最小的元素，一直遍歷左子樹
? ? ? ? Entry<K,V> p = root;
? ? ? ? if (p != null)
? ? ? ? ? ? while (p.left != null)
? ? ? ? ? ? ? ? p = p.left;
? ? ? ? return p;
? ? }
? ? final Entry<K,V> getLastEntry() { // 獲取最后個元素也就是最大的元素，一直遍歷右子樹
? ? ? ? Entry<K,V> p = root;
? ? ? ? if (p != null)
? ? ? ? ? ? while (p.right != null)
? ? ? ? ? ? ? ? p = p.right;
? ? ? ? return p;
? ? }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
6，keySet()和entrySet()方法，在將HashMap的時候已經講過了，Map沒有迭代器，要將Map轉化為Set，用Set的迭代器才能進行元素迭代。
總結
TreeMap繼承了Map的性質，同時其樹結構又可以進行元素排序，用處很大。
---------------------?
作者：name_s_Jimmy?
來源：CSDN?
原文：https://blog.csdn.net/qq_32166627/article/details/72773293?
版權聲明：本文為博主原創文章，轉載請附上博文鏈接！
總結
以上是生活随笔為你收集整理的java集合（6）：TreeMap源码分析（jdk1.8）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： HashSet源码解析
- 下一篇： CouncurrentHashMap源码