Java 排序去重實戰：TreeSet、Stream API 與效能對比

字串陣列排序去重是基礎操作，但資料量增大時效能差異顯著。本文對比 Arrays.sort + 迴圈、TreeSet、Stream API、LinkedHashSet + ArrayList.sort 四種方案，提供基準測試與選型建議。

原始需求重述

輸入："ZZZ BBB AAA OOO ZZZ AAA ZZZ BBB AAA ZZZ AAA VVV OOO CCC DDD CCC CCC KKK BBB AAA ZZZ AAA CCC KKK"

輸出：按字典序輸出 單詞:出現次數，如 AAA:7。

方案一：Arrays.sort + 雙重迴圈 (原始碼) ⭐

String[] words = strs.split(" ");
Arrays.sort(words); // O(n log n)

TreeSet set = new TreeSet<>(); // 自動排序+去重
for (int i = 0; i < words.length; i++) {
    int count = 0;
    for (int j = 0; j < words.length; j++) { // O(n^2) 計數
        if (words[i].equals(words[j])) count++;
    }
    set.add(words[i] + ":" + count);
}
for (String s : set) System.out.println(s);

• 時間複雜度：O(n²) 計數 + O(n log n) 排序 + O(k log k) TreeSet 插入 (k=不重複詞數)。
• 缺點：雙重迴圈極慢；TreeSet 再次排序多餘；字串拼接產生大量臨時對象。

方案二：TreeSet + 單次遍歷計數 ⭐⭐

Map freq = new HashMap<>();
for (String w : words) freq.merge(w, 1, Integer::sum); // O(n)

TreeSet result = new TreeSet<>(); // 排序
for (Map.Entry e : freq.entrySet()) {
    result.add(e.getKey() + ":" + e.getValue());
}
result.forEach(System.out::println);

• ✅ O(n) 計數 + O(k log k) 排序，大幅優化。
• ✅ 程式碼清晰，HashMap 計數、TreeSet 排序職責分離。

方案三：Stream API (Java 8+) ⭐⭐⭐

Arrays.stream(strs.split(" "))
      .collect(Collectors.groupingBy(
          w -> w, 
          Collectors.counting()))
      .entrySet().stream()
      .sorted(Map.Entry.comparingByKey())
      .forEach(e -> System.out.println(e.getKey() + ":" + e.getValue()));

• ✅ 一行式、聲明式、易讀。
• ✅ 並行流 .parallelStream() 可利用多核 (大數據量時)。
• ⚠️ 小數據量因物件創建開銷反而較慢。

方案四：LinkedHashSet + ArrayList.sort (保留首現順序) ⭐⭐

// 若需「首次出現順序」而非字典序
Set seen = new LinkedHashSet<>(Arrays.asList(words));
List unique = new ArrayList<>(seen);
unique.sort(String::compareTo); // 或不排序保留原順序
// 計數同方案二

基準測試 (JMH) 結果參考

測試環境：JDK 17, Intel i7-12700H, 16GB RAM, -Xmx2g

生產環境選型建議

1. 一般業務 (萬級以內)：方案三 Stream API，程式碼最簡潔、易維護。
2. 高效能/大數據量 (十萬級+)：方案二 HashMap + TreeSet 或 ConcurrentHashMap + parallelStream。
3. 需保留首現順序：LinkedHashMap 計數 + LinkedHashSet 去重。
4. 記憶體受限：外部排序 + 流式處理，或使用 MapDB/RocksDB 磁碟 Map。

進階：自定義 Comparator (按長度、忽略大小寫等)

TreeSet set = new TreeSet<>(
    Comparator.comparing(String::length)
              .thenComparing(String.CASE_INSENSITIVE_ORDER)
);