【死磕 Java 集合】— TreeMap原始碼分析（一）

簡介

TreeMap使用紅黑樹儲存元素，可以保證元素按key值的大小進行遍歷。

繼承體系

TreeMap實現了Map、SortedMap、NavigableMap、Cloneable、Serializable等介面。

SortedMap規定了元素可以按key的大小來遍歷，它定義了一些傳回部分map的方法。

1. public interface SortedMap extends Map {
2. // key的比較器
3. Comparator super K> comparator();
4. // 傳回fromKey（包含）到toKey（不包含）之間的元素組成的子map
5. SortedMap subMap(K fromKey, K toKey);
6. // 傳回小於toKey（不包含）的子map
7. SortedMap headMap(K toKey);
8. // 傳回大於等於fromKey（包含）的子map
9. SortedMap tailMap(K fromKey);
10. // 傳回最小的key
11. K firstKey();
12. // 傳回最大的key
13. K lastKey();
14. // 傳回key集合
15. Set keySet();
16. // 傳回value集合
17. Collection values();
18. // 傳回節點集合
19. Set<Map.Entry> entrySet();
20. }

NavigableMap是對SortedMap的增強，定義了一些傳回離標的key最近的元素的方法。

1. public interface NavigableMap extends SortedMap {
2. // 小於給定key的最大節點
3. Map.Entry lowerEntry(K key);
4. // 小於給定key的最大key
5. K lowerKey(K key);
6. // 小於等於給定key的最大節點
7. Map.Entry floorEntry(K key);
8. // 小於等於給定key的最大key
9. K floorKey(K key);
10. // 大於等於給定key的最小節點
11. Map.Entry ceilingEntry(K key);
12. // 大於等於給定key的最小key
13. K ceilingKey(K key);
14. // 大於給定key的最小節點
15. Map.Entry higherEntry(K key);
16. // 大於給定key的最小key
17. K higherKey(K key);
18. // 最小的節點
19. Map.Entry firstEntry();
20. // 最大的節點
21. Map.Entry lastEntry();
22. // 彈出最小的節點
23. Map.Entry pollFirstEntry();
24. // 彈出最大的節點
25. Map.Entry pollLastEntry();
26. // 傳回倒序的map
27. NavigableMap descendingMap();
28. // 傳回有序的key集合
29. NavigableSet navigableKeySet();
30. // 傳回倒序的key集合
31. NavigableSet descendingKeySet();
32. // 傳回從fromKey到toKey的子map，是否包含起止元素可以自己決定
33. NavigableMap subMap(K fromKey, boolean fromInclusive,
34. K toKey, boolean toInclusive);
35. // 傳回小於toKey的子map，是否包含toKey自己決定
36. NavigableMap headMap(K toKey, boolean inclusive);
37. // 傳回大於fromKey的子map，是否包含fromKey自己決定
38. NavigableMap tailMap(K fromKey, boolean inclusive);
39. // 等價於subMap(fromKey, true, toKey, false)
40. SortedMap subMap(K fromKey, K toKey);
41. // 等價於headMap(toKey, false)
42. SortedMap headMap(K toKey);
43. // 等價於tailMap(fromKey, true)
44. SortedMap tailMap(K fromKey);
45. }

儲存結構

TreeMap只使用到了紅黑樹，所以它的時間複雜度為O(log n)，我們再來回顧一下紅黑樹的特性。

（1）每個節點或者是黑色，或者是紅色。

（2）根節點是黑色。

（3）每個葉子節點（NIL）是黑色。（註意：這裡葉子節點，是指為空(NIL或NULL)的葉子節點！）

（4）如果一個節點是紅色的，則它的子節點必須是黑色的。

（5）從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。

原始碼解析

屬性

1. /**
2. * 比較器，如果沒傳則key要實現Comparable介面
3. */
4. private final Comparator super K> comparator;
5.  
6. /**
7. * 根節點
8. */
9. private transient Entry root;
10.  
11. /**
12. * 元素個數
13. */
14. private transient int size = 0;
15.  
16. /**
17. * 修改次數
18. */
19. private transient int modCount = 0;

（1）comparator

按key的大小排序有兩種方式，一種是key實現Comparable介面，一種方式透過構造方法傳入比較器。

