集合系列 Set：TreeSet

TreeSet是一個有序的集合，它的作用是提供有序的Set集合。TreeSet是一個有序的集合，它的作用是提供有序的Set集合。它繼承了AbstractSet抽象類，實作了NavigableSet，Cloneable，Serializable接口。TreeSet是基于TreeMap實作的，TreeSet的元素支援2種排序方式：自然排序或者根據提供的Comparator進行排序。

TreeSet 是 Set 集合的紅黑樹實作，但其内部并沒有具體的邏輯，而是直接使用 TreeMap 對象實作。我們先來看看 TreeSet 的定義。

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
           

可以看到 TreeSet 實作了 NavigableSet 接口，而 NavigableSet 接口又繼承了SortedSet 接口。SortedSet 接口又繼承了 Set 接口。

public interface NavigableSet<E> extends SortedSet<E>

public interface SortedSet<E> extends Set<E> 
           

TreeSet 的類繼承關系如下圖所示。

原理

我們還是通過類成員變量、構造方法、核心方法來解析 TreeSet 的實作。

類成員變量

// 具體的實作類
private transient NavigableMap<E,Object> m;
// Map的value
private static final Object PRESENT = new Object();
           

構造方法

TreeSet 一共有 5 個構造方法，如下所示：

// 預設采用TreeMap實作
public TreeSet() {
    this(new TreeMap<E,Object>());
}
// 指定實作類型
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}
// 指定TreeMap的比較器
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}
// 指定初始集合
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}
// 指定比較器以及初始集合
public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}
           

可以看到，如果我們沒有指定傳入的 Map 類型，TreeSet 将自動采用 TreeMap 來實作。而如果你傳入了 NavigableMap 類型的對象，那麼就按照你傳入的對象類型來實作。

核心方法

TreeSet 的核心方法實作直接采用了 TreeMap 的實作，無論是 add 還是 remove 方法。

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}
    
public boolean remove(Object o) {
    return m.remove(o)==PRESENT;
}
           

總結

TreeSet 的實作與 HashSet 類似，都是直接采用了 TreeMap 的方法實作。是以如果了解了 TreeMap，那麼 TreeSet 就很簡單了。

1. 不能有重複的元素；
2. 具有排序功能；
3. TreeSet中的元素必須實作Comparable接口并重寫compareTo()方法，TreeSet判斷元素是否重複

4. 以及确定元素的順序 靠的都是這個方法；

   ①對于Java類庫中定義的類，TreeSet可以直接對其進行存儲，如String，Integer等,因為這些類已經實作了Comparable接口);

   ②對于自定義類，如果不做适當的處理，TreeSet中隻能存儲一個該類型的對象執行個體，否

5. 則無法判斷是否重複。 依賴TreeMap。
6. 相對HashSet,TreeSet的優勢是有序，劣勢是相對讀取慢。根據不同的場景選擇不同的集合。