您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

深入解析 Java TreeSet：有序集合的實現原理與核心用法

編輯：Java 綜合教學

TreeSet 核心特性與定位

在上一節中我們介紹了 HashSet，雖然它能高效實現去重，但元素無序是其明顯短板。Java 集合框架提供了另一個關鍵實現 —— TreeSet，它基於紅黑樹結構，天然保證元素有序。與 HashSet 依賴 HashMap 類似，TreeSet 內部封裝了一個 TreeMap，所有操作最終委託給底層映射處理。

基本用法詳解

構造方法選擇

TreeSet 提供兩種核心構造方式：

public TreeSet()
public TreeSet(Comparator<? super E> comparator)

無參構造要求元素實現 Comparable 接口（自然排序）；帶比較器構造則允許自定義排序邏輯，元素無需實現 Comparable。

基礎示例：去重與排序

Set<String> words = new TreeSet<>();
words.addAll(Arrays.asList("tree", "map", "hash", "map"));
for (String w : words) {
    System.out.print(w + " ");
}
// 輸出：hash map tree

程式碼展示了 TreeSet 同時實現「去重」與「升序排列」兩大核心功能。

自定義比較器：忽略大小寫排序

Set<String> words = new TreeSet<>(new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        return o1.compareToIgnoreCase(o2);
    }
});
words.addAll(Arrays.asList("tree", "map", "hash", "Map"));
System.out.println(words);
// 輸出：[hash, map, tree]

關鍵細節：Set 判重依賴比較器返回值，compare() == 0 視為重複。上例中 "map" 與 "Map" 忽略大小寫比較結果為 0，因此僅保留首個元素。

進階功能：有序集合專屬操作

SortedSet 接口：區間視圖與極值訪問

TreeSet 實現 SortedSet，提供豐富的有序操作：

first() / last()：獲取首尾元素
headSet(toElement)：嚴格小於指定值的子集
tailSet(fromElement)：大於等於指定值的子集
subSet(from, to)：[from, to) 區間子集

所有子集方法返回的是視圖，對視圖修改會直接影響原集合。

SortedSet<String> set = new TreeSet<>();
set.addAll(Arrays.asList("c", "a", "b", "d", "f"));
System.out.println(set.first());           // a
System.out.println(set.last());            // f
System.out.println(set.headSet("b"));      // [a]
System.out.println(set.tailSet("d"));      // [d, f]
System.out.println(set.subSet("b", "e"));  // [b, c, d]
set.subSet("b", "e").clear();              // 刪除原集合中區間元素
System.out.println(set);                   // [a, f]

NavigableSet 接口：鄰近查詢與雙向遍歷

NavigableSet 繼承 SortedSet，新增精準邊界控制與反向操作：

floor(e) / lower(e)：≤e / <e 的最大元素
ceiling(e) / higher(e)：≥e / >e 的最小元素
pollFirst() / pollLast()：彈出並移除首尾元素
descendingSet() / descendingIterator()：逆序視圖與迭代器

NavigableSet<String> set = new TreeSet<>();
set.addAll(Arrays.asList("c", "a", "b", "d", "f"));
System.out.println(set.floor("a"));                    // a
System.out.println(set.lower("b"));                    // a
System.out.println(set.ceiling("d"));                  // d
System.out.println(set.higher("c"));                   // d
System.out.println(set.subSet("b", true, "d", true));  // [b, c, d] 含邊界
System.out.println(set.pollFirst());                   // a
System.out.println(set.pollLast());                    // f
System.out.println(set.descendingSet());               // [d, c, b]

構造方法全景

public TreeSet(Collection<? extends E> c)   // 自然排序複製集合
public TreeSet(SortedSet<E> s)              // 複製並繼承比較器
TreeSet(NavigableMap<E, Object> m)          // 內部包裝構造（非 public）

內部實現原理剖析

核心結構

private transient NavigableMap<E, Object> m;
private static final Object PRESENT = new Object();

m 是底層 TreeMap，PRESENT 作為統一佔位值。

關鍵方法委託實現

操作	TreeSet 實現	委託目標
add(e)	`m.put(e, PRESENT) == null`	TreeMap.put()
contains(o)	`m.containsKey(o)`	TreeMap.containsKey()
remove(o)	`m.remove(o) == PRESENT`	TreeMap.remove()
subSet(...)	`new TreeSet<>(m.subMap(...))`	TreeMap.subMap()
first()/last()	`m.firstKey()/lastKey()`	TreeMap.firstKey()/lastKey()
pollFirst()/pollLast()	調用 `m.pollFirstEntry()/pollLastEntry()` 取鍵	TreeMap.pollFirstEntry()/pollLastEntry()
descendingIterator()	`m.descendingKeySet().iterator()`	TreeMap.descendingKeySet()