與 HashSet 是基于 HashMap 實現(xiàn)一樣，TreeSet 同樣是基于 TreeMap 實現(xiàn)的。在《Java 提高篇（二七）—–TreeMap》中 LZ 詳細講解了 TreeMap 實現(xiàn)機制，如果客官詳情看了這篇博文或者多 TreeMap 有比較詳細的了解，那么 TreeSet 的實現(xiàn)對您是喝口水那么簡單。
我們知道 TreeMap 是一個有序的二叉樹，那么同理 TreeSet 同樣也是一個有序的，它的作用是提供有序的 Set 集合。通過源碼我們知道 TreeSet 基礎 AbstractSet，實現(xiàn) NavigableSet、Cloneable、Serializable 接口。其中 AbstractSet 提供 Set 接口的骨干實現(xiàn)，從而最大限度地減少了實現(xiàn)此接口所需的工作。NavigableSet 是擴展的 SortedSet，具有了為給定搜索目標報告最接近匹配項的導航方法，這就意味著它支持一系列的導航方法。比如查找與指定目標最匹配項。Cloneable 支持克隆，Serializable 支持序列化。
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
同時在 TreeSet 中定義了如下幾個變量。
private transient NavigableMap<E,Object> m;
//PRESENT會被當做Map的value與key構建成鍵值對
private static final Object PRESENT = new Object();
其構造方法：
//默認構造方法，根據其元素的自然順序進行排序
public TreeSet() {
this(new TreeMap<E,Object>());
}
//構造一個包含指定 collection 元素的新 TreeSet，它按照其元素的自然順序進行排序。
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
//構造一個新的空 TreeSet，它根據指定比較器進行排序。
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
//構造一個與指定有序 set 具有相同映射關系和相同排序的新 TreeSet。
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
1、add：將指定的元素添加到此 set（如果該元素尚未存在于 set 中）。
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
2、addAll：將指定 collection 中的所有元素添加到此 set 中。
public boolean addAll(Collection<? extends E> c) {
// Use linear-time version if applicable
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<? super E> cc = (Comparator<? super E>) 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);
}
3、ceiling：返回此 set 中大于等于給定元素的最小元素；如果不存在這樣的元素，則返回 null。
public E ceiling(E e) {
return m.ceilingKey(e);
}
4、clear：移除此 set 中的所有元素。
public void clear() {
m.clear();
}
5、clone：返回 TreeSet 實例的淺表副本。屬于淺拷貝。
public Object clone() {
TreeSet<E> clone = null;
try {
clone = (TreeSet<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
clone.m = new TreeMap<>(m);
return clone;
}
6、comparator：返回對此 set 中的元素進行排序的比較器；如果此 set 使用其元素的自然順序，則返回 null。
public Comparator<? super E> comparator() {
return m.comparator();
}
7、contains：如果此 set 包含指定的元素，則返回 true。
public boolean contains(Object o) {
return m.containsKey(o);
}
8、descendingIterator：返回在此 set 元素上按降序進行迭代的迭代器。
public Iterator<E> descendingIterator() {
return m.descendingKeySet().iterator();
}
9、descendingSet：返回此 set 中所包含元素的逆序視圖。
public NavigableSet<E> descendingSet() {
return new TreeSet<>(m.descendingMap());
}
10、first：返回此 set 中當前第一個（最低）元素。
public E first() {
return m.firstKey();
}
11、floor：返回此 set 中小于等于給定元素的最大元素；如果不存在這樣的元素，則返回 null。
public E floor(E e) {
return m.floorKey(e);
}
12、headSet：返回此 set 的部分視圖，其元素嚴格小于 toElement。
public SortedSet<E> headSet(E toElement) {
return headSet(toElement, false);
}
13、higher：返回此 set 中嚴格大于給定元素的最小元素；如果不存在這樣的元素，則返回 null。
public E higher(E e) {
return m.higherKey(e);
}
14、isEmpty：如果此 set 不包含任何元素，則返回 true。
public boolean isEmpty() {
return m.isEmpty();
}
15、iterator：返回在此 set 中的元素上按升序進行迭代的迭代器。
public Iterator<E> iterator() {
return m.navigableKeySet().iterator();
}
16、last：返回此 set 中當前最后一個（最高）元素。
public E last() {
return m.lastKey();
}
17、lower：返回此 set 中嚴格小于給定元素的最大元素；如果不存在這樣的元素，則返回 null。
public E lower(E e) {
return m.lowerKey(e);
}
18、pollFirst：獲取并移除第一個（最低）元素；如果此 set 為空，則返回 null。
public E pollFirst() {
Map.Entry<E,?> e = m.pollFirstEntry();
return (e == null) ? null : e.getKey();
}
19、pollLast：獲取并移除最后一個（最高）元素；如果此 set 為空，則返回 null。
public E pollLast() {
Map.Entry<E,?> e = m.pollLastEntry();
return (e == null) ? null : e.getKey();
}
20、remove：將指定的元素從 set 中移除（如果該元素存在于此 set 中）。
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
21、size：返回 set 中的元素數（set 的容量）。
public int size() {
return m.size();
}
22、subSet：返回此 set 的部分視圖
/**
* 返回此 set 的部分視圖，其元素范圍從 fromElement 到 toElement。
*/
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive) {
return new TreeSet<>(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
/**
* 返回此 set 的部分視圖，其元素從 fromElement（包括）到 toElement（不包括）。
*/
public SortedSet<E> subSet(E fromElement, E toElement) {
return subSet(fromElement, true, toElement, false);
}
23、tailSet：返回此 set 的部分視圖
/**
* 返回此 set 的部分視圖，其元素大于（或等于，如果 inclusive 為 true）fromElement。
*/
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
return new TreeSet<>(m.tailMap(fromElement, inclusive));
}
/**
* 返回此 set 的部分視圖，其元素大于等于 fromElement。
*/
public SortedSet<E> tailSet(E fromElement) {
return tailSet(fromElement, true);
}
由于 TreeSet 是基于 TreeMap 實現(xiàn)的，所以如果我們對 treeMap 有了一定的了解，對 TreeSet 那是小菜一碟，我們從 TreeSet 中的源碼可以看出，其實現(xiàn)過程非常簡單，幾乎所有的方法實現(xiàn)全部都是基于 TreeMap 的。
掃碼關注鍍金池微信號
手機訂課，優(yōu)惠多多