本博客將從源碼的角度帶領(lǐng)大家學(xué)習(xí)TreeSet相關(guān)的知識。

一TreeSet類的定義：

public class TreeSet<E> extends AbstractSet<E>implements NavigableSet<E>, Cloneable, java.io.Serializable可以看到TreeSet是繼承自AbstracSet同時實現(xiàn)了NavigableSet，Cloneable，Serializable三個接口，其中Cloneable，Serializable這兩個接口基本上是java集合框架中所有的集合類都要實現(xiàn)的接口。

二TreeSet中的重要屬性：

private transient NavigableMap<E,Object> m;private static final Object PRESENT = new Object();可以看到第一個屬性是NavigableMap接口，該接口是TreeMap的父接口，即TreeMap實現(xiàn)了該接口，據(jù)此我們可以推測TreeSet的底層是基于TreeMap的，這一點稍后我們將在TreeSet的構(gòu)造器中更清楚的看到。第二個參數(shù)是以O(shè)bject對象，與HashSet中的這個屬性完全相同，即TreeSet雖然底層是基于TreeMap的，但是同樣只是用來保存Key而Value值全部為默認值PRESENT。

三TreeSet內(nèi)部實現(xiàn)原理：我們來看一下TreeSet的構(gòu)造器:

TreeSet(NavigableMap<E,Object> m) {this.m = m;}public TreeSet() {this(new TreeMap<E,Object>());}public TreeSet(Collection<? extends E> c) {this();addAll(c);}public TreeSet(Collection<? extends E> c) {this();addAll(c);}public TreeSet(SortedSet<E> s) {this(s.comparator());addAll(s);}可以看到共5個構(gòu)造器，其中第一個構(gòu)造器是私有的，即對外不公開的，而在第二個默認的無參數(shù)的構(gòu)造器中調(diào)用了第一個構(gòu)造器，且可以清楚的看到在這個構(gòu)造器中創(chuàng)建了一個TreeMap對象作為參數(shù)傳給第一個構(gòu)造器，這說明我們上面的推測：TreeSet底層是基于TreeMap的是正確的。另外余下的幾個構(gòu)造器中可以看到當(dāng)用一個集合作為參數(shù)去構(gòu)造一個TreeSet的時候，都是調(diào)用addAll這個方法，我們來看一下其源碼：

public boolean addAll(Collection<? extends E> c) {// Use linear-time version if applicableif (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;Comparator<?> cc = set.comparator();Comparator<? super E> mc = map.comparator();if (cc==mc || (cc != null && cc.equals(mc))) {map.addAllForTreeSet(set, PRESENT);return true;}}return super.addAll(c);}public boolean addAll(Collection<? extends E> c) {boolean modified = false;for (E e : c)if (add(e))modified = true;return modified;}public boolean add(E e) {return m.put(e, PRESENT)==null;}
可以看到在addAll方法中首先會判斷是否傳入的集合參數(shù)c是否為SortedSet或其子類且c不為空(c.size()>0)，如果是則會調(diào)用addAllForTreeSet方法，否則會直接返回addAll方法的結(jié)果，關(guān)于addAll方法請參看我的博客 【java集合框架源碼剖析系列】java源碼剖析之HashSet相關(guān)內(nèi)容，因為內(nèi)容相同，在此不做贅述，重點來看一下addAllForTreeSet方法：

void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {try {buildFromSorted(set.size(), set.iterator(), null, defaultVal);} catch (java.io.IOException cannotHappen) {} catch (ClassNotFoundException cannotHappen) {}}private void buildFromSorted(int size, Iterator<?> it,java.io.ObjectInputStream str,V defaultVal)throws java.io.IOException, ClassNotFoundException {this.size = size;root = buildFromSorted(0, 0, size-1, computeRedLevel(size),it, str, defaultVal);} 可以看到在addAllForTreeSet方法中調(diào)用了buildFromSorted(int size, Iterator<?> it, java.io.ObjectInputStream str,V defaultVal)，該方法的作用即是在線性時間內(nèi)對數(shù)據(jù)進行排序（Linear time tree building algorithm from sorted data），看到這里我們就明白TreeSet排序的原理了，即當(dāng)使用一個TreeMap集合作為參數(shù)構(gòu)造一個TreeSet的時候，TreeSet會將Map中的元素先排序，然后將排序后的元素add到TreeSet中。也就是說TreeSet中的元素都是排過序的，另外正因為存在排序過程，所以TreeSet不允許插入null值，因為null值不能排序。

四TreeSet中的重要方法：

<strong> </strong>public boolean add(E e) {return m.put(e, PRESENT)==null;}public boolean remove(Object o) {return m.remove(o)==PRESENT;}public void clear() {m.clear();}public boolean contains(Object o) {return m.containsKey(o);}public E first() {return m.firstKey();}public E last() {return m.lastKey();}可以看到TreeSet中與TreeMap中同名的方法全部都是調(diào)用的TreeMap中的方法來實現(xiàn)的，其中add方法在調(diào)用TreeMap的put方法時第二個參數(shù)傳入的是固定值PRESENT，一個Object類型對象。

五總結(jié)：經(jīng)過前面TreeMap的源碼剖析可以看到TreeSet非常簡單

1TreeSet底層是基于TreeMap的（而TreeMap是基于紅黑樹的），但是僅僅用來保存Key，而不保存Value，因為TreeSet的add()方法在調(diào)用TreeMap的put方法的時候第二個參數(shù)傳入的都是PRESENT這個固定的Object對象。
2可以看到TreeSet中的add與remove等方法均無synchronized關(guān)鍵字修飾，即TreeSet不是線程安全的，如果要使用同步的TreeSet需要使用Collections集合類的靜態(tài)方法，即Set s=Collections.synchronizedSet(new TreeSet());
3TreeSet中的元素是自動排好序的，插入的值不允許為null。

4TreeSet中元素的值必須是唯一的，因為TreeSet底層是基于TreeMap的，而TreeMap不允許元素key重復(fù)。

總結(jié)

以上是生活随笔為你收集整理的【java集合框架源码剖析系列】java源码剖析之TreeSet的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。