41節介紹了HashSet，我們提到，HashSet有一個重要局限，元素之間沒有特定的順序，我們還提到，Set接口還有另一個重要的實現類TreeSet，它是有序的，與HashSet和HashMap的關系一樣，TreeSet是基於TreeMap的，上節我們介紹了TreeMap，本節我們來詳細討論TreeSet。
下面，我們先來看TreeSet的用法，然後看實現原理，最後總結分析TreeSet的特點。
基本用法
構造方法
TreeSet的基本構造方法有兩個：
public TreeSet() public TreeSet(Comparator<? super E> comparator)
默認構造方法假定元素實現了Comparable接口，第二個使用傳入的比較器，不要求元素實現Comparable。
基本例子
TreeSet經常也只是當做Set使用，只是希望迭代輸出有序，如下面代碼所示：
Set<String> words = new TreeSet<String>();
words.addAll(Arrays.asList(new String[]{
"tree", "map", "hash", "map",
}));
for(String w : words){
System.out.print(w+" ");
}
輸出為：
hash map tree
TreeSet實現了兩點：排重和有序。
如果希望不同的排序，可以傳遞一個Comparator，如下所示：
Set<String> words = new TreeSet<String>(new Comparator<String>(){
@Override
public int compare(String o1, String o2) {
return o1.compareToIgnoreCase(o2);
}});
words.addAll(Arrays.asList(new String[]{
"tree", "map", "hash", "Map",
}));
System.out.println(words);
忽略大小寫進行比較，輸出為：
[hash, map, tree]
需要注意的是，Set是排重的，排重是基於比較結果的，結果為0即視為相同，"map"和"Map"雖然不同，但比較結果為0，所以只會保留第一個元素。
以上就是TreeSet的基本用法，簡單易用。不過，因為有序，TreeSet還實現了NavigableSet和SortedSet接口，NavigableSet擴展了SortedSet，此外，TreeSet還有幾個構造方法，我們來看下。
高級用法
SortedSet接口
SortedSet接口與SortedMap接口類似，具體定義為：
public interface SortedSet<E> extends Set<E> {
Comparator<? super E> comparator();
SortedSet<E> subSet(E fromElement, E toElement);
SortedSet<E> headSet(E toElement);
SortedSet<E> tailSet(E fromElement);
E first();
E last();
}
first()返回第一個元素，last()返回最後一個，headSet/tailSet/subSet都返回一個視圖，包括原Set中的一定取值范圍的元素，區別在於范圍：
與之前介紹的視圖概念一樣，對返回視圖的操作會直接影響原Set。
comparator()返回使用的比較器，如果沒有自定義的比較器，返回值為null。
我們來看一段簡單的示例代碼，以增強直觀感受，輸出用注釋說明：
SortedSet<String> set = new TreeSet<String>();
set.addAll(Arrays.asList(new String[]{
"c", "a", "b", "d","f"
}));
System.out.println(set.first()); //a
System.out.println(set.last()); //f
System.out.println(set.headSet("b"));//[a]
System.out.println(set.tailSet("d"));//[d, f]
System.out.println(set.subSet("b", "e")); //[b, c, d]
set.subSet("b", "e").clear(); //會從原set中刪除
System.out.println(set); //[a, f]
NavigableSet接口
與NavigableMap類似，NavigableSet接口擴展了SortedSet，主要增加了一些查找鄰近元素的方法，比如：
E floor(E e); //返回小於等於e的最大元素 E lower(E e); // 返回小於e的最大元素 E ceiling(E e); //返回大於等於e的最小元素 E higher(E e); //返回大於e的最小元素
相比SortedSet中的視圖方法，NavigableSet增加了一些方法，以更為明確的方式指定返回值中是否包含邊界值，如：
NavigableSet<E> headSet(E toElement, boolean inclusive);
NavigableSet<E> tailSet(E fromElement, boolean inclusive);
NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive);
NavigableSet也增加了兩個對頭尾的操作：
E pollFirst(); //返回並刪除第一個元素 E pollLast(); //返回並刪除最後一個元素
此外，NavigableSet還有如下方法，以方便逆序訪問：
NavigableSet<E> descendingSet(); Iterator<E> descendingIterator();
我們來看一段簡單的示例代碼，以增強直觀感受，輸出用注釋說明：
NavigableSet<String> set = new TreeSet<String>();
set.addAll(Arrays.asList(new String[]{
"c", "a", "b", "d","f"
}));
System.out.println(set.floor("a")); //a
System.out.println(set.lower("b")); //a
System.out.println(set.ceiling("d"));//d
System.out.println(set.higher("c"));//d
System.out.println(set.subSet("b", true, "d", true)); //[b, c, d]
System.out.println(set.pollFirst()); //a
System.out.println(set.pollLast()); //f
System.out.println(set.descendingSet()); //[d, c, b]
其他構造方法
TreeSet的其他構造方法為：
public TreeSet(Collection<? extends E> c) public TreeSet(SortedSet<E> s) TreeSet(NavigableMap<E,Object> m)
前兩個都是以一個已有的集合為參數，將其中的所有元素添加到當前TreeSet，區別在於，在第一個中，比較器為null，假定元素實現了Comparable接口，而第二個中，比較器設為和參數SortedSet中的一樣。
第三個不是public的，是內部用的。
基本實現原理
41節介紹過，HashSet是基於HashMap實現的，元素就是HashMap中的鍵，值是一個固定的值，TreeSet是類似的，它是基於TreeMap實現的，我們具體來看一下代碼，先看其內部組成。
內部組成
TreeSet的內部有如下成員：
private transient NavigableMap<E,Object> m; private static final Object PRESENT = new Object();
m就是背後的那個TreeMap，這裡用的是更為通用的接口類型NavigableMap，PRESENT就是那個固定的共享值。
TreeSet的方法實現主要就是調用m的方法，我們具體來看下。
構造方法
幾個構造方法的代碼為：
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet() {
this(new TreeMap<E,Object>());
}
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);
}
代碼都比較簡單，就不解釋了。
添加元素
add方法的代碼為：
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
就是調用map的put方法，元素e用作鍵，值就是固定值PRESENT，put返回null表示原來沒有對應的鍵，添加成功了。
檢查是否包含元素
代碼為：
public boolean contains(Object o) {
return m.containsKey(o);
}
就是檢查map中是否包含對應的鍵。
刪除元素
代碼為：
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
就是調用map的remove方法，返回值為PRESENT表示原來有對應的鍵且刪除成功了。
子集視圖
subSet方法的代碼：
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive) {
return new TreeSet<>(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
先調用subMap方法獲取NavigatebleMap的子集，然後調用內部的TreeSet構造方法。
頭尾操作
代碼為：
public E first() {
return m.firstKey();
}
public E last() {
return m.lastKey();
}
public E pollFirst() {
Map.Entry<E,?> e = m.pollFirstEntry();
return (e == null) ? null : e.getKey();
}
public E pollLast() {
Map.Entry<E,?> e = m.pollLastEntry();
return (e == null) ? null : e.getKey();
}
代碼都比較簡單，就不解釋了。
逆序遍歷
代碼為：
public Iterator<E> descendingIterator() {
return m.descendingKeySet().iterator();
}
public NavigableSet<E> descendingSet() {
return new TreeSet<>(m.descendingMap());
}
也很簡單。
實現原理小結
TreeSet的實現代碼都比較簡單，主要就是調用內部NavigatableMap的方法。
TreeSet特點分析
與HashSet相比，TreeSet同樣實現了Set接口，但內部基於TreeMap實現，而TreeMap基於大致平衡的排序二叉樹 - 紅黑樹，這決定了它有如下特點：
小結
本節介紹了TreeSet的用法和實現原理，在用法方面，它實現了Set接口，但有序，同樣實現了SortedSet和NavigatableSet接口，在內部實現上，它使用了TreeMap，代碼比較簡單。
至此，我們已經介紹完了Java中主要常見的容器接口和實現類，接口主要有隊列(Queue)，雙端隊列(Deque)，列表(List)，Map和Set，實現類有ArrayList, LinkedList, HashMap, TreeMap, HashSet和TreeSet。
關於接口Queue, Deque, Map和Set，Java容器類中還有其他一些實現類，它們各有特點，讓我們在接下來的幾節中繼續探索。
---------------
未完待續，查看最新文章，敬請關注微信公眾號“老馬說編程”(掃描下方二維碼)，從入門到高級，深入淺出，老馬和你一起探索Java編程及計算機技術的本質。用心原創，保留所有版權。
