這篇文章帶給大家的內容是關於Java中TreeSet怎麼實現？ （詳解），有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。
HashSet是基於HashMap實作的，那TreeSet會是怎麼實現的呢？沒錯！和大家想的一樣，它是基於TreeMap實現的。所以，TreeSet的原始碼也很簡單，主要還是理解TreeMap。
TreeSet的繼承關係
依慣例，先來看TreeSet類別的繼承關係：
##
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable
#
public interface NavigableSet<E> extends SortedSet<E>
Comparator<? super E> comparator();
自然排序和自訂排序。自然排序要求加入到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
再看add和remove方法：
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}建構子
果然，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); // 一个一个添加元素
}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; // 强转成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);
}addAllForTreeSet方法：
#
void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
try {
buildFromSorted(set.size(), set.iterator(), null, defaultVal);
} catch (java.io.IOException | ClassNotFoundException cannotHappen) {
}
}導航方法
既然實作了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());
}
...... // 前面构造了一个存储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);
}descendingIterator的實作：
public Iterator<E> descendingIterator() {
return m.descendingKeySet().iterator();
}總結
以上是Java中TreeSet怎麼實作？ （詳解）的詳細內容。更多資訊請關注PHP中文網其他相關文章！
