Java常用資料結構之Set之TreeSet
上篇文章我們分析了HashSet,它是基於HashMap實現的,那TreeSet會是怎麼實現的呢?沒錯!和大家想的一樣,它是基於TreeMap 實現的。所以,TreeSet的原始碼也很簡單,主要還是理解TreeMap。
TreeSet的繼承關係
按照慣例,先來看TreeSet類的繼承關係:
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable 複製程式碼
- 毫不意外的繼承了抽象類AbstracSet,方便擴充套件;
- 實現了一個NavigableSet介面,和NavigableMap介面類似,提供了各種導航方法;
- 實現了Cloneable介面,可以克隆;
- 實現了Serializable介面,可以序列化;
這裡主要看NavigableSet介面類:
public interface NavigableSet<E> extends SortedSet<E> 複製程式碼
熟悉的味道,繼承SortedSet介面。SortedSet則提供了一個返回比較器的方法:
Comparator<? super E> comparator(); 複製程式碼
和SortedMap一樣,支援自然排序 和自定義排序 。自然排序要求新增到Set中的元素實現Comparable介面,自定義排序要求實現一個Comparator比較器。
原始碼分析
關鍵點
關鍵點自然是TreeSet如何保證元素不重複以及元素有序的,前面說了它是基於TreeMap實現的,那我們來看看吧。
private transient NavigableMap<E,Object> m; // 保證有序 // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); // 固定Value 複製程式碼
縱觀TreeSet原始碼,發現只有這兩個屬性(還有個uid,這裡就不算了)。很明顯,m
是用來儲存元素的,但m
宣告的是NavigableMap
而不是TreeMap
。可以猜測,TreeMap
應該是在構造方法裡實例化的,這裡使用NavigableMap
可以讓TreeSet更加靈活。PRESENT
和HashSet中的PRESENT
作用一樣,作為固定Value值進行佔位的。
再看add
和remove
方法:
public boolean add(E e) { return m.put(e, PRESENT)==null; } public boolean remove(Object o) { return m.remove(o)==PRESENT; } 複製程式碼
和HashSet的實現一樣,也是利用了Map儲存的Key-Value鍵值對的Key不會重複的特點。
建構函式
果然,TreeSet中的TreeMap是在建構函式中初始化的。
public TreeSet() { this(new TreeMap<>()); // 預設自然排序的TreeMap } public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); // 自定義比較器的TreeMap } public TreeSet(Collection<? extends E> c) { this(); // 還是用的預設 addAll(c); // 將元素一個一個新增到TreeMap中 } public TreeSet(SortedSet<E> s) { this(s.comparator()); // 使用傳入的SortedSet的比較器 addAll(s); // 一個一個新增元素 } 複製程式碼
預設例項化了一個自然排序的TreeMap,當然,我們可以自定義比較器。
這裡跟蹤下addAll
方法:
publicboolean 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; // 強轉成TreeMap Comparator<?> cc = set.comparator(); Comparator<? super E> mc = map.comparator(); if (cc==mc || (cc != null && cc.equals(mc))) { // 要保證set和map的比較器一樣 map.addAllForTreeSet(set, PRESENT); // TreeMap專門為TreeSet準備的方法 return true; } } return super.addAll(c); } 複製程式碼
呼叫了TreeMap的addAllForTreeSet
方法:
void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) { try { buildFromSorted(set.size(), set.iterator(), null, defaultVal); } catch (java.io.IOException | ClassNotFoundException cannotHappen) { } } 複製程式碼
看到buildFromSorted
,應該很熟悉,在TreeMap的文章中分析過。該方法將傳入的集合元素構造成了一棵最底層的結點為紅色,而其他結點都是黑色的紅黑樹。
導航方法
既然實現了NavigableSet
,那各種導航方法自然少不了。它們的實現也很簡單,直接呼叫m
對應的導航方法即可。例如:
public E first() { return m.firstKey(); // 返回第一個元素 } public E lower(E e) { return m.lowerKey(e); // 返回小於e的第一個元素 } public NavigableSet<E> headSet(E toElement, boolean inclusive) { return new TreeSet<>(m.headMap(toElement, inclusive)); // 取前幾個元素構成子集 } public E pollFirst() { // 彈出第一個元素 Map.Entry<E,?> e = m.pollFirstEntry(); return (e == null) ? null : e.getKey(); } public NavigableSet<E> descendingSet() { // 倒排Set return new TreeSet<>(m.descendingMap()); } ...... 複製程式碼
這裡需要注意的是返回子集合的方法,例如:headSet
。返回的子集合是可以新增和刪除元素的,但是有邊界限制
,舉個栗子。
// 前面構造了一個儲存Int的Set // 3、5、7、9 SortedSet<Integer> subSet = intSet.headSet(8); // 最大值7,超過7越界 for (Integer sub : subSet) { System.out.println(sub); } subSet.add(2); //subSet.add(8); // 越界了 subSet.remove(3); for (Integer sub : subSet) { System.out.println(sub); } 複製程式碼
TreeSet也是支援逆序輸出的,因為有descendingIterator
的實現:
public Iterator<E> descendingIterator() { return m.descendingKeySet().iterator(); } 複製程式碼