Java中TreeSet怎麼實作？ （詳解）

這篇文章帶給大家的內容是關於Java中TreeSet怎麼實現？ （詳解），有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

HashSet是基於HashMap實作的，那TreeSet會是怎麼實現的呢？沒錯！和大家想的一樣，它是基於TreeMap實現的。所以，TreeSet的原始碼也很簡單，主要還是理解TreeMap。

TreeSet的繼承關係

依慣例，先來看TreeSet類別的繼承關係：

##

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

1. #毫不意外的繼承了抽象類別AbstracSet，方便擴展；

2. 實作了一個NavigableSet接口，和NavigableMap介面類似，提供了各種導航方法；

3. 實作了Cloneable接口，可以複製；

4. 實作了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方法：

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);
    }

#呼叫了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();
    }

總結

1. TreeSet是基於TreeMap實作的，支援自然排序和自訂排序，可以進行逆序輸出；

2. TreeSet不允許null值；

3. TreeSet不是執行緒安全的，多執行緒環境下可以使用SortedSet s = Collections.synchronizedSortedSet(new TreeSet(.. .));

以上是Java中TreeSet怎麼實作？ （詳解）的詳細內容。更多資訊請關注PHP中文網其他相關文章！