TreeSet概述
所有實現的接口：

Serializable, Cloneable, Iterable<E>, Collection<E>, NavigableSet<E>, Set<E>, SortedSet<E>
1
以下是類的對應關系。

從左到右分析上圖：?
實現Serializable接口，即支持序列化。?
實現Cloneable接口，即能被克隆。?
實現Iterable接口，即能用foreach使用迭代器遍歷得到集合元素。?
實現了NavigableSet接口，即能支持一系列的導航方法。比如查找與指定目標最匹配項。并且，TreeSet中含有一個”NavigableMap類型的成員變量”m，而m實際上是”TreeMap的實例”。?
繼承AbstractSet，AbstractSet實現set,所以它是一個Set集合，不包含滿足element1.eauqals(element2)的元素樹，并且最多包含一個null.

所以，TreeSet的本質是一個”有序的，并且沒有重復元素”的集合，而且支持自定義排序。

接下來讓我們看一下具體的源代碼。（基于ＪＤＫ１.７）

構造函數：
方式一：

? ?TreeSet(NavigableMap<E,Object> m) {
? ? ? ? this.m = m;
? ? }
1
2
3
看NavigableMap的代碼是 :

public interface NavigableMap<K,V> extends SortedMap<K,V>
1
而SortedMap又是繼承Map:

public interface SortedMap<K,V> extends Map<K,V>
1
由此，該方式TreeSet初始化時 底層是map

方式二：

? ? ? ? // 以自然排序方式創建一個新的 TreeMap，
? ? ? ? // 根據該 TreeSet 創建一個 TreeSet，
? ? ? ? // 使用該 TreeMap 的 key 來保存 Set 集合的元素

? ? public TreeSet() {
? ? ? ? this(new TreeMap<E,Object>());
? ? }
1
2
3
4
5
6
7
方式三：

? ? ? ? // 以定制排序方式創建一個新的 TreeMap，
? ? ? ? // 根據該 TreeSet 創建一個 TreeSet，
? ? ? ? // 使用該 TreeMap 的 key 來保存 Set 集合的元素

? public TreeSet(Comparator<? super E> comparator) {
? ? ? ? this(new TreeMap<>(comparator));
? ? }
1
2
3
4
5
6
7
8
方式四：

? ? public TreeSet(Collection<? extends E> c) {
? ? ? ? // 調用方式一構造器創建一個 TreeSet，底層以 TreeMap 保存集合元素
? ? ? ? this();?
? ? ? ? // 向 TreeSet 中添加 Collection 集合 c 里的所有元素
? ? ? ? addAll(c);?
? ? }
1
2
3
4
5
6
從上述可以看出，TreeSet的構造函數都是通過新建一個TreeMap作為實際存儲Set元素的容器。因此得出結論: TreeSet的底層實際使用的存儲容器就是TreeMap。TreeSet 里絕大部分方法都是直接調用 TreeMap 的方法來實現的。?
列舉一個，大家也可以自行查看源碼。

