小編給大家分享一下Java中TreeSet的實(shí)現(xiàn)方法，希望大家閱讀完這篇文章后大所收獲，下面讓我們一起去探討吧！

成都創(chuàng)新互聯(lián)公司專注于企業(yè)全網(wǎng)營(yíng)銷推廣、網(wǎng)站重做改版、贛縣網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5高端網(wǎng)站建設(shè)、商城網(wǎng)站建設(shè)、集團(tuán)公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站制作、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁(yè)設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為贛縣等各大城市提供網(wǎng)站開(kāi)發(fā)制作服務(wù)。

HashSet是基于HashMap實(shí)現(xiàn)的，那TreeSet會(huì)是怎么實(shí)現(xiàn)的呢？沒(méi)錯(cuò)！和大家想的一樣，它是基于TreeMap實(shí)現(xiàn)的。所以，TreeSet的源碼也很簡(jiǎn)單，主要還是理解TreeMap。

TreeSet的繼承關(guān)系

按照慣例，先來(lái)看TreeSet類的繼承關(guān)系：

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

1. 毫不意外的繼承了抽象類AbstracSet，方便擴(kuò)展；

2. 實(shí)現(xiàn)了一個(gè)NavigableSet接口，和NavigableMap接口類似，提供了各種導(dǎo)航方法；

3. 實(shí)現(xiàn)了Cloneable接口，可以克隆；

4. 實(shí)現(xiàn)了Serializable接口，可以序列化；

這里主要看NavigableSet接口類：

public interface NavigableSet<E> extends SortedSet<E>

熟悉的味道，繼承SortedSet接口。SortedSet則提供了一個(gè)返回比較器的方法：

Comparator<? super E> comparator();

和SortedMap一樣，支持自然排序和自定義排序。自然排序要求添加到Set中的元素實(shí)現(xiàn)Comparable接口，自定義排序要求實(shí)現(xiàn)一個(gè)Comparator比較器。

源碼分析

關(guān)鍵點(diǎn)

關(guān)鍵點(diǎn)自然是TreeSet如何保證元素不重復(fù)以及元素有序的，前面說(shuō)了它是基于TreeMap實(shí)現(xiàn)的，那我們來(lái)看看吧。

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源碼，發(fā)現(xiàn)只有這兩個(gè)屬性（還有個(gè)uid，這里就不算了）。很明顯，m是用來(lái)保存元素的，但m聲明的是NavigableMap而不是TreeMap。可以猜測(cè)，TreeMap應(yīng)該是在構(gòu)造方法里實(shí)例化的，這里使用NavigableMap可以讓TreeSet更加靈活。PRESENT和HashSet中的PRESENT作用一樣，作為固定Value值進(jìn)行占位的。
再看add和remove方法：

public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }

和HashSet的實(shí)現(xiàn)一樣，也是利用了Map保存的Key-Value鍵值對(duì)的Key不會(huì)重復(fù)的特點(diǎn)。

構(gòu)造函數(shù)

果然，TreeSet中的TreeMap是在構(gòu)造函數(shù)中初始化的。

public TreeSet() {
        this(new TreeMap<>()); // 默認(rèn)自然排序的TreeMap
    }
public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator)); // 自定義比較器的TreeMap
    }
public TreeSet(Collection<? extends E> c) {
        this(); // 還是用的默認(rèn)
        addAll(c); // 將元素一個(gè)一個(gè)添加到TreeMap中
    }
 public TreeSet(SortedSet<E> s) {
        this(s.comparator()); // 使用傳入的SortedSet的比較器
        addAll(s); // 一個(gè)一個(gè)添加元素
    }

默認(rèn)實(shí)例化了一個(gè)自然排序的TreeMap，當(dāng)然，我們可以自定義比較器。

這里跟蹤下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; // 強(qiáng)轉(zhuǎn)成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專門(mén)為T(mén)reeSet準(zhǔn)備的方法
                return true;
            }
        }
        return super.addAll(c);
    }

調(diào)用了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，應(yīng)該很熟悉，在TreeMap的文章中分析過(guò)。該方法將傳入的集合元素構(gòu)造成了一棵最底層的結(jié)點(diǎn)為紅色，而其他結(jié)點(diǎn)都是黑色的紅黑樹(shù)。

導(dǎo)航方法

既然實(shí)現(xiàn)了NavigableSet，那各種導(dǎo)航方法自然少不了。它們的實(shí)現(xiàn)也很簡(jiǎn)單，直接調(diào)用m對(duì)應(yīng)的導(dǎo)航方法即可。例如：

public E first() {
        return m.firstKey(); // 返回第一個(gè)元素
    }
public E lower(E e) {
        return m.lowerKey(e); // 返回小于e的第一個(gè)元素
    }
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new TreeSet<>(m.headMap(toElement, inclusive)); // 取前幾個(gè)元素構(gòu)成子集
    }
public E pollFirst() { // 彈出第一個(gè)元素
        Map.Entry<E,?> e = m.pollFirstEntry();
        return (e == null) ? null : e.getKey();
    }
public NavigableSet<E> descendingSet() { // 倒排Set
        return new TreeSet<>(m.descendingMap());
    }
......

這里需要注意的是返回子集合的方法，例如：headSet。返回的子集合是可以添加和刪除元素的，但是有邊界限制，舉個(gè)栗子。

        // 前面構(gòu)造了一個(gè)存儲(chǔ)Int的Set
        // 3、5、7、9
        SortedSet<Integer> subSet = intSet.headSet(8); // 大值7，超過(guò)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也是支持逆序輸出的，因?yàn)橛?code>descendingIterator的實(shí)現(xiàn)：

public Iterator<E> descendingIterator() {
        return m.descendingKeySet().iterator();
    }

總結(jié)

1. TreeSet是基于TreeMap實(shí)現(xiàn)的，支持自然排序和自定義排序，可以進(jìn)行逆序輸出；

2. TreeSet不允許null值；

3. TreeSet不是線程安全的，多線程環(huán)境下可以使用SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...))；

看完了這篇文章，相信你對(duì)Java中TreeSet的實(shí)現(xiàn)方法有了一定的了解，想了解更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！

本文標(biāo)題：Java中TreeSet的實(shí)現(xiàn)方法-創(chuàng)新互聯(lián)
文章路徑：http://www.chinadenli.net/article28/cccijp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、面包屑導(dǎo)航、網(wǎng)站策劃、微信公眾號(hào)、網(wǎng)站導(dǎo)航、網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)