【Java集合】TreeSet、TreeMap源碼解讀

?參考筆記：java TreeSet 和 TreeMap 源碼解讀-CSDN博客

1.前言

2.紅黑樹

2.1 紅黑樹的五大性質

2.2 節點顏色的初始設置

2.3 插入新節后的調整

2.4 刪除結構后的調整

2.5 排序規則

2.6 設計紅黑樹的原因

3.TreeSet簡介、底層實現

3.1 TreeSet簡介

3.2 TreeSet底層實現

4. TreeSet源碼解讀：演示第一種排序機制：元素類實現Comparable接口

????????4.1 準備工作

????????4.2 跳入TreeSet無參構造器?

????????4.3?向集合中添加第一個元素100?

????????????????① 跳入add 方法

????????????????② 跳入put方法

????????????????③ 逐層返回，跳回演示類中

????????4.4?向集合中添加第二個元素 3

????????????????① 跳入put方法

????????????????② 逐層返回，跳回演示類中

????????4.5?向集合中添加重復元素3

????????????????① 跳入put方法

????????????????② 回到add方法

????????????????③ 回到演示類中

????????4.6?繼續向集合添加元素

????????4.7?輸出結果

5. TreeSet源碼解讀：演示第二種排序機制：提供Comparator比較器

????????5.1 準備工作

? ? ? ? 5.2 跳入TreeSet有參構造器

????????5.3 向集合添加第一個元素 100

????????5.4 向集合添加第二個元素3

????????????????① 跳入put方法

????????????????② 逐層返回，跳回演示類中

????????5.5 繼續向集合添加元素

????????5.6 輸出結果

6.TreeMap簡介+底層實現

7.TreeMap源碼解讀

????????7.1 準備工作

????????7.2 TreeMap構造器

????????7.3 向集合添加第一個元素

????????7.4 向集合添加第二個元素

????????7.5 輸出結果

8.完結

1.前言

? ? ? ? 本文將通過 Debug 流程分析，剖析?TreeSet 以及 TreeMap 的底層實現。TreeSet 的底層基于? TreeMap 實現，而 TreeMap 使用 紅黑樹 Red-Balck Tree 作為數據結構。因此本文在對 TreeSet、TreeMap 源碼分析之前會先介紹一下紅黑樹的基本知識
? ? ? ? 注意：本篇博文對?HashSet?源碼的解讀基于主流的?JDK 8.0?的版本

2.紅黑樹

紅黑樹(Red-Black Tree)是一種自平衡二叉搜索樹，它通過特定的顏色規則和調整操作來保持樹的平衡

2.1 紅黑樹的五大性質

①?顏色屬性：每個節點要么是紅色，要么是黑色

②?根節點屬性：根節點必須是黑色

③?紅色節點屬性：紅色節點的子節點必須是黑色，即不能有兩個連續的紅色節點

④?葉子節點屬性：所有葉子節點（NIL節點，空節點）都是黑色

⑤?黑高一致性：從任一節點到其每個葉子節點的所有路徑都包含相同數目的黑色節點，稱為"黑高"

補充：紅黑樹的葉子節點與普通二叉樹葉子節點的區別

普通二叉樹：沒有子節點的節點為葉子節點
紅黑樹：所有實際數據節點都被視為內部節點，真正的葉子節點是虛擬的NIL/NULL節點

那為什么紅黑樹的葉子節點要這樣設計呢？

簡化邊界條件處理：將所有空指針都視為統一的 NIL 節點
保持規則一致性：
- 確保"從節點到葉子路徑的黑高相同"規則可以統一應用
- 確保"紅色節點的子節點必須是黑色"規則可以統一檢查
代碼實現方便

2.2 節點顏色的初始設置

新插入的節點：默認總是設置為紅色
- 原因：設置為紅色不會違反紅黑樹的性質⑤：黑高一致性
- 風險：可能會違反"無連續紅色節點"規則（性質③）
特殊情況：如果插入的是根節點，會強制變為黑色（滿足性質②）

2.3 插入新節后的調整

插入的新節點初始是紅色，也就是 "紅插" ，后續將根據平衡性變色和調整，規則如下：

① 新節點的父節點是黑色：不需要任何調整，沒有違反紅黑樹的五大性質

② 新節點的父節點是紅色：

