TreeSet

Collection.png

TreeSet是一個(gè)有序的集合，它的作用是提供有序的Set集合。它繼承了AbstractSet抽象類(lèi)，實(shí)現(xiàn)了NavigableSet<E>，Cloneable，Serializable接口。TreeSet是基于TreeMap實(shí)現(xiàn)的，TreeSet的元素支持2種排序方式：自然排序或者根據(jù)提供的Comparator進(jìn)行排序。

TreeSet.png

（1）TreeSet繼承于AbstractSet，并且實(shí)現(xiàn)了NavigableSet接口。
（2）TreeSet是一個(gè)包含有序的且沒(méi)有重復(fù)元素的集合，通過(guò)TreeMap實(shí)現(xiàn)。TreeSet中含有一個(gè)"NavigableMap類(lèi)型的成員變量"m，而m實(shí)際上是"TreeMap的實(shí)例"。

TreeSet用法

public static void demoOne() {
        TreeSet<Person> ts = new TreeSet<>();
        ts.add(new Person("張三", 11));
        ts.add(new Person("李四", 12));
        ts.add(new Person("王五", 15));
        ts.add(new Person("趙六", 21));
        
        System.out.println(ts);
    }

執(zhí)行結(jié)果：會(huì)拋出一個(gè) 異常：java.lang.ClassCastException
顯然是出現(xiàn)了類(lèi)型轉(zhuǎn)換異常。原因在于我們需要告訴TreeSet如何來(lái)進(jìn)行比較元素，如果不指定，就會(huì)拋出這個(gè)異常

如何解決：
如何指定比較的規(guī)則，需要在自定義類(lèi)(Person)中實(shí)現(xiàn)Comparable接口，并重寫(xiě)接口中的compareTo方法

public class Person implements Comparable<Person> {
    private String name;
    private int age;
    ...
    public int compareTo(Person o) {
        return 0;                //當(dāng)compareTo方法返回0的時(shí)候集合中只有一個(gè)元素
        return 1;                //當(dāng)compareTo方法返回正數(shù)的時(shí)候集合會(huì)怎么存就怎么取
        return -1;                //當(dāng)compareTo方法返回負(fù)數(shù)的時(shí)候集合會(huì)倒序存儲(chǔ)
    }
}

為什么返回0，只會(huì)存一個(gè)元素，返回-1會(huì)倒序存儲(chǔ)，返回1會(huì)怎么存就怎么取呢？原因在于TreeSet底層其實(shí)是一個(gè)二叉樹(shù)機(jī)構(gòu)，且每插入一個(gè)新元素(第一個(gè)除外)都會(huì)調(diào)用compareTo()方法去和上一個(gè)插入的元素作比較，并按二叉樹(shù)的結(jié)構(gòu)進(jìn)行排列。

1. 如果將compareTo()返回值寫(xiě)死為0，元素值每次比較，都認(rèn)為是相同的元素，這時(shí)就不再向TreeSet中插入除第一個(gè)外的新元素。所以TreeSet中就只存在插入的第一個(gè)元素。
2. 如果將compareTo()返回值寫(xiě)死為1，元素值每次比較，都認(rèn)為新插入的元素比上一個(gè)元素大，于是二叉樹(shù)存儲(chǔ)時(shí)，會(huì)存在根的右側(cè)，讀取時(shí)就是正序排列的。
3. 如果將compareTo()返回值寫(xiě)死為-1，元素值每次比較，都認(rèn)為新插入的元素比上一個(gè)元素小，于是二叉樹(shù)存儲(chǔ)時(shí)，會(huì)存在根的左側(cè)，讀取時(shí)就是倒序序排列的。

示例代碼，需求：現(xiàn)在要制定TreeSet中按照String長(zhǎng)度比較String。

//定義一個(gè)類(lèi)，實(shí)現(xiàn)Comparator接口，并重寫(xiě)compare()方法，
class CompareByLength implements Comparator<String> {

