TreeSet 源碼解析

​

我的人生就像在白夜裡走路。——東野圭吾《白夜行》

0 前言

上篇我們分析了HashSet，它是組合了 HashMap 實現的，那TreeSet會是怎麼實現的呢？沒錯！組合 TreeMap 實現.

1 繼承體系

​

• 繼承了抽象類AbstracSet，方便擴展
• 實現的 SortedSet,解鎖如下方法
  ​
• 實現 NavigableSet 接口，和 NavigableMap 接口類似，提供了各種導航方法
  ​
• 實現 Cloneable 接口，可被克隆
• 實現Serializable接口，可被序列化
  ​

2 屬性

和 HashSet設計幾乎一致

• 後備的 map
  ​
• 固定的value
  ​

3 構造方法

3.1 無參

• 構造一個新的空TreeSet，並根據其元素的自然順序對其進行排序.插入set中的所有元素必須實現Comparable接口.此外,所有這些元素必須相互可比較:e1.compareTo(e2) 不得為集合中的任何元素e1和e2引發ClassCastException.如果用戶嘗試向違反此約束的集合中添加元素（例如，用戶試圖向其元素為整數的集合中添加字符串元素），則add調用將引發ClassCastException.
  
  ​

3.2 有參

• 構造一個包含指定集合中元素的新TreeSet，並根據其元素的自然順序對其進行排序。 插入集合中的所有元素必須實現Comparable接口。 此外，所有這些元素必須相互可比較：e1.compareTo（e2）不得為集合中的任何元素e1和e2引發ClassCastException.
  ​
• 構造一個新的TreeSet，其中包含與指定的sorted set相同的元素，並使用相同的順序
  ​
• 構造一個新的空樹集，根據指定的比較器排序。 插入到集合中的所有元素必須與指定的比較器相互比較：compare.compare（e1，e2）不得為集合中的任何元素e1和e2拋出ClassCastException。 如果用戶嘗試將違反此約束的元素添加到集合中，則add調用將引發ClassCastException。
  ​

設計大都類似,看幾個核心方法.

4 add

• 直接使用的是 TreeMap#put 並判斷
  ​

如果指定的元素尚不存在，則將其添加到該set中。 更確切地講，如果set中不包含任何元素e2，使得(e==null ? e2==null : e.equals(e2)),則將指定的元素e添加到該set中.如果此set已包含該元素，則調用將使該集合保持不變並返回false。

和HashSet的實現一樣，也是利用了Map保存的Key-Value鍵值對的Key不會重複的特點.諸多類似 add 這種方法實現比較簡單,所以 TreeSet 自己簡單組合實現下即可.

藉由不重複 key 特點,我們還可以用其對 key 進行去重,TreeSet 底層使用的是 TreeMap，TreeMap 在 put 的時候，如果發現 key 是相同的，會把 value 值進行覆蓋，所有不會產生重複的 key ，利用這一特性，使用 TreeSet 正好可以去重.

5 ceiling

• TreeSet中實現NavigableSet接口
  ​
• 而調用的依舊是 TreeMap 中的實現
  ​

• TreeMap 中的 KeySet 定義:
  ​
  與Values和EntrySet不同，TreeMap 中的 KeySet類是靜態的，委派給NavigableMap以供SubMap使用，這勝過需要對以下迭代器方法進行類型測試的麻煩，這些迭代器方法分別在main和submap類中定義

6 總結

總體設計和 HashSet 無異.

• 基於TreeMap實現的，支持自然排序和自定義排序
• 不允許null值；
• 非線程安全，併發場景下可以使用Collections.synchronizedSortedSet(new TreeSet(...))包裝.