? ? public ?boolean addAll(Collection<? extends E> c) {
? ? ? ? if (m.size()==0 && c.size() > 0 &&
? ? ? ? ? ? c instanceof SortedSet &&
? ? ? ? ? ? m instanceof TreeMap) {
? ? ? ? ? ? SortedSet<? extends E> set = (SortedSet<? extends E>) c;
? ? ? ? ? ? //快看！！！我在這！！！
? ? ? ? ? ? TreeMap<E,Object> map = (TreeMap<E, Object>) m;
? ? ? ? ? ? Comparator<?> cc = set.comparator();
? ? ? ? ? ? Comparator<? super E> mc = map.comparator();
? ? ? ? ? ? if (cc==mc || (cc != null && cc.equals(mc))) {
? ? ? ? ? ? ? ? map.addAllForTreeSet(set, PRESENT);
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return super.addAll(c);
? ? }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Set幾乎都成了Map的一個馬甲 , 我們來關注一下TreeSet應用的TreeMap。

紅黑樹
對于 TreeMap 而言，它采用一種被稱為“紅黑樹”的排序二叉樹，這是一種自平衡排序二叉樹，樹中每個節點的值，都大于或等于在它的左子樹中的所有節點的值，并且小于或等于在它的右子樹中的所有節點的值，這確保紅黑樹運行時可以快速地在樹中查找和定位的所需節點。每個 Entry 都被當成“紅黑樹”的一個節點對待。

紅黑樹又稱紅-黑二叉樹，它首先是一顆二叉樹，它具體二叉樹所有的特性。同時紅黑樹更是一顆自平衡的排序二叉樹。?
?
當且僅當兩個子樹的高度差不超過1時，這個樹是平衡二叉樹。?
通過這種直觀的對比，能感受到平衡二叉樹比普通二叉樹在查找上的優勢。平衡二叉樹的時間復雜度是log(n)，如果二叉樹的元素個數為n，那么不管是對樹進行插入節點、查找、刪除節點都是log(n)次循環調用就可以了。?
而紅黑樹是一種自平衡二叉查找樹。放棄了追求完全平衡，追求大致平衡，在與平衡二叉樹的時間復雜度相差不大的情況下，保證每次插入最多只需要三次旋轉就能達到平衡，實現起來也更為簡單。不是嚴格控制左、右子樹高度或節點數之差小于等于1。但紅黑樹高度依然是平均log(n)，且最壞情況高度不會超過2log(n)。一個更明顯的特點就是紅黑樹是有顏色區分的。?

紅黑樹中調整位置和改變顏色，相關代碼，隨意感受一下：

? ? private void fixAfterDeletion(Entry<K,V> x) {
? ? ? ? while (x != root && colorOf(x) == BLACK) {
? ? ? ? ? ? if (x == leftOf(parentOf(x))) {
? ? ? ? ? ? ? ? Entry<K,V> sib = rightOf(parentOf(x));

? ? ? ? ? ? ? ? if (colorOf(sib) == RED) {
? ? ? ? ? ? ? ? ? ? setColor(sib, BLACK);
? ? ? ? ? ? ? ? ? ? setColor(parentOf(x), RED);
? ? ? ? ? ? ? ? ? ? rotateLeft(parentOf(x));
? ? ? ? ? ? ? ? ? ? sib = rightOf(parentOf(x));
? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? if (colorOf(leftOf(sib)) ?== BLACK &&
? ? ? ? ? ? ? ? ? ? colorOf(rightOf(sib)) == BLACK) {
? ? ? ? ? ? ? ? ? ? setColor(sib, RED);
? ? ? ? ? ? ? ? ? ? x = parentOf(x);
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? if (colorOf(rightOf(sib)) == BLACK) {
? ? ? ? ? ? ? ? ? ? ? ? setColor(leftOf(sib), BLACK);
? ? ? ? ? ? ? ? ? ? ? ? setColor(sib, RED);
? ? ? ? ? ? ? ? ? ? ? ? rotateRight(sib);
? ? ? ? ? ? ? ? ? ? ? ? sib = rightOf(parentOf(x));
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? setColor(sib, colorOf(parentOf(x)));
? ? ? ? ? ? ? ? ? ? setColor(parentOf(x), BLACK);
? ? ? ? ? ? ? ? ? ? setColor(rightOf(sib), BLACK);
? ? ? ? ? ? ? ? ? ? rotateLeft(parentOf(x));
? ? ? ? ? ? ? ? ? ? x = root;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? } else { // symmetric
? ? ? ? ? ? ? ? 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);
? ? }
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
規則：
其紅黑樹的規則是：?
（1）節點是紅色或黑色。?
（2）根節點是黑色。?
（3）每個葉節點（NIL節點，空節點）是黑色的。?
（4）每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)?
（5）從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

添加過程：
紅黑樹的添加原理及TreeMap的put實現過程;?
（1）將紅黑樹當成一顆二叉查找樹，將節點插入。?
（2）將新插入的節點設置為紅色?
（3）通過旋轉和著色，使它恢復平衡，重新變成一顆符合規則的紅黑樹。?
該部分參考博客TreeMap源碼解析： 及視頻演示。有興趣的可以深入研究。

對比：
1. TreeSet和TreeMap
相同點：?
TreeMap和TreeSet都是有序的集合。?
TreeMap和TreeSet都是非同步集合，因此他們不能在多線程之間共享，不過可以使用方法Collections.synchroinzedMap()來實現同步。?
運行速度都要比Hash集合慢，他們內部對元素的操作時間復雜度為O(logN)，而HashMap/HashSet則為O(1)。

不同點：?
最主要的區別就是TreeSet和TreeMap非別實現Set和Map接口?
TreeSet只存儲一個對象，而TreeMap存儲兩個對象Key和Value（僅僅key對象有序）?
TreeSet中不能有重復對象，而TreeMap中可以存在。

TreeSet和HashSet
相同點：?
都是唯一不重復的Set集合。

不同點：?
底層來說，HashSet是用Hash表來存儲數據，而TreeSet是用二叉平衡樹來存儲數據。 功能上來說，由于TreeSet是有序的Set，可以使用SortedSet。接口的first()、last()等方法。但由于要排序，勢必要影響速度。所以，如果不需要順序的話，還是使用HashSet吧，使用Hash表存儲數據的HashSet在速度上更勝一籌。如果需要順序則TreeSet更為明智。?
底層來說，HashSet是用Hash表來存儲數據，而TreeSet是用二叉平衡樹來存儲數據。

總結
1、不能有重復的元素；?
2、具有排序功能；?
3、TreeSet中的元素必須實現Comparable接口并重寫compareTo()方法，TreeSet判斷元素是否重復 、以及確定元素的順序 靠的都是這個方法；?
①對于java類庫中定義的類，TreeSet可以直接對其進行存儲，如String，Integer等,因為這些類已經實現了Comparable接口);?
②對于自定義類，如果不做適當的處理，TreeSet中只能存儲一個該類型的對象實例，否則無法判斷是否重復。?
4、依賴TreeMap。?
5、相對HashSet,TreeSet的優勢是有序，劣勢是相對讀取慢。根據不同的場景選擇不同的集合。
---------------------?
作者：青年小篆?
來源：CSDN?
原文：https://blog.csdn.net/u010176014/article/details/52096398?
版權聲明：本文為博主原創文章，轉載請附上博文鏈接！

總結

以上是生活随笔為你收集整理的TreeSet源码解析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。