您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 集合深度剖析：TreeSet 原理、源碼與實戰指南

編輯：Java 相關知識

前言

TreeSet 是 Java 集合框架中唯一的有序 Set 實現，底層基於 TreeMap（紅黑樹），提供 O(log n) 的增刪查效能，並支援豐富的導航操作。本文從繼承體系、源碼實現、遍歷方式到實戰範例，全方位解析 TreeSet。

一、TreeSet 核心特性速覽

特性	說明
有序性	元素按自然順序或 `Comparator` 排序
不重複	繼承 `AbstractSet`，基於 `compareTo/compare` 判斷相等
導航支援	實現 `NavigableSet`，提供 floor/ceiling/higher/lower 等精準查找
非同步	多執行緒環境需外部同步或用 `Collections.synchronizedSortedSet`
Fail-fast 迭代器	結構修改時拋出 `ConcurrentModificationException`
序列化/可克隆	實現 `Serializable`、`Cloneable`

二、繼承體系與構造函數

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

TreeSet 與 Collection 體系圖

四大構造函數

// 自然排序
TreeSet()
// 從 Collection 建構（自然排序）
TreeSet(Collection c)
// 自定義比較器
TreeSet(Comparator comparator)
// 從 SortedSet 建構（保留其比較器）
TreeSet(SortedSet s)

三、源碼核心解析（基於 JDK 8）

1. 核心欄位：借用 TreeMap 存儲

private transient NavigableMap m;
private static final Object PRESENT = new Object(); // 虛擬值

設計精髓：TreeSet 不直接存儲元素，而是將元素作為 TreeMap 的 Key，統一 Value 為 PRESENT。所有操作委派給 m。

2. 增刪查核心委派

public boolean add(E e) {
    return m.put(e, PRESENT) == null; // Key 不存在才成功
}

public boolean remove(Object o) {
    return m.remove(o) == PRESENT;
}

public boolean contains(Object o) {
    return m.containsKey(o);
}

public int size() { return m.size(); }
public boolean isEmpty() { return m.isEmpty(); }
public void clear() { m.clear(); }

3. 導航方法：直擊紅黑樹操作

方法	TreeMap 委派	語義
`first()`	`m.firstKey()`	最小元素
`last()`	`m.lastKey()`	最大元素
`lower(e)`	`m.lowerKey(e)`	嚴格小於 e 的最大元素
`floor(e)`	`m.floorKey(e)`	小於等於 e 的最大元素
`ceiling(e)`	`m.ceilingKey(e)`	大於等於 e 的最小元素
`higher(e)`	`m.higherKey(e)`	嚴格大於 e 的最小元素
`pollFirst()`	`m.pollFirstEntry()`	取出並移除最小元素
`pollLast()`	`m.pollLastEntry()`	取出並移除最大元素

4. 子集視圖：零拷貝切片

public NavigableSet subSet(E from, boolean fromInc, E to, boolean toInc) {
    return new TreeSet<>(m.subMap(from, fromInc, to, toInc));
}
public NavigableSet headSet(E to, boolean inclusive) {
    return new TreeSet<>(m.headMap(to, inclusive));
}
public NavigableSet tailSet(E from, boolean inclusive) {
    return new TreeSet<>(m.tailMap(from, inclusive));
}

關鍵點：返回新 TreeSet 共享底層 TreeMap 節點，修改視圖會影響原集合，屬「視圖」而非「快照」。

5. 序列化機制：手寫 writeObject/readObject

private void writeObject(ObjectOutputStream s) throws IOException {
    s.defaultWriteObject();
    s.writeObject(m.comparator()); // 比較器
    s.writeInt(m.size());          // 容量
    for (Iterator i = m.keySet().iterator(); i.hasNext(); )
        s.writeObject(i.next());   // 逐個寫入元素
}

private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
    s.defaultReadObject();
    Comparator c = (Comparator) s.readObject();
    TreeMap tm = (c == null) ? new TreeMap<>() : new TreeMap<>(c);
    m = tm;
    int size = s.readInt();
    tm.readTreeSet(size, s, PRESENT); // 批量讀取重建樹
}

6. addAll 優化：批量構建紅黑樹

public boolean addAll(Collection c) {
    if (m.size() == 0 && c.size() > 0 && c instanceof SortedSet && m instanceof TreeMap) {
        SortedSet set = (SortedSet) c;
        TreeMap map = (TreeMap) m;
        Comparator cc = (Comparator) set.comparator();
        Comparator mc = map.comparator();
        if (cc == mc || (cc != null && cc.equals(mc))) {
            map.addAllForTreeSet(set, PRESENT); // 線性時間批量構建
            return true;
        }
    }
    return super.addAll(c); // 退化為逐個 add
}

當目標為空、來源為 SortedSet 且比較器一致時，直接調用 TreeMap.addAllForTreeSet 以 O(n) 建立平衡樹，避免 O(n log n) 逐個插入。

四、遍歷方式全覽

1. 正序迭代器（推薦）

for (Iterator it = set.iterator(); it.hasNext(); ) {
    E e = it.next();
}

2. 逆序迭代器

for (Iterator it = set.descendingIterator(); it.hasNext(); ) {
    E e = it.next();
}

3. for-each（需轉陣列，不推薦大數據）

String[] arr = set.toArray(new String[0]);
for (String s : arr) { ... }

注意：TreeSet 不支援隨機存取（無 get(index)），僅能透過迭代器遍歷。

五、實戰範例：TreeSetTest.java 核心演示

TreeSet tSet = new TreeSet<>();
tSet.add("aaa"); tSet.add("aaa"); // 去重
tSet.add("bbb"); tSet.add("eee"); tSet.add("ddd"); tSet.add("ccc");
// 輸出：[aaa, bbb, ccc, ddd, eee]

// 導航查找
tSet.floor("bbb");   // "bbb"
tSet.lower("bbb");   // "aaa"
tSet.ceiling("bbb"); // "bbb"
tSet.higher("bbb");  // "ccc"

// 區間視圖
tSet.subSet("aaa", true, "ccc", true);   // [aaa, bbb, ccc]
tSet.subSet("aaa", false, "ccc", false); // [bbb]
tSet.headSet("ccc", true);  // [aaa, bbb, ccc]
tSet.tailSet("ccc", false); // [ddd, eee]

// 彈出操作
tSet.pollFirst(); // 移除並返回 "aaa"
tSet.pollLast();  // 移除並返回 "eee"

六、總結與避坑指南

比較器一致性：自定義 Comparator 必須與 equals 一致，否則違反 Set 契約（如 Comparator 認為 a==b 但 equals 為 false，會導致重複元素存入）。
非線程安全：併發場景用 ConcurrentSkipListSet（無鎖跳表實現）或手動加鎖。
視圖修改回傳：subSet/headSet/tailSet 返回的視圖修改會影響原集合，若需快照請 new TreeSet<>(view)。
Null 元素：自然排序下不允許 null（NullPointerException），自定義 Comparator 可決定是否支援。
效能特徵：add/remove/contains 穩定 O(log n)，適合頻繁查找、範圍查詢、有序輸出場景。

結語

TreeSet 以紅黑樹為底層，將有序性、去重、導航查找完美融合。掌握其「Map 代理存儲」、「視圖零拷貝」、「批量構建優化」等源碼細節，能幫助你在面試與架構設計中遊刃有餘。實戰中，善用 floor/ceiling 解決「最近匹配」問題，用 subSet 實現分頁與區間統計，是 TreeSet 發揮最大價值的關鍵。