    @Override
    public int compare(String s1, String s2) {        //按照字符串的長(zhǎng)度比較
        int num = s1.length() - s2.length();        //長(zhǎng)度為主要條件
        return num == 0 ? s1.compareTo(s2) : num;    //內(nèi)容為次要條件
    }
}

 public static void demoTwo() {

        //需求:將字符串按照長(zhǎng)度排序
        TreeSet<String> ts = new TreeSet<>(new CompareByLen());        //Comparator c = new CompareByLen();
        ts.add("aaaaaaaa");
        ts.add("z");
        ts.add("wc");
        ts.add("nba");
        ts.add("cba");
        
        System.out.println(ts);
    }

TreeSet的部分源碼:

package java.util;

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    // 使用NavigableMap對(duì)象的key來(lái)保存Set集合的元素
    private transient NavigableMap<E,Object> m;

    //使用PRESENT作為Map集合中的value
    private static final Object PRESENT = new Object();

    // 不帶參數(shù)的構(gòu)造函數(shù)。創(chuàng)建一個(gè)空的TreeMap
    //以自然排序方法創(chuàng)建一個(gè)新的TreeMap，再根據(jù)該TreeMap創(chuàng)建一個(gè)TreeSet
    //使用該TreeMap的key來(lái)保存Set集合的元素
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

    // 將TreeMap賦值給 "NavigableMap對(duì)象m"
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

    //以定制排序的方式創(chuàng)建一個(gè)新的TreeMap。根據(jù)該TreeMap創(chuàng)建一個(gè)TreeSet
    //使用該TreeMap的key來(lái)保存set集合的元素
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<E,Object>(comparator));
    }

    // 創(chuàng)建TreeSet，并將集合c中的全部元素都添加到TreeSet中
    public TreeSet(Collection<? extends E> c) {
        this();
        // 將集合c中的元素全部添加到TreeSet中
        addAll(c);
    }

    // 創(chuàng)建TreeSet，并將s中的全部元素都添加到TreeSet中
    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }

    // 返回TreeSet的順序排列的迭代器。
    // 因?yàn)門(mén)reeSet時(shí)TreeMap實(shí)現(xiàn)的，所以這里實(shí)際上時(shí)返回TreeMap的“鍵集”對(duì)應(yīng)的迭代器
    public Iterator<E> iterator() {
        return m.navigableKeySet().iterator();
    }

    // 返回TreeSet的逆序排列的迭代器。
    // 因?yàn)門(mén)reeSet時(shí)TreeMap實(shí)現(xiàn)的，所以這里實(shí)際上時(shí)返回TreeMap的“鍵集”對(duì)應(yīng)的迭代器
    public Iterator<E> descendingIterator() {
        return m.descendingKeySet().iterator();
    }

    // 返回TreeSet的大小
    public int size() {
        return m.size();
    }

    // 返回TreeSet是否為空
    public boolean isEmpty() {
        return m.isEmpty();
    }

    // 返回TreeSet是否包含對(duì)象(o)
    public boolean contains(Object o) {
        return m.containsKey(o);
    }

    // 添加e到TreeSet中
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

    // 刪除TreeSet中的對(duì)象o
    public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }

    // 清空TreeSet
    public void clear() {
        m.clear();
    }

    // 將集合c中的全部元素添加到TreeSet中
    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) {
            //把C集合強(qiáng)制轉(zhuǎn)換為SortedSet集合
            SortedSet<? extends E> set = (SortedSet<? extends E>) c; 
             //把m集合強(qiáng)制轉(zhuǎn)換為T(mén)reeMap集合
            TreeMap<E,Object> map = (TreeMap<E, Object>) m;
            Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
            Comparator<? super E> mc = map.comparator();
            //如果cc和mc兩個(gè)Comparator相等
            if (cc==mc || (cc != null && cc.equals(mc))) {
            //把Collection中所有元素添加成TreeMap集合的key
                map.addAllForTreeSet(set, PRESENT);
                return true;
            }
        }
        return super.addAll(c);
    }

    // 返回子Set，實(shí)際上是通過(guò)TreeMap的subMap()實(shí)現(xiàn)的。
    public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                                  E toElement,   boolean toInclusive) {
        return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
                                       toElement,   toInclusive));
    }

    // 返回Set的頭部，范圍是：從頭部到toElement。
    // inclusive是是否包含toElement的標(biāo)志
    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new TreeSet<E>(m.headMap(toElement, inclusive));
    }

    // 返回Set的尾部，范圍是：從fromElement到結(jié)尾。
    // inclusive是是否包含fromElement的標(biāo)志
    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
        return new TreeSet<E>(m.tailMap(fromElement, inclusive));
    }

    // 返回子Set。范圍是：從fromElement(包括)到toElement(不包括)。
    public SortedSet<E> subSet(E fromElement, E toElement) {
        return subSet(fromElement, true, toElement, false);
    }

    // 返回Set的頭部，范圍是：從頭部到toElement(不包括)。
    public SortedSet<E> headSet(E toElement) {
        return headSet(toElement, false);
    }

    // 返回Set的尾部，范圍是：從fromElement到結(jié)尾(不包括)。
    public SortedSet<E> tailSet(E fromElement) {
        return tailSet(fromElement, true);
    }

    // 返回Set的比較器
    public Comparator<? super E> comparator() {
        return m.comparator();
    }

    // 返回Set的第一個(gè)元素
    public E first() {
        return m.firstKey();
    }

    // 返回Set的最后一個(gè)元素
    public E first() {
    public E last() {
        return m.lastKey();
    }

    // 返回Set中小于e的最大元素
    public E lower(E e) {
        return m.lowerKey(e);
    }

    // 返回Set中小于/等于e的最大元素
    public E floor(E e) {
        return m.floorKey(e);
    }

    // 返回Set中大于/等于e的最小元素
    public E ceiling(E e) {
        return m.ceilingKey(e);
    }

    // 返回Set中大于e的最小元素
    public E higher(E e) {
        return m.higherKey(e);
    }

    // 獲取第一個(gè)元素，并將該元素從TreeMap中刪除。
    public E pollFirst() {
        Map.Entry<E,?> e = m.pollFirstEntry();
        return (e == null)? null : e.getKey();
    }

    // 獲取最后一個(gè)元素，并將該元素從TreeMap中刪除。
    public E pollLast() {
        Map.Entry<E,?> e = m.pollLastEntry();
        return (e == null)? null : e.getKey();
    }

    // 克隆一個(gè)TreeSet，并返回Object對(duì)象
    public Object clone() {
        TreeSet<E> clone = null;
        try {
            clone = (TreeSet<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }

        clone.m = new TreeMap<E,Object>(m);
        return clone;
    }

    // java.io.Serializable的寫(xiě)入函數(shù)
    // 將TreeSet的“比較器、容量，所有的元素值”都寫(xiě)入到輸出流中
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        s.defaultWriteObject();

        // 寫(xiě)入比較器
        s.writeObject(m.comparator());

        // 寫(xiě)入容量
        s.writeInt(m.size());

        // 寫(xiě)入“TreeSet中的每一個(gè)元素”
        for (Iterator i=m.keySet().iterator(); i.hasNext(); )
            s.writeObject(i.next());
    }

    // java.io.Serializable的讀取函數(shù)：根據(jù)寫(xiě)入方式讀出
    // 先將TreeSet的“比較器、容量、所有的元素值”依次讀出
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden stuff
        s.defaultReadObject();

        // 從輸入流中讀取TreeSet的“比較器”
        Comparator<? super E> c = (Comparator<? super E>) s.readObject();

        TreeMap<E,Object> tm;
        if (c==null)
            tm = new TreeMap<E,Object>();
        else
            tm = new TreeMap<E,Object>(c);
        m = tm;

        // 從輸入流中讀取TreeSet的“容量”
        int size = s.readInt();

        // 從輸入流中讀取TreeSet的“全部元素”
        tm.readTreeSet(size, s, PRESENT);
    }

    // TreeSet的序列版本號(hào)
    private static final long serialVersionUID = -2479143000061671589L;
}