（2）root

根節點，TreeMap沒有桶的概念，所有的元素都儲存在一顆樹中。

Entry內部類

儲存節點，典型的紅黑樹結構。

1. static final class Entry implements Map.Entry {
2. K key;
3. V value;
4. Entry left;
5. Entry right;
6. Entry parent;
7. boolean color = BLACK;
8. }

構造方法

1. /**
2. * 預設構造方法，key必須實現Comparable介面
3. */
4. public TreeMap() {
5. comparator = null;
6. }
7.  
8. /**
9. * 使用傳入的comparator比較兩個key的大小
10. */
11. public TreeMap(Comparator super K> comparator) {
12. this.comparator = comparator;
13. }
14.  
15. /**
16. * key必須實現Comparable介面，把傳入map中的所有元素儲存到新的TreeMap中
17. */
18. public TreeMap(Map extends K, ? extends V> m) {
19. comparator = null;
20. putAll(m);
21. }
22.  
23. /**
24. * 使用傳入map的比較器，並把傳入map中的所有元素儲存到新的TreeMap中
25. */
26. public TreeMap(SortedMapextends V> m) {
27. comparator = m.comparator();
28. try {
29. buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
30. } catch (java.io.IOException cannotHappen) {
31. } catch (ClassNotFoundException cannotHappen) {
32. }
33. }

構造方法主要分成兩類，一類是使用comparator比較器，一類是key必須實現Comparable介面。

其實，筆者認為這兩種比較方式可以合併成一種，當沒有傳comparator的時候，可以用以下方式來給comparator賦值，這樣後續所有的比較操作都可以使用一樣的邏輯處理了，而不用每次都檢查comparator為空的時候又用Comparable來實現一遍邏輯。

1. // 如果comparator為空，則key必須實現Comparable介面，所以這裡肯定可以強轉
2. // 這樣在構造方法中統一替換掉，後續的邏輯就都一致了
3. comparator = (k1, k2) -> ((Comparable super K>)k1).compareTo(k2);

get(Object key)方法

獲取元素，典型的二叉查詢樹的查詢方法。

1. public V get(Object key) {
2. // 根據key查詢元素
3. Entry p = getEntry(key);
4. // 找到了傳回value值，沒找到傳回null
5. return (p==null ? null : p.value);
6. }
7.  
8. final Entry getEntry(Object key) {
9. // 如果comparator不為空，使用comparator的版本獲取元素
10. if (comparator != null)
11. return getEntryUsingComparator(key);
12. // 如果key為空傳回空指標異常
13. if (key == null)
14. throw new NullPointerException();
15. // 將key強轉為Comparable
16. @SuppressWarnings("unchecked")
17. Comparable super K> k = (Comparable super K>) key;
18. // 從根元素開始遍歷
19. Entry p = root;
20. while (p != null) {
21. int cmp = k.compareTo(p.key);
22. if (cmp < 0)
23. // 如果小於0從左子樹查詢
24. p = p.left;
25. else if (cmp > 0)
26. // 如果大於0從右子樹查詢
27. p = p.right;
28. else
29. // 如果相等說明找到了直接傳回
30. return p;
31. }
32. // 沒找到傳回null
33. return null;
34. }
35.  
36. final Entry getEntryUsingComparator(Object key) {
37. @SuppressWarnings("unchecked")
38. K k = (K) key;
39. Comparator super K> cpr = comparator;
40. if (cpr != null) {
41. // 從根元素開始遍歷
42. Entry p = root;
43. while (p != null) {
44. int cmp = cpr.compare(k, p.key);
45. if (cmp < 0)
46. // 如果小於0從左子樹查詢
47. p = p.left;
48. else if (cmp > 0)
49. // 如果大於0從右子樹查詢
50. p = p.right;
51. else
52. // 如果相等說明找到了直接傳回
53. return p;
54. }
55. }
56. // 沒找到傳回null
57. return null;
58. }

（1）從root遍歷整個樹；

（2）如果待查詢的key比當前遍歷的key小，則在其左子樹中查詢；

（3）如果待查詢的key比當前遍歷的key大，則在其右子樹中查詢；

（4）如果待查詢的key與當前遍歷的key相等，則找到了該元素，直接傳回；

