CodeGym /課程 /C# SELF /集合: HashSet<T>

集合: HashSet<T>

C# SELF
等級 27, 課堂 4
開放

1. 前言

想像一下:你在寫一個網路商店系統,要存所有賣過的商品唯一代碼。或者更酷一點,你寫社群 app,要很快查某個使用者名稱有沒有被用過。又或者你想算一大篇文章裡有幾個不重複的單字?

這些情境都需要一個集合,裡面每個元素只能出現一次。這時候 HashSet<T> 就閃亮登場啦。

HashSet<T> 是一種 collection,專門存放無順序的唯一元素。重點就是 唯一。如果你想加一個已經存在的元素進 HashSet,它會直接無視你,不會加重複的。就像「只收獨一無二」的俱樂部:你進來過一次,第二次就不給進了。

HashSet<T> 的重點:

  • 唯一性: 保證每個元素只會出現一次。
  • 效能: 超快檢查有沒有、加、刪元素。這些操作平均都是常數時間 (O(1)),不管元素多少都一樣快!這是因為它用了一種叫 hashing 的機制。
  • 沒順序: 跟 List<T> 不一樣,HashSet<T> 裡的東西沒有固定順序。你不能用 index 取元素(比如「第五個」)。
  • 基於 hash table: HashSet<T> 裡面是用 hash table 存元素,這就是它快的原因。我們這邊不會細講 hash table 怎麼運作(這是進階課題),你可以想像每個元素都會「變成」一個特殊的數字(hash),靠這個數字超快找到它。

如果你用 List<T> 來存唯一元素,每次都要整個 list 掃一遍,確定沒有才加,這對大 list 來說超慢。HashSet<T> 則是瞬間完成!

2. HashSet<T> 對工程師有什麼用?

唯一集合的祕密

寫程式常常會遇到這種需求:要存不重複的東西。比如你在 parse app 使用者的 email 清單,要確定沒有重複。或是你要收集資料夾裡所有不重複的檔名。最簡單的解法就是用一個不能加重複元素的 collection。

當然你也可以用 List<T>,手動檢查有沒有再加:

var users = new List<string>();
if (!users.Contains("vasya@example.com"))
    users.Add("vasya@example.com");

但這種寫法遇到大量資料就很爛——Contains 會把 List 全部掃一遍,如果有幾千個使用者,程式就會慢到像 Windows XP 的老電腦。

HashSet<T> 幫你做了什麼

HashSet<T> 則保證每個元素只會存一次。它是用 hash table(跟 dictionary 一樣)實作的,所以加、查、刪都超快——通常是常數時間,不用全部掃過。

3. HashSet<T> 的基本用法

宣告與建立

要開始用不用額外加 library——這個 class 已經在 System.Collections.Generic namespace 裡了。

using System.Collections.Generic;

var emails = new HashSet<string>();

你也可以直接在建構時給初始值:

var fruits = new HashSet<string> { "蘋果", "香蕉", "梨子", "香蕉" };
// "香蕉" 出現兩次,但只會存一次!

加元素

加元素用 Add 方法。如果還沒有這個元素,會回傳 true。如果已經有了——什麼都不做,回傳 false。

bool added = emails.Add("vasya@example.com"); // true,加進去了
added = emails.Add("vasya@example.com");      // false,已經有了,沒加

有趣: 你可以一直叫 Add 加同一個值一百次——HashSet 不會生氣,只會禮貌地無視重複。

檢查有沒有:Contains

要查有沒有這個元素,用 Contains:

if (emails.Contains("vasya@example.com"))
    Console.WriteLine("這個 email 已經有了!");

刪元素

刪除也很快:

emails.Remove("vasya@example.com");

如果沒有這個元素——沒關係,方法只會回傳 false。

4. 實戰範例

我們來讓我們的學生 CRM 進階一點,這是我們這系列課程一直在改進的專案。

需求

假設我們的系統規定,每個使用者都要有唯一的使用者名稱(login)。加新使用者前要檢查有沒有重複,如果有就要提示。

範例程式

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // 存唯一 login 的 collection
        var userNames = new HashSet<string>();

        while (true)
        {
            Console.Write("請輸入使用者名稱(或輸入 leave 離開):");
            string name = Console.ReadLine();

            if (name == "leave")
                break;

            if (userNames.Add(name))
            {
                Console.WriteLine("名稱新增成功!");
            }
            else
            {
                Console.WriteLine("錯誤:這個名稱已經被用過,請換一個。");
            }
        }

        Console.WriteLine("使用者清單:");
        foreach (var user in userNames)
            Console.WriteLine($"- {user}");

        // 注意!輸出順序可能是亂的。
    }
}