從上述可以看出，TreeSet的構(gòu)造函數(shù)都是通過(guò)新建一個(gè)TreeMap作為實(shí)際存儲(chǔ)Set元素的容器。因此得出結(jié)論: TreeSet的底層實(shí)際使用的存儲(chǔ)容器就是TreeMap。
對(duì)于TreeMap而言，它采用一種被稱為”紅黑樹(shù)”的排序二叉樹(shù)來(lái)保存Map中每個(gè)Entry。每個(gè)Entry被當(dāng)成”紅黑樹(shù)”的一個(gè)節(jié)點(diǎn)來(lái)對(duì)待。

對(duì)于如下代碼:

TreeMap<String,Double> map = new TreeMap<String,Double>();
map.put("ccc",89.0);
map.put("aaa",80.0);
map.put("bbb",89.0);
map.put("bbb",89.0);

如上代碼所示，程序向TreeMap放入四個(gè)值。根據(jù)”紅黑樹(shù)”的定義，程序會(huì)把”ccc,89.0”這個(gè)Entry做為該”紅黑數(shù)”的根節(jié)點(diǎn)，然后執(zhí)行put(“aaa”,”80.0”)時(shí)會(huì)將其作為新的節(jié)點(diǎn)添加到已存在的紅黑樹(shù)中。也就是說(shuō)，以后每次向TreeMap中放入一個(gè)key-value對(duì)，系統(tǒng)都需要將Entry當(dāng)成一個(gè)新的節(jié)點(diǎn)，添加到存在的”紅黑樹(shù)”中，通過(guò)這種方式就可以保證TreeMap中所有的key都是按一定順序地排列的。