（5）從這裡可以看出是否有comparator分化成了兩個方法，但是內部邏輯一模一樣，因此可見筆者 comparator=(k1,k2)->((Comparable

我是一條美麗的分割線，前方高能，請做好準備。

---

特性再回顧

（1）每個節點或者是黑色，或者是紅色。

（2）根節點是黑色。

（3）每個葉子節點（NIL）是黑色。（註意：這裡葉子節點，是指為空(NIL或NULL)的葉子節點！）

（4）如果一個節點是紅色的，則它的子節點必須是黑色的。

（5）從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。

左旋

左旋，就是以某個節點為支點向左旋轉。

整個左旋過程如下：

（1）將 y的左節點 設為 x的右節點，即將 β 設為 x的右節點；

（2）將 x 設為 y的左節點的父節點，即將 β的父節點 設為 x；

（3）將 x的父節點 設為 y的父節點；

（4）如果 x的父節點 為空節點，則將y設定為根節點；如果x是它父節點的左（右）節點，則將y設定為x父節點的左（右）節點；

（5）將 x 設為 y的左節點；

（6）將 x的父節點 設為 y；

讓我們來看看TreeMap中的實現：

1. /**
2. * 以p為支點進行左旋
3. * 假設p為圖中的x
4. */
5. private void rotateLeft(Entry p) {
6. if (p != null) {
7. // p的右節點，即y
8. Entry r = p.right;
9.  
10. // （1）將 y的左節點 設為 x的右節點
11. p.right = r.left;
12.  
13. // （2）將 x 設為 y的左節點的父節點（如果y的左節點存在的話）
14. if (r.left != null)
15. r.left.parent = p;
16.  
17. // （3）將 x的父節點 設為 y的父節點
18. r.parent = p.parent;
19.  
20. // （4）...
21. if (p.parent == null)
22. // 如果 x的父節點 為空，則將y設定為根節點
23. root = r;
24. else if (p.parent.left == p)
25. // 如果x是它父節點的左節點，則將y設定為x父節點的左節點
26. p.parent.left = r;
27. else
28. // 如果x是它父節點的右節點，則將y設定為x父節點的右節點
29. p.parent.right = r;
30.  
31. // （5）將 x 設為 y的左節點
32. r.left = p;
33.  
34. // （6）將 x的父節點 設為 y
35. p.parent = r;
36. }
37. }

右旋

右旋，就是以某個節點為支點向右旋轉。

整個右旋過程如下：

（1）將 x的右節點 設為 y的左節點，即 將 β 設為 y的左節點；

（2）將 y 設為 x的右節點的父節點，即 將 β的父節點 設為 y；

（3）將 y的父節點 設為 x的父節點；

（4）如果 y的父節點 是 空節點，則將x設為根節點；如果y是它父節點的左（右）節點，則將x設為y的父節點的左（右）節點；

（5）將 y 設為 x的右節點；

（6）將 y的父節點 設為 x；

讓我們來看看TreeMap中的實現：

1. /**
2. * 以p為支點進行右旋
3. * 假設p為圖中的y
4. */
5. private void rotateRight(Entry p) {
6. if (p != null) {
7. // p的左節點，即x
8. Entry l = p.left;
9.  
10. // （1）將 x的右節點 設為 y的左節點
11. p.left = l.right;
12.  
13. // （2）將 y 設為 x的右節點的父節點（如果x有右節點的話）
14. if (l.right != null) l.right.parent = p;
15.  
16. // （3）將 y的父節點 設為 x的父節點
17. l.parent = p.parent;
18.  
19. // （4）...
20. if (p.parent == null)
21. // 如果 y的父節點 是 空節點，則將x設為根節點
22. root = l;
23. else if (p.parent.right == p)
24. // 如果y是它父節點的右節點，則將x設為y的父節點的右節點
25. p.parent.right = l;
26. else
27. // 如果y是它父節點的左節點，則將x設為y的父節點的左節點
28. p.parent.left = l;
29.  
30. // （5）將 y 設為 x的右節點
31. l.right = p;
32.  
33. // （6）將 y的父節點 設為 x
34. p.parent = l;
35. }
36. }

未完待續，下一節我們一起探討紅黑樹插入元素的操作。