上一篇文章中介紹了 Set 接口和它的兩個主要實(shí)現(xiàn)，HashSet 和 LinkedHashSet。回憶一下它們的特點(diǎn)狂男，HashSet 特點(diǎn)是無序，而 LinkedHashSet 則是有有序的品腹，它的順序是按照集合內(nèi)元素的添加順序岖食。
它們具體的內(nèi)部實(shí)現(xiàn)也較為簡單，都是對兩個 Map 數(shù)據(jù)結(jié)構(gòu)的封裝舞吭，應(yīng)該都不難理解泡垃。
今天介紹的數(shù)據(jù)結(jié)構(gòu)也同屬于 Set 接口之下，同樣不能存放相同的元素羡鸥，但是最大的不同之處在于它是有順序的蔑穴，它就是 TreeSet。
SortedSet
在開始分析源碼之前還是先來看看 TreeSet 的類圖：
從類圖上看惧浴，出現(xiàn)了兩個之前沒有見過的接口存和，即 SortedSet 和 NavigableSet 。讓我們先來看看 SortedSet 的注釋和源碼。
注釋給我們提供了以下的這些信息：
-
SortedSet是一個「有序」的集合捐腿，它的順序由Comparable或是Comparator的結(jié)果決定纵朋。這意味著SortedSet容器內(nèi)的元素必須實(shí)現(xiàn)這兩個接口中的任一一個。 - 所有實(shí)現(xiàn)
SortedSet接口的具體類茄袖，需要提供 4 個不同的構(gòu)造函數(shù)操软，這里不再贅述，有興趣的讀者可以直接看這部分的注釋绞佩。 -
SortedSet提供的部分獲取某個范圍元素的方法寺鸥，都是前閉后開的。如果需要兩個都是閉區(qū)間或是開區(qū)間品山，只能通過自己調(diào)整輸入?yún)?shù)來控制。
現(xiàn)在我們已經(jīng)了解了 SortedSet 和 TreeSet 「有順序」的意思了烤低，接著就看看 SortedSet 接口上有哪些有意思的方法肘交。
-
first,last方法分別是返回集合內(nèi)第一個和最后一個元素。 -
headSet(E toElement)返回集合內(nèi)所有小于toElement元素的集合扑馁，注意這里是開區(qū)間涯呻，是「小于」而不是「小于等于」。 -
tailSet(E fromElement)與headSet類似腻要，返回所有大于等于fromElement元素的集合复罐，注意這里是閉區(qū)間，即是「大于等于」雄家。 -
subSet(E fromElement, E toElement)返回fromElement和toElement范圍之間的元素集合效诅，注意這里是前面提到的前閉后開區(qū)間，即「大于等于」fromElement趟济，「小于」toElement元素的集合乱投。
SortedSet 關(guān)鍵方法就這些，準(zhǔn)備進(jìn)入下一個接口 NavigableSet 吧顷编。
NavigableSet
NavigableSet 繼承了 SortedSet 接口戚炫，并增加了數(shù)個方法，讓我們逐一分析媳纬。
新增了 lower(E e)双肤，floor(E e)，ceiling(E e)钮惠，higher(E e) 四個方法茅糜，分別返回集合內(nèi)「小于」，「小于等于」萌腿，「大于等于」限匣，「大于」輸入?yún)?shù)的 e 的元素，如果集合內(nèi)沒有符合條件的參數(shù)，則返回 null米死。
pollFirst() 和 pollLast() 分別返回并移除集合中最小和最大的元素锌历。
重載了父接口 SortedSet 中的 headSet ，tailSet峦筒，subSet 這些方法究西，增加了額外的參數(shù)，控制區(qū)間的閉合物喷，讓方法更加方便使用卤材，具體可以看對應(yīng)的方法簽名和注釋。
剩下值得一提的是 descendingSet 方法峦失，該方法會返回一個當(dāng)前集合降序排列的視圖扇丛，而注釋中也提及通常情況下升序操作的性能好于降序。
TreeSet
其實(shí)寫到這里 TreeSet 本身并沒有太多值得分析的尉辑，因?yàn)樗c HashSet 一樣帆精，真正存儲數(shù)據(jù)，并進(jìn)行各種操作的是代理給了 TreeMap隧魄∽苛罚基本上前面提到的所有方法都是直接掉用了 TreeMap 上的相關(guān)方法」鹤模看下面的代碼片段：
private transient NavigableMap<E,Object> m;
public E last() {
return m.lastKey();
}
public E pollFirst() {
Map.Entry<E,?> e = m.pollFirstEntry();
return (e == null) ? null : e.getKey();
}
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
return new TreeSet<>(m.headMap(toElement, inclusive));
}
額外可以從注釋中了解的就是 add襟企，remove，contains 這幾個方法的時間復(fù)雜度為 log(n)狮含。
下階段預(yù)告
看完 Set 部分的源碼你會發(fā)現(xiàn)其實(shí)大部分?jǐn)?shù)據(jù)結(jié)構(gòu)的操作都是由 Map 這個數(shù)據(jù)結(jié)構(gòu)完成顽悼，包括了 HashMap 和 TreeMap，而 Map 作為開發(fā)人員日常使用頻率最高的數(shù)據(jù)結(jié)構(gòu)之一辉川，可謂是 Java Collections Framework 中最核心的數(shù)據(jù)結(jié)構(gòu)之一表蝙，而它的代碼中也包含了大量必備的數(shù)據(jù)結(jié)構(gòu)知識和算法，在面試中也是被問到最多的乓旗。
很多讀者問我什么時候會開始 Map 源碼的講解府蛇，答案就是現(xiàn)在。從下一篇開始我會開始分析 Map 源碼屿愚，因?yàn)槠渲猩婕暗闹R點(diǎn)很多汇跨，我會寫的非常細(xì)，估計(jì)會有4 ～ 5 篇專門來分析 Map 系列的源碼妆距。如果你希望真正了解和掌握 Java Collections Framework 的一些知識穷遂，我想接下來的文章是不容錯過的。我也歡迎你提出任何問題娱据，我都會回復(fù)你蚪黑。下一篇見！
