C# 集合深度對比：HashSet、HashTable、TreeSet 核心原理與選型指南

C# 集合深度對比：HashSet、HashTable、TreeSet 核心原理與選型指南

本文聚焦 C#/.NET 體系下的三大經典集合：**HashSet<T>**、**Hashtable**、**TreeSet**（實為 SortedSet<T>），從底層數據結構、核心 API、性能特徵、適用場景四個維度深度對比，助你精準選型。

一、HashSet<T>：高性能集合運算利器

1. 核心定位

• 基於**哈希表**實現，專為**集合運算**（並集、交集、差集、子集判斷）優化
• 元素**唯一、無序**，單元素操作 O(1) 平均複雜度
• .NET Framework 3.5+ 引入，泛型、類型安全

2. 關鍵構造函數

new HashSet<T>()                                    // 默認比較器
new HashSet<T>(IEnumerable<T> collection)           // 從集合初始化
new HashSet<T>(IEqualityComparer<T> comparer)       // 自定義相等比較
new HashSet<T>(IEnumerable<T>, IEqualityComparer<T>)

3. 核心集合運算方法 (修改當前實例)

4. 其他常用方法

• Add/Remove/Contains/Clear/Count
• RemoveWhere(predicate)、TrimExcess() (釋放多餘容量)

二、TreeSet / SortedSet<T>：有序集合的紅黑樹實現

.NET 中**無 TreeSet 類**，有序集合為 SortedSet<T> (Framework 4.0+)，底層同為**紅黑樹**，功能對標 Java TreeSet。

1. 核心特徵

• 元素**唯一、有序**（升序），插入/刪除/查找 O(log n)
• 要求元素實現 IComparable<T> 或構造時傳入 IComparer<T>
• **不允許 null 值** (紅黑樹比較需非空)
• 提供 Min/Max、GetViewBetween(lower, upper) 範圍視圖、Reverse() 逆序枚舉

2. HashSet vs SortedSet 核心差異

三、Hashtable：非泛型時代的同步哈希表

Hashtable 為非泛型集合** (存 Object)，**強烈建議新代碼改用 Dictionary<TKey, TValue>** 或 ConcurrentDictionary<TKey, TValue>。本節僅供維護舊代碼參考。

需要 Key-Value 映射？
    ├─ 是 → 高併發？ → 是 → ConcurrentDictionary
    │                └─ 否 → Dictionary
    └─ 否 → 需要有序/範圍查詢？
                 ├─ 是 → SortedSet / SortedDictionary
                 └─ 否 → 需要集合運算(並/交/差)？
                          ├─ 是 → HashSet
                          └─ 是 → 只需去重/存在性判斷 → HashSet
                                   └─ 兼容舊代碼 → Hashtable (不推薦新用)