Java 從 Set 獲取有序元素完全指南：TreeSet、LinkedHashSet 與 Comparator 實戰

核心結論

HashSet 無序，每次迭代順序不可預期。需有序 Set 必須使用：

• TreeSet：自然排序 / 定制排序（紅黑樹，O(log n)）
• LinkedHashSet：插入順序 / 訪問順序（雙向鏈表 + HashMap，O(1)）

HashSet vs TreeSet 直觀對比

public class SetOrderDemo {
    public static void main(String[] args) {
        useHashSet();
        useTreeSet();
    }

    static void useHashSet() {
        Set set = new HashSet<>();
        for (int i = 1; i <= 10; i++) set.add(new User(i, "uname" + i, "pswd" + i));
        System.out.println("--- HashSet (無序) ---");
        set.forEach(System.out::println);
    }

    static void useTreeSet() {
        Set set = new TreeSet<>(); // User2 實現 Comparable
        for (int i = 1; i <= 10; i++) set.add(new User2(i, "uname" + i, "pswd" + i));
        System.out.println("--- TreeSet (按 id 升序) ---");
        set.forEach(System.out::println);
    }
}

// 普通 POJO，無 Comparable
class User { int id; String username, password; ... }

// 實現 Comparable，按 id 排序
class User2 implements Comparable {
    int id; String username, password; ...
    @Override public int compareTo(User2 o) {
        return Integer.compare(this.id, o.id); // 升序
    }
}

運行結果

--- HashSet (無序) ---
User{id=3, username='uname3', password='pswd3'}
User{id=4, username='uname4', password='pswd4'}
User{id=1, username='uname1', password='pswd1'}
... (每次運行順序不同)

--- TreeSet (按 id 升序) ---
User2{id=1, username='uname1', password='pswd1'}
User2{id=2, username='uname2', password='pswd2'}
...
User2{id=10, username='uname10', password='pswd10'}

三大有序 Set 實現深度解析

TreeSet 進階用法

1. 定制 Comparator（外部排序邏輯）

// 降序
Set descSet = new TreeSet<>(Comparator.comparingInt(User2::getId).reversed());

// 多字段排序：先按 username 升序，再按 id 降序
Set multiSet = new TreeSet<>(
    Comparator.comparing(User2::getUsername)
              .thenComparing(Comparator.comparingInt(User2::getId).reversed())
);

2. 導航方法 (NavigableSet)

TreeSet scores = new TreeSet<>(Arrays.asList(10, 50, 30, 70, 90));

scores.lower(50);    // < 50 最大元素 → 30
scores.floor(50);    // ≤ 50 最大元素 → 50
scores.higher(50);   // > 50 最小元素 → 70
scores.ceiling(50);  // ≥ 50 最小元素 → 50

scores.first();      // 最小 → 10
scores.last();       // 最大 → 90

scores.pollFirst();  // 移除並返回最小 → 10
scores.pollLast();   // 移除並返回最大 → 90

scores.subSet(30, true, 70, false); // [30, 70) → [30, 50]
scores.headSet(50, true);           // ≤ 50 → [10, 30, 50]
scores.tailSet(50, false);          // > 50 → [70, 90]

3. 避坑指南

• **元素不可變性**：加入 TreeSet 後，**不能修改影響比較的字段**，否則破壞樹結構導致查找失效
• **compareTo 與 equals 一致性**：`e1.compareTo(e2) == 0` 應等價於 `e1.equals(e2)`，否則違反 Set 語義（如 BigDecimal "1.0" vs "1.00"）
• **null 元素**：TreeSet 不允許 null（比較拋 NPE），LinkedHashSet 允許單個 null

LinkedHashSet：保持插入順序

Set linked = new LinkedHashSet<>();
linked.add("C");
linked.add("A");
linked.add("B");
linked.add("A"); // 重複忽略
System.out.println(linked); // [C, A, B] - 保持首次插入順序

// 訪問順序模式 (access-order) - 適合 LRU 緩存
Set lru = new LinkedHashSet<>(16, 0.75f, true); // 第三參數 true=訪問順序
lru.add("A"); lru.add("B"); lru.add("C");
lru.contains("A"); // 訪問 A
System.out.println(lru); // [B, C, A] - A 移至末尾

性能對比基準 (JMH 參考)

選型決策樹

需要有序嗎？
├── 否 → HashSet (最高性能)
└── 是 → 何種順序？
    ├── 插入/訪問順序 → LinkedHashSet (O(1)，低開銷)
    └── 排序順序 → 元素實現 Comparable 嗎？
        ├── 是 → TreeSet (自然排序)
        └── 否 → TreeSet + Comparator (定制排序)
            └── 高併發環境 → ConcurrentSkipListSet