由于TreeMap底層采用一顆”紅黑樹(shù)”來(lái)保存集合中的Entry。所以TreeMap添加元素，取出元素的性能都比HashMap低。當(dāng)TreeMap添加元素時(shí)，需要通過(guò)循環(huán)找到新增的Entry的插入位置，因?yàn)楸容^耗性能。當(dāng)取出元素時(shí)，也需要通過(guò)循環(huán)才能找到合適的Entry一樣比較耗性能。但并不是說(shuō)TreeMap性能低于HashMap就一無(wú)是處，TreeMap中的所有Entry總是按key根據(jù)指定的排序規(guī)則保持有序狀態(tài)。

備注:紅黑樹(shù)是一種自平衡二叉查找樹(shù) , 它們當(dāng)中每一個(gè)節(jié)點(diǎn)的比較值都必須大于或等于在它的左子樹(shù)中的所有節(jié)點(diǎn)，并且小于或等于在它的右子樹(shù)中的所有節(jié)點(diǎn)。這確保紅黑樹(shù)運(yùn)作時(shí)能夠快速的在樹(shù)中查找給定的值。

現(xiàn)在我們來(lái)觀察TreeMap的put(K key,V value)方法，該方法將Entry放入TreeMap的Entry鏈，并維護(hù)該Entry鏈的有序狀態(tài)。下面列出源碼:

