Set 接口核心契約
- 唯一性：不包含重複元素 (
e1.equals(e2) 為 true 視為重複)
- 無序性：不保證迭代順序 (除非具體實現類提供順序保證)
- 至多一個 null：最多允許一個 null 元素
- 繼承 Collection：所有方法源自
Collection<E>，但強化了建構子與 add/equals/hashCode 契約
HashSet：雜湊表實現 (O(1) 平均)
核心結構
public class HashSet<E> extends AbstractSet<E>
implements Set<E>, Cloneable, Serializable {
// 底層委派 HashMap，值固定為 PRESENT
private transient HashMap<E, Object> map;
private static final Object PRESENT = new Object();
public HashSet() { map = new HashMap<>(); }
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
// 所有操作轉發 map：add → map.put, remove → map.remove, contains → map.containsKey
}
關鍵特性
- 效能：
add/remove/contains/size 平均 O(1)
- 順序：不保證順序，隨雜湊分佈與擴容而變
- 執行緒不安全：需外部同步或
Collections.synchronizedSet()
- Fail-fast 迭代器：結構性修改拋出
ConcurrentModificationException
- 序列化：自訂
writeObject/readObject 保留雜湊表結構
建構子選項
| 建構子 | 用途 |
|---|
HashSet() | 預設容量 16、負載因子 0.75 |
HashSet(Collection) | 從集合建立，自動去重 |
HashSet(int capacity) | 指定初始容量 |
HashSet(int capacity, float loadFactor) | 完全控制擴容閾值 |
TreeSet：紅黑樹實現 (O(log n) 保證)
核心結構
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, Serializable {
// 底層委派 TreeMap (紅黑樹)
private transient NavigableMap<E, Object> m;
public TreeSet() { this(new TreeMap<>()); } // 自然排序
public TreeSet(Comparator<? super E> c) { this(new TreeMap<>(c)); } // 客製比較器
}
關鍵特性
- 有序性：元素按自然順序 (
Comparable) 或比較器 (Comparator) 排序
- 效能保證：
add/remove/contains O(log n) 最壞情況
- 導航功能：
first/last/lower/floor/ceiling/higher/pollFirst/pollLast
- 範圍視圖：
subSet/headSet/tailSet (含/不含邊界可控)
- 順序一致性要求：比較器判定相等 (
compare==0) 必須與 equals 一致，否則違反 Set 契約
NavigableSet 進階 API 精選
| 方法 | 說明 | 回傳 |
|---|
lower(E e) | 嚴格小於 e 的最大元素 | E 或 null |
floor(E e) | 小於等於 e 的最大元素 | E 或 null |
ceiling(E e) | 大於等於 e 的最小元素 | E 或 null |
higher(E e) | 嚴格大於 e 的最小元素 | E 或 null |
pollFirst() | 取出並移除最小元素 | E 或 null |
pollLast() | 取出並移除最大元素 | E 或 null |
subSet(from, fromInc, to, toInc) | 區間視圖 (可控邊界包含) | NavigableSet |
descendingSet() | 逆序視圖 | NavigableSet |
descendingIterator() | 逆序迭代器 | Iterator |
HashSet vs TreeSet 選型決策表
| 維度 | HashSet | TreeSet |
|---|
| 底層結構 | HashMap (雜湊表) | TreeMap (紅黑樹) |
| 時間複雜度 | 平均 O(1)，最壞 O(n) | 保證 O(log n) |
| 順序 | 無序 | 有序 (自然/比較器) |
| Null 元素 | 允許一個 | 自然排序不允許；比較器視實作而定 |
| 元素需求 | 正確實作 hashCode()/equals() | 實作 Comparable 或提供 Comparator |
| 適用場景 | 去重、快速查找、順序無關 | 區間查詢、排序輸出、最近鄰搜尋、排名系統 |
| 記憶體開銷 | 較低 (陣列+節點) | 較高 (樹節點+指標) |
實戰程式碼範例
public class SetDemo {
public static void main(String[] args) {
// HashSet: 去重 + 快速查找
Set<String> uniqueTags = new HashSet<>();
uniqueTags.addAll(Arrays.asList("java", "spring", "java", "jvm", "spring"));
System.out.println("去重結果: " + uniqueTags); // [jvm, spring, java] 順序不定
// TreeSet: 自動排序 + 區間查詢
Set<Integer> scores = new TreeSet<>();
scores.addAll(Arrays.asList(85, 92, 78, 96, 88, 92));
System.out.println("排序分數: " + scores); // [78, 85, 88, 92, 96]
System.out.println("90分以上: " + scores.tailSet(90, true)); // [92, 96]
System.out.println("前三高: " + scores.descendingSet().stream().limit(3).toList()); // [96, 92, 88]
// 自訂比較器: 字串長度排序
Set<String> byLength = new TreeSet<>(Comparator.comparingInt(String::length));
byLength.addAll(Arrays.asList("a", "abc", "ab", "abcd"));
System.out.println("按長度: " + byLength); // [a, ab, abc, abcd]
}
}
執行緒安全替代方案
Collections.synchronizedSet(new HashSet<>())：鎖住所有方法ConcurrentHashMap.newKeySet() (Java 8+)：高並發、無鎖讀取、弱一致性迭代器CopyOnWriteArraySet：讀多寫少、迭代器快照隔離
