Java 集合源碼系列（六）：TreeSet 基於 TreeMap 實現的有序集合深度解析

TreeSet 定位

• 有序、不重複集合
• 繼承 AbstractSet，實現 NavigableSet<E>、Cloneable、Serializable
• 底層委託 TreeMap 實現，元素作為 TreeMap 的 key，value 統一為 PRESENT 常量

構造函數族

// 自然排序
public TreeSet() { this(new TreeMap<E,Object>()); }

// 指定 Comparator
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<E,Object>(comparator));
}

// 集合轉換
public TreeSet(Collection<? extends E> c) { this(); addAll(c); }
public TreeSet(SortedSet<E> s) { this(s.comparator()); addAll(s); }

核心 API 分類

源碼核心邏輯：全部委託 TreeMap

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

public boolean add(E e) { return m.put(e, PRESENT) == null; }
public boolean remove(Object o) { return m.remove(o) == PRESENT; }
public Iterator<E> iterator() { return m.navigableKeySet().iterator(); }
public E first() { return m.firstKey(); }
public E lower(E e) { return m.lowerKey(e); }
public NavigableSet<E> subSet(E from, boolean fromInc, E to, boolean toInc) {
    return new TreeSet<E>(m.subMap(from, fromInc, to, toInc));
}
// 序列化：寫入 comparator、size、所有元素
// 反序列化：讀取 comparator、size、逐個添加元素

關鍵特性總結

• 有序性：自然排序或 Comparator 定制，O(log n) 基本操作
• 非線程安全：多線程需外部同步或用 Collections.synchronizedSortedSet
• Fail-fast 迭代器：結構修改時拋 ConcurrentModificationException
• 序列化支援：保存比較器、容量、元素序列

TreeSet vs HashSet vs LinkedHashSet