C# HashSet 和 SortedSet 介紹

HashSet 是一個高效能的集合類型，和 List 除了速度以外的差別在於 HashSet 不予許重複，且沒有順序。HashSet 使用 Hash 來存取元素，使用他的主要因素就是因為速度非常快，檢索的時間複雜度為 O(1)。如果需要速度快但是需要記錄順序的可以改為使用 SortedSet ，檢索的時間複雜度為 O(Log N)，但是一樣也不會儲存重複的資料。

速度比較

這裡做一個不嚴謹的測試，將 50 萬筆資料插入，再逐一檢查是否包含此資料，測試方式如下:

    
HashSet<int> hashSet = new HashSet<int>();

for (int i = 1; i <= 500000; i++)
{
    hashSet.Add(i);
}

// 計時
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();

// 搜尋
for (int i = 1; i <= 500000; i++)
{
    var contains = hashSet.Contains(i);
}

stopwatch.Stop();
Console.WriteLine($"HashSet: {stopwatch.ElapsedMilliseconds} ms");
    

HashSet, SortedSet, List 三者的速度比較如下:

    
// HashSet: 3 ms
// SortedSet: 46 ms
// List: 27089 ms
    

可以發現平時最常使用的 List 在大量存取下顯得有點吃力，反倒是 HashSet, SortedSet 非常快速。

基礎操作

HashSet 和 SortedSet 都有實作 ISet 介面，所以基礎操作都差不多:

    
HashSet<int> hashSet = new HashSet<int> ();
hashSet.Add(1);
hashSet.Add(1);
hashSet.Add(2);

Console.WriteLine(hashSet.Count); // 2

var contains = hashSet.Contains(1);
Console.WriteLine(contains); // true

hashSet.Remove(1);
Console.WriteLine(hashSet.Count); // 1

foreach (var i in hashSet)
{
    Console.WriteLine(i);
}
    

只是 HashSet 和 SortedSet 與 List 相比還多了 Overlaps, IsSubsetOf, IsProperSubsetOf 等數學集合運算方法可以使用。

參考資料：
Microsoft.Learn - HashSet<T> Class
Microsoft.Learn - SortedSet<T> Class