public V put(K key, V value) {
      //定義一個(gè)t來(lái)保存根元素
        Entry<K,V> t = root;
        //如果t==null，表明是一個(gè)空鏈表
        if (t == null) {
        //如果根節(jié)點(diǎn)為null，將傳入的鍵值對(duì)構(gòu)造成根節(jié)點(diǎn)（根節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)，所以傳入的父節(jié)點(diǎn)為null）
            root = new Entry<K,V>(key, value, null);
            //設(shè)置該集合的size為1
            size = 1;
            //修改此時(shí)+1
            modCount++;
            return null;
        }
        // 記錄比較結(jié)果
        int cmp;
        Entry<K,V> parent;
        // 分割比較器和可比較接口的處理
        Comparator<? super K> cpr = comparator;
        // 有比較器的處理，即采用定制排序
        if (cpr != null) {
            // do while實(shí)現(xiàn)在root為根節(jié)點(diǎn)移動(dòng)尋找傳入鍵值對(duì)需要插入的位置
            do {
                //使用parent上次循環(huán)后的t所引用的Entry
                // 記錄將要被摻入新的鍵值對(duì)將要節(jié)點(diǎn)(即新節(jié)點(diǎn)的父節(jié)點(diǎn))
                parent = t;
                // 使用比較器比較父節(jié)點(diǎn)和插入鍵值對(duì)的key值的大小
                cmp = cpr.compare(key, t.key);
                // 插入的key較大
                if (cmp < 0)
                    t = t.left;
                // 插入的key較小
                else if (cmp > 0)
                    t = t.right;
                // key值相等，替換并返回t節(jié)點(diǎn)的value(put方法結(jié)束)
                else
                    return t.setValue(value);
            } while (t != null);
        }
        // 沒(méi)有比較器的處理
        else {
            // key為null拋出NullPointerException異常
            if (key == null)
                throw new NullPointerException();
            Comparable<? super K> k = (Comparable<? super K>) key;
            // 與if中的do while類(lèi)似，只是比較的方式不同
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        // 沒(méi)有找到key相同的節(jié)點(diǎn)才會(huì)有下面的操作
        // 根據(jù)傳入的鍵值對(duì)和找到的“父節(jié)點(diǎn)”創(chuàng)建新節(jié)點(diǎn)
        Entry<K,V> e = new Entry<K,V>(key, value, parent);
        // 根據(jù)最后一次的判斷結(jié)果確認(rèn)新節(jié)點(diǎn)是“父節(jié)點(diǎn)”的左孩子還是又孩子
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        // 對(duì)加入新節(jié)點(diǎn)的樹(shù)進(jìn)行調(diào)整
        fixAfterInsertion(e);
        // 記錄size和modCount
        size++;
        modCount++;
        // 因?yàn)槭遣迦胄鹿?jié)點(diǎn)，所以返回的是null
        return null;
    }

上面程序中的兩個(gè)do…while就是實(shí)現(xiàn)”排序二叉樹(shù)”的關(guān)鍵算法。每當(dāng)程序希望添加新節(jié)點(diǎn)時(shí)，總是從樹(shù)的根節(jié)點(diǎn)開(kāi)始比較，即將根節(jié)點(diǎn)當(dāng)成當(dāng)前節(jié)點(diǎn)。

• 如果新增節(jié)點(diǎn)大于當(dāng)前節(jié)點(diǎn)且當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)存在，則以右子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)。并繼續(xù)循環(huán)
• 如果新增節(jié)點(diǎn)小于當(dāng)前節(jié)點(diǎn)且當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)存在，則以左子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)。并繼續(xù)循環(huán)
• 如果新增節(jié)點(diǎn)等于當(dāng)前節(jié)點(diǎn)，則新增節(jié)點(diǎn)覆蓋當(dāng)前節(jié)點(diǎn)，并結(jié)束循環(huán)。

當(dāng)TreeMap根據(jù)key來(lái)取出value時(shí)，TreeMap對(duì)應(yīng)的方法如下:

public V get(Object key) {
     //根據(jù)key取出Entry
     Entry<K,V> p = getEntry(key);
     //取出Entry所包含的value
     return (p==null ? null : p.value);
 }

現(xiàn)在我們可以知道，其實(shí)get(Object key)方法實(shí)質(zhì)上是由getEntry()方法實(shí)現(xiàn)的。現(xiàn)在我們來(lái)看getEntry(Object key)的源碼:

final Entry<K,V> getEntry(Object key) {
    // 如果有比較器，返回getEntryUsingComparator(Object key)的結(jié)果
    if (comparator != null)
        return getEntryUsingComparator(key);
    // 查找的key為null，拋出NullPointerException
    if (key == null)
        throw new NullPointerException();
    // 如果沒(méi)有比較器，而是實(shí)現(xiàn)了可比較接口
    //將key強(qiáng)制轉(zhuǎn)換為Comparable接口
    Comparable<? super K> k = (Comparable<? super K>) key;
    // 獲取根節(jié)點(diǎn)
    Entry<K,V> p = root;
    // 從根節(jié)點(diǎn)開(kāi)始對(duì)樹(shù)進(jìn)行遍歷查找節(jié)點(diǎn)
    while (p != null) {
        // 把key和當(dāng)前節(jié)點(diǎn)的key進(jìn)行比較
        int cmp = k.compareTo(p.key);
        // key小于當(dāng)前節(jié)點(diǎn)的key
        if (cmp < 0)
            // p “移動(dòng)”到左節(jié)點(diǎn)上
            p = p.left;
        // key大于當(dāng)前節(jié)點(diǎn)的key
        else if (cmp > 0)
        // p “移動(dòng)”到右節(jié)點(diǎn)上
　　　　p = p.right;
        // key值相等則當(dāng)前節(jié)點(diǎn)就是要找的節(jié)點(diǎn)
        else
            // 返回找到的節(jié)點(diǎn)
            return p;
        }
    // 沒(méi)找到則返回null
    return null;
}

getEntry(Object obj)方法也是充分利用排序二叉樹(shù)的特性來(lái)搜索目標(biāo)Entry。程序依然從二叉數(shù)的根節(jié)點(diǎn)開(kāi)始，如果被搜索節(jié)點(diǎn)大于當(dāng)前節(jié)點(diǎn)，程序向”右子樹(shù)”搜索，如果小于，則向”左子樹(shù)”搜索。如果相等則說(shuō)明找到了指定節(jié)點(diǎn)。

我們觀察到當(dāng)該TreeMap采用了定制排序。在采用定制排序的方式下，TreeMap采用getEntryUsingComparator(key)方法來(lái)根據(jù)key獲取Entry。

final Entry<K,V> getEntryUsingComparator(Object key) {
    K k = (K) key;
    // 獲取比較器
Comparator<? super K> cpr = comparator;
// 其實(shí)在調(diào)用此方法的get(Object key)中已經(jīng)對(duì)比較器為null的情況進(jìn)行判斷，這里是防御性的判斷
if (cpr != null) {
    // 獲取根節(jié)點(diǎn)
        Entry<K,V> p = root;
        // 遍歷樹(shù)
        while (p != null) {
            // 獲取key和當(dāng)前節(jié)點(diǎn)的key的比較結(jié)果
            int cmp = cpr.compare(k, p.key);
            // 查找的key值較小
            if (cmp < 0)
                // p“移動(dòng)”到左孩子
                p = p.left;
            // 查找的key值較大
            else if (cmp > 0)
                // p“移動(dòng)”到右節(jié)點(diǎn)
                p = p.right;
            // key值相等
            else
                // 返回找到的節(jié)點(diǎn)
                return p;
        }
}
// 沒(méi)找到key值對(duì)應(yīng)的節(jié)點(diǎn)，返回null
    return null;
}

其實(shí)getEntry()和getEntryUsingComparator()這兩個(gè)方法實(shí)現(xiàn)思路幾乎完全類(lèi)似。只是前者對(duì)自然排序的TreeMap獲取有效，后者對(duì)定制排序的TreeMap有效。

通過(guò)上述源碼其實(shí)不難看出，TreeMap這個(gè)工具類(lèi)的實(shí)現(xiàn)其實(shí)很簡(jiǎn)單。或者說(shuō)，從本質(zhì)上來(lái)說(shuō)TreeMap就是一棵”紅黑樹(shù)”，每個(gè)Entry就是一個(gè)節(jié)點(diǎn)。

總結(jié)

1、不能有重復(fù)的元素；
2、具有排序功能；
3、TreeSet中的元素必須實(shí)現(xiàn)Comparable接口并重寫(xiě)compareTo()方法，TreeSet判斷元素是否重復(fù) 、以及確定元素的順序 靠的都是這個(gè)方法；
①對(duì)于Java類(lèi)庫(kù)中定義的類(lèi)，TreeSet可以直接對(duì)其進(jìn)行存儲(chǔ)，如String，Integer等,因?yàn)檫@些類(lèi)已經(jīng)實(shí)現(xiàn)了Comparable接口);
②對(duì)于自定義類(lèi)，如果不做適當(dāng)?shù)奶幚?，TreeSet中只能存儲(chǔ)一個(gè)該類(lèi)型的對(duì)象實(shí)例，否則無(wú)法判斷是否重復(fù)。
4、依賴TreeMap。
5、相對(duì)HashSet,TreeSet的優(yōu)勢(shì)是有序，劣勢(shì)是相對(duì)讀取慢。根據(jù)不同的場(chǎng)景選擇不同的集合。