就這麼簡單,我們就保證了唯一性。不用自己檢查有沒有——HashSet 會自動幫你搞定。

5. HashSet<T> 裡面怎麼運作?hash code 有什麼用

比喻:儲存格

想像你有一大疊 login 卡片,桌上有 0 到 1000 號的格子。每個 login 你都放進一個格子,格子的號碼是用一個函數(GetHashCode)算出來的。如果卡片重複——它們會在同一格,你就能很快知道這個 login 已經有了。

GetHashCode 函數

HashSet<T> 比較元素時不是直接比值,而是先用 GetHashCode() 算出 hash code。大部分內建型別(int、string、double 等)都已經有很好的實作。

有趣的小知識: 如果你要存自己的 class 進 HashSet<T>,一定要自己實作正確的相等比較跟 hash code(Equals 跟 GetHashCode 方法),這樣唯一性才會正確。這個我們之後還會再講。

HashSet<T> 常見錯誤

剛學用唯一集合時,大家常掉進一個坑:以為 HashSet<T> 會照加進去的順序存東西。其實不是!hash set 完全不保證順序,東西可能亂七八糟。如果你很在意順序——要用別的 collection,比如 SortedSet<T>,但這又是另一個主題了。

第二個常見錯誤——想用 index 取值:

string name = userNames[0]; // 錯誤!HashSet<T> 沒有 index。

跟 array 或 list 不一樣,這裡不能用編號取元素。只能用 foreach 來跑。

第三個常見混淆是序列化或存檔時——因為順序不固定,每次程式跑起來元素順序都可能不一樣。

6. 集合運算:聯集、交集、差集

HashSet<T> 有一堆方法,讓你可以像數學集合一樣操作它。像是:聯集、交集、差集、對稱差。

主要有這些:

方法 功能
UnionWith(other)
把 other 裡的所有元素加進 hash set。
IntersectWith(other)
只留下同時在這裡跟 other 裡的元素。
ExceptWith(other)
把 other 裡的元素從目前集合移除。
SymmetricExceptWith(other)
只留下只在這裡或 other 裡,但不在兩邊都有的元素。

範例:交集與聯集

來看個例子。假設有兩組名字:

var groupA = new HashSet<string> { "安雅", "鮑里斯", "維拉" };
var groupB = new HashSet<string> { "維拉", "格列布", "達莎" };

// 找出兩組都有的人
var common = new HashSet<string>(groupA); // 複製內容,不然 groupA 會被改!
common.IntersectWith(groupB);

Console.WriteLine("兩組都有的人:");
foreach (var name in common)
    Console.WriteLine(name); // 會印出 "維拉"

// 把兩組所有學生合起來,沒人漏掉:
var all = new HashSet<string>(groupA);
all.UnionWith(groupB);

Console.WriteLine("所有學生:");
foreach (var name in all)
    Console.WriteLine(name); // "安雅", "鮑里斯", "維拉", "格列布", "達莎"

7. 其他方法與屬性

Count —— 查集合裡有幾個元素:

Console.WriteLine(userNames.Count);

Clear —— 全部清空(就像 CTRL+A, DELETE):

userNames.Clear();

SetEquals、IsSubsetOf、IsSupersetOf —— 檢查集合是否相等、是不是子集合、是不是超集合。這很適合你在玩(或寫)「數學家誰比較強」這種遊戲。

if (groupA.IsSubsetOf(groupB))
    Console.WriteLine("A 組的所有人都在 B 組裡");

8. 在 HashSet<T> 裡存自己的物件

剛剛有提到,標準型別都已經會算 hash 跟比較相等了。

但如果你要存自己的物件,比如使用者,就要自己定義怎麼比(比如用 login):

class User
{
    public string Login { get; set; }

    public override bool Equals(object obj)
    {
        if (obj is User other)
            return Login == other.Login;
        return false;
    }

    public override int GetHashCode()
    {
        return Login.GetHashCode();
    }
}

// 現在可以這樣用:
var users = new HashSet<User>();
users.Add(new User { Login = "vasya" });
users.Add(new User { Login = "petya" });
users.Add(new User { Login = "vasya" }); // 不會加進去!

如果沒有 override Equals 跟 GetHashCode,HashSet 會把每個 instance 都當不同的(即使 login 一樣),因為預設是比記憶體位址。

2
任務
C# SELF, 等級 27, 課堂 4
上鎖
檢查字串唯一性
檢查字串唯一性
1
問卷/小測驗
主要集合概覽,等級 27,課堂 4
未開放
主要集合概覽
集合型別與 generics
留言
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION