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> 有一堆方法,讓你可以像數學集合一樣操作它。像是:聯集、交集、差集、對稱差。
主要有這些:
| 方法 | 功能 |
|---|---|
|
把 other 裡的所有元素加進 hash set。 |
|
只留下同時在這裡跟 other 裡的元素。 |
|
把 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 一樣),因為預設是比記憶體位址。
GO TO FULL VERSION