Java Collection 框架 Set 接口詳解：HashSet、TreeSet、LinkedHashSet 核心原理與選型

Set 是不包含重複元素的集合，對應數學集合概念。Java 提供三大主流實現：HashSet (無序、O(1))、LinkedHashSet (插入序、O(1))、TreeSet (有序、O(log n))。本文深度解析底層數據結構、去重原理、比較器機制、併發陷阱與選型指南。

Set 接口核心契約

• 唯一性：!e1.equals(e2) 對任意兩元素
• 最多一個 null：HashSet/LinkedHashSet 允許一個 null，TreeSet 不允許 (比較拋 NPE)
• 非同步：多線程寫入需外部同步或用 Collections.synchronizedSet / ConcurrentHashMap.newKeySet()

三大實現深度對比

HashSet / LinkedHashSet 去重原理

// HashMap.putVal 邏輯簡化
public boolean add(E e) {
    return map.put(e, PRESENT) == null; // PRESENT = new Object()
}

// 判斷相等兩步驟：
// 1. hashCode() 相同 → 同一桶位
// 2. equals() 返回 true → 認定重複

關鍵規約 (Effective Java Item 11)

1. 覆寫 equals 必須覆寫 hashCode
2. equals 相等 → hashCode 必相等
3. hashCode 相等 ≠ equals 相等 (哈希碰撞)
4. 集合中元素不可變性**：作為 Set 元素/Map Key 的對象，**一旦放入不應修改參與 equals/hashCode 的字段**，否則導致「找不到元素」/內存洩漏

不可變性違反示例

class Person { String name; int age; /* equals/hashCode 基於 name+age */ }
Set set = new HashSet<>();
Person p = new Person("Alice", 20);
set.add(p);
p.setAge(21); // 修改參與 hashCode 的字段！
set.contains(p); // false - 元素「丟失」
set.remove(p);   // false - 無法刪除 → 內存洩漏

TreeSet 排序機制詳解

方式一：自然順序 (元素實現 Comparable)

class Student implements Comparable {
    String name; int score;
    public int compareTo(Student o) {
        // 按分數降序，分數相同按姓名升序
        int cmp = Integer.compare(o.score, this.score);
        return cmp != 0 ? cmp : this.name.compareTo(o.name);
    }
}
Set set = new TreeSet<>(); // 自動按 compareTo 排序

方式二：比較器順序 (構造器注入 Comparator)

// 靜態比較器 (推薦)
static final Comparator BY_NAME_THEN_SCORE = Comparator
    .comparing(Student::getName)
    .thenComparingInt(Student::getScore);

Set set = new TreeSet<>(BY_NAME_THEN_SCORE);
// 或 Lambda 內聯
Set set2 = new TreeSet<>((s1, s2) -> s1.getName().compareTo(s2.getName()));

比較器一致性要求

• compare(x,y) == -compare(y,x) (反對稱)
• compare(x,y)>0 && compare(y,z)>0 → compare(x,z)>0 (傳遞性)
• compare(x,y)==0 → (compare(x,z)==compare(y,z)) (與 equals 一致性，**強烈建議**）
• 違反將導致 TreeSet 行為未定義 (拋異常、死循環、數據錯誤)

併發安全 Set 選型

效能測試基準 (參考)

// JMH 基準測試模板
@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
public class SetBenchmark {
    @Param({"1000", "10000", "100000"}) int size;
    Set hashSet, linkedSet, treeSet;

    @Setup public void setup() {
        hashSet = new HashSet<>(size);
        linkedSet = new LinkedHashSet<>(size);
        treeSet = new TreeSet<>();
        for (int i = 0; i < size; i++) {
            int v = ThreadLocalRandom.current().nextInt();
            hashSet.add(v); linkedSet.add(v); treeSet.add(v);
        }
    }

    @Benchmark public void contains_HashSet(Blackhole bh) { bh.consume(hashSet.contains(500)); }
    @Benchmark public void contains_TreeSet(Blackhole bh) { bh.consume(treeSet.contains(500)); }
    @Benchmark public void iterate_HashSet(Blackhole bh) { for (int v : hashSet) bh.consume(v); }
    @Benchmark public void iterate_LinkedSet(Blackhole bh) { for (int v : linkedSet) bh.consume(v); }
}

選型決策樹

1. **需要排序/範圍查詢** (first/last/headSet/tailSet/subSet) → TreeSet
2. **需要保持插入順序迭代** (LRU 緩存、日誌去重) → LinkedHashSet
3. **純去重、高頻增刪查、無序需求** → HashSet (默認首選)
4. **高併發** → ConcurrentHashMap.newKeySet()
5. **元素不可比較、需自定義排序** → TreeSet + Comparator
6. **元素可能為 null** → 避開 TreeSet

總結

Set 三巨頭各有千秋：**HashSet 通用王者、LinkedHashSet 有序去重、TreeSet 範圍查詢專家**。核心避坑點：元素不可變性、equals/hashCode 契約、TreeSet 比較器一致性、併發場景選型。掌握底層 HashMap/TreeMap 結構，能在面對海量去重、排序、併發場景時做出正確架構決策。

1. 上一篇文章： Java 資源文件路徑載入完整指南：ClassLoader 與 Class.getResource() 深度解析
2. 下一篇文章： Java ZIP 檔案自動解壓縮工具類實作（支援目錄結構保留）

Java 程式設計入門

Java 開發必備：10 個高效調試技巧全解析（Eclipse 實戰演示）

調試前的三條黃金建議 拒絕 System.out.prin

深入理解 Java 陣列記憶體分配：引用變數、堆疊與垃圾回收機制

前言：一個顛覆認知的現象 許多 Java 入門書都說：「基本

J2ME MIDP 開發無線應用入門：架構、生命週期與 UI 元件

前言 J2ME (Java 2 Micro Edition)

Struts + Spring + Hibernate 整合架構：打造鬆耦合 Web 應用完整指南

為什麼需要整合框架？ 構建非簡單 Web 應用時，開發者面臨