需要根據叔叔節點（父節點的兄弟）的顏色進一步處理：
- 叔叔節點是黑色：
  - LL型：右單旋，父換爺+變色
  - RR型：左單旋，父換爺+變色
  - LR型：左右雙旋，兒換爺+變色
  - RL型：右左雙旋，兒換爺+變色
- 叔叔節點是紅色：
  - 叔父爺節點先全部變色，爺爺節點變成新節點，然后再來一輪紅黑樹調整

關于紅黑樹的旋轉、調整等其他操作大家可以去在線演示網站試試，有助于理解，鏈接如下：

Red/Black Tree Visualization https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

2.4 刪除結構后的調整

刪除節點后可能會破壞黑高一致性，需要通過復雜的旋轉和重新著色來恢復平衡，本文不作探討

2.5 排序規則

left < root < right

左子樹規則：左子樹中的所有結點都小于根節點
右子樹規則：右子樹中的所有結點都大于根節點

2.6 設計紅黑樹的原因

??🆗，下面開始本文的正式內容，TreeSet、TreeMap的源碼解析

3.TreeSet簡介、底層實現

3.1 TreeSet簡介

① TreeSet 是單列集合 Set 接口的一個實現類，位于 java.util.TreeSet 下，其類定義和繼承關系圖如下所示：

② TreeSet 中的元素不能為 null ，否則會報 NullPointerException? ? ? ? ? ? ??
③ 與 HashSet 類不同， TreeSet 最大的特點是可以進行排序。TreeSet 底層基于 TreeMap，而 TreeMap 底層由紅黑樹實現，可以對元素對象進行排序

排序機制要求：
- 要么元素類實現 Comparable 接口，重寫 compareTo 方法，自定義排序邏輯
- 要么在創建 TreeSet 集合時提供 Comparator 比較器并重寫 compare 方法，自定義排序邏輯

3.2 TreeSet底層實現

① TreeSet 的底層是 TreeMap ，而 TreeMap 是使用紅黑樹數據結構實現的

② TreeSet 中的每個結點類型是 TreeMap$Entry ，Entry 是 TreeMap 的一個靜態內部類，其類的定義如下：

③ TreeSet 的去重機制：

????????（1）如果使用 TreeSet 的無參構建創建 TreeSet 集合，并且添加的元素類已經實現了Comparable 接口的 compareTo 方法，則使用 compareTo 方法去重。即如果 compareTo 方法返回值為 0 ，則認為是相同的元素或數據，放棄添加

????????（2）如果使用 TreeSet 的有參構造創建?TreeSet 集合時提供了 Comparator 比較器，就使用重寫的 compare 方法進行去重。即如果 compare 方法返回值為 0 ，則認為是相同的元素或數據，放棄添加

注意：如果既沒有在創建 TreeSet 對象時提供 Comparator 比較器，也沒有在所添加的元素的類中重寫 Comparable 接口的 compareTo 方法，那么在添加元素時 JVM 一定會報類型轉換異常 ClassCastException

示例代碼：
import java.util.TreeSet;
public class demo {public static void main(String[] args) {System.out.println("hello world");TreeSet treeSet = new TreeSet();treeSet.add(new Cat());}
}class Cat {//none
}
運行結果：

④ TreeSet 的底層是 TreeMap ，那肯定會需要頻繁訪問 TreeMap 中的屬性或者方法，那 Java 中是如何實現的呢？

TreeSet 類中維護了一個屬性 private transient NavigableMap<E，object>? m，初始值為 null ，TreeSet 就是用 m 來訪問 TreeMap 中的屬性或方法的，其源碼如下：

但?NavigableMap 是一個接口類型，看到這大家肯定會覺得懵逼，前面不是說要用 m 來訪問 TreeMap 嗎？這類型都不一致，怎么訪問啊？別急，我們來看看? TreeMap 和 NavigableSet 的關系，如下圖：

🆗，可以看到，TreeMap 類實現了 NavigableMap 接口，所以接口 NavigableMap 引用可以指向 TreeMap 對象，只能說多態機制牛逼！！！TreeSet 底層正好就是這么做的，在使用 TreeSet 構造器創建 TreeSet 集合對象時，會給 private transient NavigableMap<E，object>? m 作初始化，下面我以無參構造器為例：

所以?private transient NavigableMap<E，object>? m 最終的運行類型就是 TreeMap，這樣TreeSet 對象內部就可以通過這個 m 去訪問 TreeMap 中的屬性或者方法了。?還是想感嘆 Java 的多態機制真牛逼！！！

4. TreeSet源碼解讀：演示第一種排序機制：元素類實現Comparable接口

????????4.1 準備工作

? ? ? ? 我們這里的案例是向 TreeSet 集合中添加 int 類型，但底層會實現自動裝箱 int ---> Integer。而 Integer 類剛好實現了 Comparable 接口，并實現 CompareTo 方法，如下：?

? ? ? ? Integer 實現的 compareTo 方法內部調用了 compare 方法。compareTo 方法在底層會作為該紅黑樹的排序機制和去重機制

????????最終該紅黑樹的排序規則如下：

left < root < right

? ? ? ? 最終打印 TreeSet 集合的效果就是按升序排序

????????去重機制：當前添加的元素與某個結點使用 compareTo 方法比較時，如果返回值 = 0，則為重復元素，放棄添加

???????????🆗，解釋完畢后，將用以下代碼作為演示類，一步一步 Debug?

import java.util.TreeSet;
public class demo {public static void main(String[] args) {TreeSet treeSet = new TreeSet();treeSet.add(100);treeSet.add(3);treeSet.add(3);//重復元素，放棄添加treeSet.add(50);treeSet.add(44);System.out.println("treeSet = " + treeSet);//[3,44,50,100]}
}

????????4.2 跳入TreeSet無參構造器?

????????????????首先跳入 TreeSet 的帶參構造，如下?:??

? ? ? ? ? ? ? ? 我們先看上圖中的 ① ，調用的是 TreeMap 的無參構造，無參構造內有一個賦值語句 comparator = null，comparator 是 TreeMap 類維護的一個屬性，用來接收傳入的 Comparator 比較器，作為 TreeSet 集合的排序機制和去重機制。其源碼如下：

? ? ? ? ? ? ? ? 由于我們并沒有傳入 Comparator 比較器，所以 comparator = null

? ? ? ? ? ? ? ? 接著?② 則是調用 TreeSet 的一個有參構造器 TreeSet(NavigableMap<E，Object> m) ，有參構造器內也是一個賦值于語句：this.m = m，為 TreeSet 的 m 屬性賦值。這里的 m 我們在前文的 "TreeSet底層實現" 中提到過，TreeSet 就是通過 m 來訪問 TreeMap 中的屬性和方法的，其源碼如下：

? ? ? ? ? ? ? ? OK，我們跳出 TreeSet 無參構造器，此時的 TreeSet 集合狀態如下：

? ? ? ? ? ? ? ? 可以看到，正如我們在 "TreeSet底層實現" 所說的，m 的類型確實是 TreeMap，TreeMap 有挺多屬性的，但我們只需要關注上圖中綠色框部分。由于當前集合未添加元素，所以此時的 root = null，size = 0，modCount = 0?

????????4.3?向集合中添加第一個元素100?

????????????????① 跳入add 方法

? ? ? ? ? ? ? ? 向 TreeSet 集合中添加第一個元素 100 ，跳入 add 方法，這里會先進入 valueOf 方法進行裝箱操作 int ---> Integer，我們直接跳出，直接重新進入 add 方法，如下所示 :?

????????????????可以看到，底層走的是 TreeMap 的?put 方法；注意實參中的?PRESENT，?這個PRESENT 和 HashSet 中 PRESENT 是一樣的，只起到占位的作用，其源碼如下 :??

????????????????② 跳入put方法

????????????????繼續往下執行，跳入 put 方法，其 源碼+注釋 如下所示，非常詳細：

//添加元素到treeSet集合中
//key：元素值 value：PRESENT占位符
public V put(K key, V value) {//記錄紅黑樹的根結點TreeMap.Entry<K,V> t = root;/** 集合元素個數 = 0 ，執行 if 語句 **///添加第一個元素時，t = null，會執行該 if 語句if (t == null) {compare(key, key); //健壯性判斷，這一行可以不用管//創建一個新結點作為根結點root = new TreeMap.Entry<>(key, value, null);size = 1;//集合元素+1modCount++;//集合修改次數+1return null;//返回null表示添加成功}/** 集合中元素個數 >= 1，執行以下代碼 **/int cmp;//記錄元素比較結果TreeMap.Entry<K,V> parent;//將comparator屬性賦值給cpr，comparator為比較器Comparator<? super K> cpr = comparator;//如果在創建TreeSet集合對象時傳入了比較器，則cpr必不為空，會執行該if語句if (cpr != null) {/*do while循環的作用：利用比較器cpr中的compare方法作為作為排序邏輯，依次遍歷紅黑樹，判斷當前添加的元素是否重復：（1）如果不重復，則為當前添加的元素找到合適的存放位置，最終parent即為添加元素的父結點（2）如果重復，則放棄添加*/do {parent = t;cmp = cpr.compare(key, t.key);//比較欲添加的元素和當前結點t的keyif (cmp < 0)t = t.left;//往左子樹查找存放位置else if (cmp > 0)t = t.right;//右右子樹查找存放位置else//如果cmp = 0 ，說明添加的元素與當前結點t重復，放棄添加return t.setValue(value);} while (t != null);}//如果在元素類中實現了Comparable接口的compareTo方法，則會執行該else語句else {if (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;/*do while循環的作用：利用元素類中實現的Comparable接口的compareTo方法作為排序邏輯，依次遍歷紅黑樹，判斷當前添加的元素是否重復（1）如果不重復，則為當前添加的元素找到合適的存放位置，最終parent即為添加元素的父結點（2）如果重復，則放棄添加*/do {parent = t;cmp = k.compareTo(t.key);//比較欲添加的元素和當前結點t的keyif (cmp < 0)t = t.left;//往左子樹查找存放位置else if (cmp > 0)t = t.right;//往右子樹查找存放位置else//如果cmp = 0 ，說明添加的元素與當前結點t重復，放棄添加return t.setValue(value);} while (t != null);}/**若不是第一次往TreeSet中添加元素，且能執行到這里，說明為當前欲添加的元素不重復，為其找到了合適的存放位置**///將添加的元素包裝在Entry類中，記錄key：添加元素，value：PRESENT占位符，parent：父結點TreeMap.Entry<K,V> e = new TreeMap.Entry<>(key, value, parent);//根據與父結點的比較結果cmp來決定存放在父節點的左子樹還是右子樹if (cmp < 0)parent.left = e;elseparent.right = e;//插入新結點后，需要調用fixAfterInsertion函數來完成紅黑樹中結點的顏色調整、旋轉等fixAfterInsertion(e);//更新size：集合中的元素個數 modCount：修改集合的次數size++;modCount++;//添加成功，返回nullreturn null;
}

? ? ? ? ? ? ? ? 這里我還是一步一步 Debug 過一遍，等整個流程搞清楚再看上面的 源碼+注釋 會更容易理解一點

????????????????我們是向 TreeSet 集合中添加第一個元素 100，所以此時的 root = null ，只會執行上圖中的紅框部分，即 if 結構

? ? ? ? ? ? ? ? if 結構中的第一行 compare 方法不需要理會，它只是作一個健壯性的判斷。接下來就是root = new Entry<>(key，value，null)，即將當前添加的元素用 Entry 類包裝起來，這里我們跳進去看看該構造器方法，如下：

?????????????????可以看到，構造器中對 Entry 類的 key、value、parent 的屬性進行賦值，key（存放添加元素）：100；value：PRESENT占位符，無實際意義；parent（父結點）：null；還有一個比較關鍵的地方就是 color = BLACK（由紅黑樹的五大性質可知，根節點是黑結點）

? ? ? ? ? ? ? ? OK，重新回到 put 方法，繼續往下執行，更新集合元素個數?size = 1 ，更新集合修改次數 moCount ++?

? ? ? ? ? ? ? ? 最后 return null 表示添加元素成功，跳出 put 方法

????????????????③ 逐層返回，跳回演示類中

? ? ? ? ? ? ? ? 逐層返回，回到演示類中，第一個元素 100 添加成功，查看此時的 TreeSet 集合的狀態，如下：

? ? ? ? ? ? ? ? 可以看到，第一個元素 100 添加成功，且作為根節點

????????4.4?向集合中添加第二個元素 3

????????????????① 跳入put方法

????????????????對于第二個元素 3?的添加，我們直接跳到?put?方法，如下?:?

? ? ? ? ? ? ? ? 首先，由于此時 root ！= null，所以 t ！= null，不會執行第一個 if 語句

? ? ? ? ? ? ? ? 接著，是兩個變量的定義：

? ? ? ? ? ? ? ? 定義了一個 int 型變量 cmp 和 Entry 類型變量 parent。這里先不作解釋，后面用到再說

? ? ? ? ? ? ? ? 繼續，往下執行，?如下所示：

? ? ? ? ? ? ? ?由于我們并沒有在創建 TreeSet 集合對象時傳入比較 Comparator ，所以 comparator = cpr = null，所以不會進入該 if 結構中

? ? ? ? ? ? ? ? 接著，重點的來了，如下圖所示：

????????????????首先，先判斷添加的元素 key 是否為 null ，如果為 null 則拋出空指針異常? NullPointerException

????????????????接著，進入非常關鍵的 do while 循環，do while 循環的作用如下：

利用元素類 Integer 中實現的 Comparable 接口的 compareTo 方法作為排序機制和去重機制，依次遍歷紅黑樹，判斷當前添加的元素是否重復：

????????（1）如果不重復：則為當前添加的元素找到合適的存放位置，最終 parent 即為添加元素的父節點

????????（2）如果重復：放棄添加

? ? ? ? ? ? ? ? 我們當前添加的元素為 3 ，顯然不會重復，經過 do while 循環，最終?parent 是元素 3 的父結點，我們看一下元素 3 的父節點是誰：

? ? ? ? ? ? ? ? 可以看到，元素 3 的父節點是我們剛才添加的第一個元素?100

? ? ? ? ? ? ? ? 前面的代碼只是為元素 3 找到了合適的存放位置，即找到了元素 3 的父節點，但還未真正將元素 3 加入到集合中，所以繼續往下執行，如下所示：

? ? ? ? ? ? ? ? 第一行即將當前添加的元素 3 用 Entry 類包裝起來，調用的構造器我們在前面也有提到過，這里就不再贅述了。重點是下面的 if --- else 結構，下面的 if---else 結構的作用：根據當前添加的元素與其父節點 parent 的比較結果 cmp 來決定存放在父節點的左子樹還是右子樹。由于當前添加的元素是 3 ，父節點 parent 是 100，因此 cmp 返回值為 -1 ，執行 if 語句，如下所示：

? ? ? ? ? ? ? ? 所以，元素 3 存放在 100 的左結點

? ? ? ? ? ? ? ? OK，到這別忘了，因為我們在紅黑樹中插入了一個新結點，而紅黑樹又要遵守其五大性質，所以可能需要進行紅黑樹結點顏色的調整、旋轉等，那源碼中如何實現的呢？

? ? ? ? ? ? ? ? 很簡單，Java 是將紅黑樹結點顏色的調整、旋轉等問題包裝成一個叫做 fixAfterInsertion函數，如下：

? ? ? ? ? ? ? ? 見名知意，fixAfterInsertion 的意思就是 "修復插入之后的問題"?。可以看到， fixAfterInsertion 方法的第一行 x.color = RED 就是將新插入的結點顏色設置為紅色，之后再通過一個 while 循環判斷是否需要對紅黑樹的結點顏色進行調整和旋轉，源碼比較復雜，感興趣的朋友可以自己看一下

? ? ? ? ? ? ? ? 最后，執行完 fixAfterInsertion 函數就是更新集合元素個數 size 、更新集合修改次數modCount，return null 表示添加元素成功

????????????????② 逐層返回，跳回演示類中

? ? ? ? ? ? ? ? 執行完 put 方法后，逐層返回，回到演示類，第二個元素 3 添加成功，查看此時的 TreeSet 集合的狀態，如下：

? ? ? ? ? ? ? ? 可以看到，添加的元素 3 確實存放在元素 100 的左節點 left ，此時的紅黑樹結構如下圖所示：

????????4.5?向集合中添加重復元素3

????????當前我們演示的是第一種排序機制：元素類實現 Comparable 接口，所以 TreeSet 的去重機制是根據實現的 Comparable 接口的 compareTo 方法來實現的。即兩個元素利用 compareTo 方法進行比較時，如果返回值 = 0，說明元素重復，放棄添加

????????????????① 跳入put方法

????????????????同樣地，前面一些相同的步驟我們不再贅述，我們直接跳到 put 方法中判斷重復元素的位置，如下：

? ? ? ? ? ? ? ? do while 循環的作用我們在上文中已經說明，忘記了可以往前翻一下。這里由于當前添加的元素 3 為重復元素，所以一定會進入 do while 循環中的 else 部分，如下：

? ? ? ? ? ? ? ? 可以看到，else 部分執行的語句是 return t.setValue(value)?，setValue 方法中其實就是將重復結點 t 的 value（PRESENT占位符）重復賦值為PRESENT占位符，其實相當于什么都沒做，然后 return oldValue = return PRESENT?，所以 put 方法如果添加的是重復元素會 return t.setValue(value) = return PRESENT

????????????????② 回到add方法

? ? ? ? ? ? ? ? put 方法執行完畢，回到 add 方法，由于添加的是重復元素，所以 add 方法的返回值一定為 false ，如下所示：

????????????????③ 回到演示類中

? ? ? ? ? ? ? ? add 方法執行完畢，回到演示類中，重復元素 3?放棄添加，查看此時的 TreeSet 集合的狀態，如下：

? ? ? ? ? ? ? ? 可以看到，集合元素個數 size = 2，元素更改次數 modCount = 2，說明重復元素 3 確實沒有加入到 TreeSet 集合中

????????4.6?繼續向集合添加元素

? ? ? ? 繼續添加元素 50、44，由于排序機制、查找元素存放位置、去重機制前面已經講的很詳細了，所以這里直接看添加元素 55、44 之后的集合狀態，如下所示：

? ? ? ? ?可以看到，根節點 root 變成了元素 50 ，集合元素個數 size = 4，集合更改次數 modCount? = 4，此時的紅黑樹結構如下所示：

? ? ? ? 每個結點滿足 left < root < right?

????????4.7?輸出結果

? ? ? ? ?treeSet 集合輸出結果如下：

? ? ? ? 可以看到，System.out.print(treeSet) 輸出的是 treeSet 集合的升序排序結果

🆗， TreeSet 第一種排序機制的源碼分析完畢，下面進行 TreeSet 第二種排序機制的源碼分析

5. TreeSet源碼解讀：演示第二種排序機制：提供Comparator比較器

????????5.1 準備工作

? ? ? ? 我們這里的案例仍然是向 TreeSet 集合中添加 int 類型，底層會實現自動裝箱 int ---> Integer。但不再使用 Integer 類實現的 Comparable 接口的 compareTo 方法，而是給 TreeSet 傳入一個 Comparator 比較器，在比較器中重寫 compare 方法，作為 TreeSet 的排序機制和去重機制

????????🆗，將用以下代碼作為演示類，一步一步 Debug

import java.util.Comparator;
import java.util.TreeSet;
public class demo {public static void main(String[] args) {TreeSet treeSet = new TreeSet(new Comparator<Integer>() {@Overridepublic int compare(Integer x, Integer y) {//該比較器可以實現一個降序排序的效果if (x < y){return 1;}else if (x > y){return -1;}else{return 0;}//三目運算符的寫法：return (x < y) ? 1 : ((x == y) ? 0 : -1);}});treeSet.add(100);treeSet.add(3);treeSet.add(3);//重復元素，放棄添加treeSet.add(50);treeSet.add(44);System.out.println("treeSet = " + treeSet);//[100，50，44，3]}
}

????????為了更好的與第一種排序機制比較，演示代碼向 TreeSet 集合中添加的是元素同樣是 100、3、3、50、44，不同之處在于我們提供的 Comparator 比較器實現的是降序排序

????????該紅黑樹的排序規則如下：

left > root > right

? ? ? ? 去重機制：當前添加的元素與某個結點使用 Comparator 比較器中重寫的 compare 方法比較時，如果返回值 = 0，則為重復元素，放棄添加?

???????????最終 System.out.println("treeSet = " + treeSet)? 的輸出結果是：treeSet = [100，50，44，3]

? ? ? ? 5.2 跳入TreeSet有參構造器

????????首先我們跳入 TreeSet 的帶參構造，如下?:??

? ? ? ? 先不著急跳入 TreeMap 的構造器，先看一下 TreeSet 帶參構造的形參：是一個 Comparator（比較器）類型的變量，這個?Comparator 類型其實就是一個接口，其源碼如下?:?

? ? ? ? 而我們一開始在演示類中傳入的是這個玩意：

    new Comparator<Integer>() {@Overridepublic int compare(Integer x, Integer y) {//該比較器可以實現一個降序排序的效果if (x < y){return 1;}else if (x > y){return -1;}else{return 0;}//三目運算符的寫法：return (x < y) ? 1 : ((x == y) ? 0 : -1);}}

????????其實就是一個實現了 Comparator 接口的匿名內部類對象，并在 TreeSet 帶參構造中形成了多態。而在 TreeSet 帶參構造中，又將匿名內部類對象 comparator 傳遞給了 TreeMap 的一個帶參構造
????????匿名內部類中實現了 Comparator 接口中的 compare 方法，該方法決定了 TreeSet 集合的排序機制和去重機制

? ? ? ? 🆗，解釋清楚了，我們重新回到下面這張圖：

? ? ? ? 看 ① ，追入 TreeMap 的帶參構造器，如下圖所示：

????????可以看到，在 TreeMap 構造器中，將匿名內部類對象 comparator 傳遞給了 TreeMap 的一個屬性 comparator。并且，此時的 comparator 已經顯示為了匿名內部類 "demo$1" 的形式
? ? ? ? 接著看 ② ，仍然是將 new 好的 TreeMap 對象賦值給 TreeSet 的 m 屬性

????????5.3 向集合添加第一個元素 100

? ? ? ? 向集合中添加第一個元素 100 的流程步驟和演示第一種排序機制的時候是完全一致的，所以這里我以 GIF 展示，如下所示：

? ? ? ? 可以看到，第一個元素 100 成功添加到 TreeSet 集合中，且作為 root 根結點

????????5.4 向集合添加第二個元素3

????????????????① 跳入put方法

? ? ? ? ? ? ? ? 我們直接跳到 put 方法，如下所示：

????????????????這時候 t 顯然不為空，不會進入第一個 if 語句

? ? ? ? ? ? ? ? 繼續往下執行，重點來了，如下:??

????????????????仔細觀察上圖中的紅色底線部分，底層是利用匿名內部類中重寫的 compare 方法來比較欲添加的元素和當前結點 t 的 key 。根據動態綁定機制，這時候如果我們跳入 compare 方法，一定會跳到演示類中的匿名內部類, 如下圖所示 :??

????????????????所以 TreeSet 確實是根據匿名內部類中重寫的 compare 方法作為排序機制和去重機制

????????????????好的，多的也不瞎扯了，執行完 compare 方法，回到原來的 if 結構中：

? ? ? ? ? ? ? ? 其實該 if 結構中的代碼本文在? "4. TreeSet源碼解讀：演示第一種排序機制：元素類實現Comparable接口" 部分已經非常詳細的講解過了，只有 cmp = cpr.compare(key，t.key) 這一條語句的差別，大家可以往前翻一下，這里就不再贅述了、

? ? ? ? ? ? ? ? 繼續往下執行，如下：

? ? ? ? ? ? ? ? "老演員"了

? ? ? ? ? ? ? ? 首先，將添加的元素 3 用 Entry 包裝起來；后面的 if--else 結構根據 cmp 值決定元素 3 存放在父節點 parent 的左結點還是右結點；接著，因為我們在紅黑樹中插入了一個新結點，所以可能需要進行紅黑樹結點顏色的調整、旋轉等，因此調用 fixAfterInsertion(e) 函數，函數名稱見名知意："修復插入的問題"。最后就是更新集合的元素個數 size、更新集合修改次數 modCount、return null 表示添加元素成功

? ? ? ? ? ? ? ? put 方法執行結束

????????????????② 逐層返回，跳回演示類中

? ? ? ? ? ? ? ? 執行完 put 方法后，逐層返回，回到演示類，第二個元素 3 添加成功，查看此時的TreeSet 集合的狀態，如下：

????????????????可以看到，添加的元素 3 存放在元素 100 的右節點 right ，此時的紅黑樹結構如下所示：

????????5.5 繼續向集合添加元素

? ? ? ? 繼續向集合中添加元素 3（重復元素，放棄添加）、50、44，添加之后的 TreeSet 集合狀態如下：

? ? ? ? ?可以看到，根節點 root 變成了元素 50 ，集合元素個數 size = 4，集合更改次數 modCount? = 4，此時的紅黑樹結構如下所示：?

? ? ? ? 每個結點滿足 right > root > left

????????5.6 輸出結果

? ? ? ? ?treeSet 集合輸出結果如下：

? ? ? ? 可以看到，System.out.print(treeSet) 輸出的是 treeSet 集合的降序排序結果?

🆗，TreeSet 第二種排序機制的源碼分析完畢，下面進行 TreeMap 的源碼分析

6.TreeMap簡介+底層實現

說明：TreeMap 的底層實現大多在上面的 TreeSet 部分基本已經講完了

①?TreeMap作為 Map 接口（雙列集合）的一個實現類，也是保存和記錄 key-value 的映射關系——鍵值對的，其類定義與繼承關系圖如下：

②? 同 TreeSet 集合一樣，TreeMap 中的每個結點類型是 TreeMap$Entry ，Entry 是 TreeMap 的一個靜態內部類，其類的定義如下：

注意，對于 TreeSet 來說，每個結點的 value 值是 PRESENT占位符，無實際意義。而 TreeMap 中每個 value 值存儲的是一個有意義的值，是 key-value 鍵值對中的 value?

②?TreeMap 中，key 不可以為 null ，否則會報 NullPointerException ；但是 value 可以為 null

③?TreeMap 也可以對元素進行自定義排序，實現方式與 TreeSet 一致

排序機制要求：
- 要么元素類實現 Comparable 接口，重寫 compareTo 方法，自定義排序邏輯
- 要么在創建 TreeMap?集合時提供 Comparator 比較器并重寫 compare 方法，自定義排序邏輯

不過需要注意的是，是根據 key-value 鍵值對中的 key 進行排序的，至于為什么是根據 key 排序，看上文 TreeSet 的源碼解讀就知道了，關鍵代碼在 TreeMap 類中的 put 方法，如下：

?可以看到，兩種排序機制比較的都是 key-value 鍵值對中的 key

④ TreeMap 集合中，如果先添加鍵值對 {key：1，value："小明"} ，再添加鍵值對 {key：1，value："蔡徐坤"} ，那么 key = 1 對應的 value 會被覆蓋為 "蔡徐坤" 。本質上其實就是 TreeMap 集合不允許 key 重復，判斷 key 重復的機制與 TreeSet 是一樣的，如下：

????????（1）如果使用 TreeMap?的無參構建創建 TreeMap?集合，并且添加的元素類已經實現了Comparable 接口的 compareTo 方法，則使用 compareTo 方法去重。即如果 compareTo 方法返回值為 0 ，則認為是相同的 key ，用新的 value 覆蓋舊的 value?

????????（2）如果使用 TreeMap?的有參構造創建?TreeMap?集合時提供了 Comparator 比較器，就使用重寫的 compare 方法進行去重。即如果 compareTo 方法返回值為 0 ，則認為是相同的 key ，用新的 value 覆蓋舊的 value?

實現代碼其實在 TreeSet 源碼解讀部分講解過了，關鍵代碼在 TreeMap 類中的 put 方法，如下：

7.TreeMap源碼解讀

由于流程和 TreeSet 是基本一致的，所以此處就簡單過一下，點到為止

????????7.1 準備工作

????????使用的案例中，鍵值對 key-value 類型是 Integer-String 。但不再使用 Integer 類實現的Comparable接口的 compareTo 方法，而是在創建 TreeMap 集合時傳入一個 Comparator 比較器，在比較器中重寫 compare 方法，作為 TreeMap 的排序機制和判斷重復邏輯

????????🆗，將用以下代碼作為演示類

import java.util.Comparator;
import java.util.TreeMap;
public class demo {public static void main(String[] args) {TreeMap<Integer, String> treeMap = new TreeMap<>(new Comparator<Integer>() {@Overridepublic int compare(Integer x, Integer y) {//按key降序排序,若返回值為0，說明key重復return (x < y) ? 1 : ((x == y) ? 0 : -1);}});treeMap.put(23,"雞你太美");treeMap.put(50,"Jack");treeMap.put(111,"小馬");treeMap.put(111,"蔡徐坤");//key = 111 重復，用"蔡徐坤"覆蓋"小馬"System.out.println("按 key 進行降序排序，結果如下：");for (Integer key : treeMap.keySet()) {String value = treeMap.get(key);System.out.println(key + " = " + value);}}
}

????????我們提供的 Comparator 比較器實現的是按 key 降序排序

????????所以該紅黑樹的排序規則如下：