C# Set 是什么？HashSet 用法全解析 – wiki基地

作者： /

C# Set 是什么？HashSet 用法全解析

在 .NET 编程中，集合（Collections）是用来存储、组织和管理数据的基础工具。我们熟知并经常使用的集合类型包括 List<T>、Array、Dictionary<TKey, TValue> 等。然而，在某些特定场景下，我们需要一种集合类型，它能够保证元素的唯一性，并且在检查某个元素是否存在时具有极高的效率。这时候，Set（集合）就闪亮登场了。

本文将深入探讨 C# 中的 Set 概念，特别是其最常用和高效的实现：HashSet<T>。我们将从 Set 的数学定义出发，过渡到它在 C# 中的体现，详细解析 HashSet<T> 的特性、基本用法、高级操作，以及性能考量和使用时的注意事项。

1. Set 的数学概念：集合论基础

在计算机科学中，许多概念都源于数学，Set 也不例外。在数学集合论中，一个集合（Set）是具有以下两个主要特征的对象的无序聚集：

  1. 唯一性 (Uniqueness): 集合中的元素是唯一的，不允许重复。如果试图将一个已存在的元素添加到集合中，该操作将不会改变集合，也不会产生新的元素。
  2. 无序性 (Unordered): 集合中的元素没有特定的顺序。元素的排列方式不影响集合本身。例如，集合 {a, b, c} 和 {c, a, b} 是同一个集合。

数学集合论还定义了一系列操作，如并集 (Union)、交集 (Intersection)、差集 (Difference) 等，这些操作在处理多个集合的关系时非常有用。C# 中的 Set 实现也提供了这些操作。

理解了数学集合的这些基本属性，我们就能更好地理解它在编程中的应用和优势。

2. C# 中的 Set 概念：ISet 接口

在 .NET Framework 和 .NET Core/.NET 平台上，Set 的概念通过 System.Collections.Generic.ISet<T> 接口体现。ISet<T> 接口继承自 ICollection<T> 和 IEnumerable<T>，它在标准集合操作（如添加、删除、检查是否存在、迭代）的基础上，增加了对集合论操作（如并集、交集、差集、判断子集/父集）的定义。

ISet<T> 接口定义了 Set 必须支持的行为，但它本身不提供具体的实现。主要的实现类有两个：

  1. HashSet<T>: 这是最常用的一种实现，它使用哈希表（Hash Table）作为底层数据结构。它不保证元素的顺序，但提供了非常高效的元素添加、删除和查找操作。
  2. SortedSet<T>: 这种实现使用平衡二叉树（Balanced Binary Tree，通常是红黑树）作为底层数据结构。它能够保持元素的有序性，并且提供了高效的元素添加、删除和查找操作，但相对于 HashSet<T>，其查找操作的平均性能略低（O(log n) vs O(1)）。

本文的重点是 HashSet<T>，因为它是 Set 概念在 C# 中最常见且性能优越的实现，尤其适用于需要快速去重和快速查找的场景。

3. 为什么选择使用 Set (特别是 HashSet)?

了解了 Set 的概念后，自然会问：为什么我们需要 Set？它在什么场景下比 List<T> 或 Dictionary<TKey, TValue> 更适合？

使用 HashSet<T> 的主要优势在于其独特的属性和高效的实现：

  1. 保证元素唯一性 (Automatic De-duplication): HashSet<T> 自动处理重复元素的添加。如果你尝试添加一个已经存在于 Set 中的元素，Add 方法会返回 false，并且 Set 的内容不会改变。这使得去重变得非常简单和高效。
  2. 高效的元素查找 (Efficient Lookups): 基于哈希表的实现使得 HashSet<T> 在平均情况下执行 Contains()、Add()、Remove() 操作的时间复杂度为 O(1)。这意味着无论 Set 中有多少元素，执行这些基本操作所需的时间大致是恒定的。这与 List<T> 形成鲜明对比，List<T> 的 Contains() 操作通常需要遍历整个列表，时间复杂度为 O(n)。当处理大量数据时，O(1) 的性能优势是巨大的。
  3. 高效的集合操作 (Set Operations): HashSet<T> 提供了直接且高效的方法来执行并集、交集、差集等操作。这些操作通常比手动遍历和比较其他集合要快得多。

典型应用场景:

  • 快速判断元素是否存在: 例如，检查一个用户名是否已被注册。
  • 从一个列表中去除重复项: 将列表元素依次添加到 HashSet 中，最后 HashSet 里的元素就是去重后的结果。
  • 找出两个列表的共同元素 (交集)。
  • 找出在一个列表中但在另一个列表中不存在的元素 (差集)。
  • 找出两个列表的所有不重复元素 (并集)。
  • 检查一个集合是否是另一个集合的子集或父集。

总而言之，当你需要一个集合来存储一组不重复的元素，并且频繁地进行成员资格测试（即检查某个元素是否存在），或者需要执行集合论操作时，HashSet<T> 是一个非常理想的选择。

4. 深入理解 HashSet 的特性

HashSet<T> 是 ISet<T> 接口最常见的实现。它基于哈希表工作，因此继承了哈希表的特性：

  • 无序性: HashSet<T> 不保证元素的顺序。元素的存储位置取决于其哈希码，即使以特定顺序添加元素，迭代时也可能得到不同的顺序。
  • 唯一性: 这是其核心特性。重复元素无法被添加。
  • 不允许 Null 元素: HashSet<T> 不允许存储 null 作为元素（对于引用类型 T）。尝试添加 null 会抛出 ArgumentNullException。
  • 性能: 如前所述，Add、Remove、Contains 等基本操作在平均情况下是 O(1)。迭代整个 Set 的时间复杂度是 O(n)，其中 n 是元素的数量。集合操作（如 UnionWith）的时间复杂度取决于参与操作的集合的大小，通常是 O(m + n)，其中 m 和 n 是两个集合的大小。
  • 依赖于 Equals() 和 GetHashCode(): HashSet<T> 使用元素的 Equals() 方法来判断两个元素是否相等（即是否是同一个元素），使用 GetHashCode() 方法来确定元素在哈希表中的存储位置。因此，当你使用自定义对象作为 HashSet<T> 的元素类型 T 时，正确地覆盖 Equals() 和 GetHashCode() 方法至关重要。如果 Equals() 和 GetHashCode() 没有被正确实现，可能会导致重复元素被错误地添加到 Set 中，或者 Contains() 方法无法找到本应存在的元素。对于值类型（如 int, string, struct），.NET 已经提供了正确的默认实现。对于引用类型，默认的 Equals() 和 GetHashCode() 基于对象的引用（内存地址），这意味着只有当两个变量引用同一个对象实例时才被认为是相等的。如果你希望基于对象的内容来判断相等性，就必须覆盖这两个方法。

5. HashSet 的基本用法解析

接下来，我们将通过代码示例详细解析 HashSet<T> 的基本用法。

5.1 创建 HashSet

可以创建空的 HashSet<T>，也可以从其他集合初始化。

“`csharp
using System;
using System.Collections.Generic;

// 1. 创建一个空的 HashSet
HashSet uniqueNames = new HashSet();
Console.WriteLine($”初始时，uniqueNames 集合大小: {uniqueNames.Count}”); // 输出: 0

// 2. 从其他集合创建 HashSet
List numbersWithDuplicates = new List { 1, 2, 3, 3, 4, 5, 1, 2 };
HashSet uniqueNumbers = new HashSet(numbersWithDuplicates);
Console.WriteLine($”从列表创建后，uniqueNumbers 集合大小: {uniqueNumbers.Count}”); // 输出: 5 (1, 2, 3, 4, 5)

// 3. 也可以使用数组等其他实现了 IEnumerable 的集合
string[] fruitsArray = { “apple”, “banana”, “orange”, “apple” };
HashSet uniqueFruits = new HashSet(fruitsArray);
Console.WriteLine($”从数组创建后，uniqueFruits 集合大小: {uniqueFruits.Count}”); // 输出: 3 (apple, banana, orange)

// 使用集合初始化器（Collection Initializer）创建
HashSet uniqueScores = new HashSet { 90.5, 85.0, 90.5, 78.0 };
Console.WriteLine($”使用初始化器创建后，uniqueScores 集合大小: {uniqueScores.Count}”); // 输出: 3 (90.5, 85.0, 78.0)
“`

5.2 添加元素 (Add)

使用 Add(T item) 方法向集合中添加元素。如果元素成功添加（即之前不存在），方法返回 true；如果元素已经存在，方法返回 false，集合保持不变。

“`csharp
HashSet attendees = new HashSet();

bool addedJohn = attendees.Add(“John”);
Console.WriteLine($”添加 John: {addedJohn}”); // 输出: True
Console.WriteLine($”集合大小: {attendees.Count}”); // 输出: 1

bool addedJane = attendees.Add(“Jane”);
Console.WriteLine($”添加 Jane: {addedJane}”); // 输出: True
Console.WriteLine($”集合大小: {attendees.Count}”); // 输出: 2

bool addedJohnAgain = attendees.Add(“John”); // John 已经存在
Console.WriteLine($”再次添加 John: {addedJohnAgain}”); // 输出: False
Console.WriteLine($”集合大小: {attendees.Count}”); // 输出: 2 (大小没有变化)

// 迭代查看当前元素 (注意: 迭代顺序不确定)
Console.WriteLine(“当前参会人员:”);
foreach (string name in attendees)
{
Console.WriteLine(name);
}
“`

5.3 检查元素是否存在 (Contains)

使用 Contains(T item) 方法检查集合中是否存在指定的元素。这是 HashSet 最常用的操作之一，并且非常高效 (平均 O(1))。

“`csharp
HashSet primes = new HashSet { 2, 3, 5, 7, 11 };

Console.WriteLine($”集合是否包含 5: {primes.Contains(5)}”); // 输出: True
Console.WriteLine($”集合是否包含 4: {primes.Contains(4)}”); // 输出: False
Console.WriteLine($”集合是否包含 11: {primes.Contains(11)}”); // 输出: True
“`

5.4 删除元素 (Remove)

使用 Remove(T item) 方法从集合中删除指定的元素。如果元素成功删除（即元素存在），方法返回 true；如果元素不存在于集合中，方法返回 false。

“`csharp
HashSet colors = new HashSet { “red”, “green”, “blue”, “yellow” };

bool removedGreen = colors.Remove(“green”);
Console.WriteLine($”删除 green: {removedGreen}”); // 输出: True
Console.WriteLine($”集合大小: {colors.Count}”); // 输出: 3

bool removedPurple = colors.Remove(“purple”); // purple 不存在
Console.WriteLine($”删除 purple: {removedPurple}”); // 输出: False
Console.WriteLine($”集合大小: {colors.Count}”); // 输出: 3 (大小没有变化)

Console.WriteLine(“当前颜色:”);
foreach (string color in colors)
{
Console.WriteLine(color); // 输出: red, blue, yellow (顺序不确定)
}
“`

5.5 获取元素数量 (Count)

使用 Count 属性获取集合中当前元素的数量。

“`csharp
HashSet letters = new HashSet(“programming”); // 初始化时会自动去重

Console.WriteLine($”集合中的唯一字母数量: {letters.Count}”); // 输出: 9 (p, r, o, g, a, m, i, n, )
“`

5.6 清空集合 (Clear)

使用 Clear() 方法移除集合中的所有元素。

“`csharp
HashSet numbers = new HashSet { 10, 20, 30, 40 };
Console.WriteLine($”清空前集合大小: {numbers.Count}”); // 输出: 4

numbers.Clear();
Console.WriteLine($”清空后集合大小: {numbers.Count}”); // 输出: 0
“`

5.7 遍历集合

可以使用 foreach 循环遍历 HashSet<T> 中的所有元素。需要注意的是，遍历的顺序是不确定的，并且可能随着 Set 的内容变化而变化，不应该依赖于特定的遍历顺序。

“`csharp
HashSet animals = new HashSet { “cat”, “dog”, “elephant”, “lion” };

Console.WriteLine(“集合中的动物:”);
foreach (string animal in animals)
{
Console.WriteLine(animal);
}
// 输出顺序可能是 cat, dog, elephant, lion，也可能是 lion, elephant, dog, cat，或其他任意组合。
“`

重要提示: 在遍历 HashSet<T> 时，不要修改集合（添加或删除元素），除非你非常清楚自己在做什么（例如在遍历过程中移除当前元素，这通常需要特殊的处理或使用 LINQ 操作）。在 foreach 循环中修改集合会导致迭代器失效，引发运行时错误（InvalidOperationException）。

6. HashSet 的高级操作：集合论操作解析

HashSet<T> 提供了丰富的集合论操作方法，可以直接对两个 Set 进行并集、交集、差集等运算。这些方法通常比手动编写循环实现这些逻辑更高效且代码更简洁。

假设我们有两个 HashSet<int> 集合 A 和 B:
HashSet<int> setA = new HashSet<int> { 1, 2, 3, 4, 5 };
HashSet<int> setB = new HashSet<int> { 4, 5, 6, 7, 8 };

6.1 并集 (UnionWith)

UnionWith(IEnumerable<T> other) 方法将当前 HashSet 修改为包含自身和另一个集合中所有不重复的元素。

“`csharp
HashSet setA_Union = new HashSet(setA); // 复制 setA 以进行操作
setA_Union.UnionWith(setB);

Console.Write(“并集 (A ∪ B): “);
foreach (int num in setA_Union)
{
Console.Write($”{num} “); // 输出: 1 2 3 4 5 6 7 8 (顺序不确定)
}
Console.WriteLine();
``
结果是{1, 2, 3, 4, 5, 6, 7, 8}`。

6.2 交集 (IntersectWith)

IntersectWith(IEnumerable<T> other) 方法将当前 HashSet 修改为只包含同时存在于自身和另一个集合中的元素。

“`csharp
HashSet setA_Intersect = new HashSet(setA); // 复制 setA 以进行操作
setA_Intersect.IntersectWith(setB);

Console.Write(“交集 (A ∩ B): “);
foreach (int num in setA_Intersect)
{
Console.Write($”{num} “); // 输出: 4 5 (顺序不确定)
}
Console.WriteLine();
``
结果是{4, 5}`。

6.3 差集 (ExceptWith)

ExceptWith(IEnumerable<T> other) 方法将当前 HashSet 修改为包含只存在于自身，而不存在于另一个集合中的元素。

“`csharp
HashSet setA_Except = new HashSet(setA); // 复制 setA 以进行操作
setA_Except.ExceptWith(setB);

Console.Write(“差集 (A \ B): “); // 元素在 A 中，但不在 B 中
foreach (int num in setA_Except)
{
Console.Write($”{num} “); // 输出: 1 2 3 (顺序不确定)
}
Console.WriteLine();

HashSet setB_Except = new HashSet(setB); // 复制 setB 以进行操作
setB_Except.ExceptWith(setA);

Console.Write(“差集 (B \ A): “); // 元素在 B 中，但不在 A 中
foreach (int num in setB_Except)
{
Console.Write($”{num} “); // 输出: 6 7 8 (顺序不确定)
}
Console.WriteLine();
``A \ B结果是{1, 2, 3}。B \ A结果是{6, 7, 8}`。

6.4 对称差集 (SymmetricExceptWith)

SymmetricExceptWith(IEnumerable<T> other) 方法将当前 HashSet 修改为包含只存在于其中一个集合中（而非同时存在于两个集合中）的元素。这相当于 (A \ B) ∪ (B \ A) 或 (A ∪ B) \ (A ∩ B)。

“`csharp
HashSet setA_SymmetricExcept = new HashSet(setA); // 复制 setA 以进行操作
setA_SymmetricExcept.SymmetricExceptWith(setB);

Console.Write(“对称差集 (A Δ B): “);
foreach (int num in setA_SymmetricExcept)
{
Console.Write($”{num} “); // 输出: 1 2 3 6 7 8 (顺序不确定)
}
Console.WriteLine();
``
结果是{1, 2, 3, 6, 7, 8}`。

6.5 判断子集/父集关系

HashSet<T> 还提供了方法来检查一个集合是否是另一个集合的子集或父集。

  • IsSubsetOf(IEnumerable<T> other): 如果当前 HashSet 中的所有元素都存在于 other 集合中，则返回 true。
  • IsProperSubsetOf(IEnumerable<T> other): 如果当前 HashSet 是 other 集合的子集，并且 other 集合至少包含一个当前 HashSet 中没有的元素（即 other 严格大于当前 HashSet），则返回 true。
  • IsSupersetOf(IEnumerable<T> other): 如果 other 集合中的所有元素都存在于当前 HashSet 中，则返回 true。
  • IsProperSupersetOf(IEnumerable<T> other): 如果当前 HashSet 是 other 集合的超集，并且当前 HashSet 至少包含一个 other 集合中没有的元素（即当前 HashSet 严格大于 other），则返回 true。

“`csharp
HashSet largeSet = new HashSet { 1, 2, 3, 4, 5 };
HashSet smallSet = new HashSet { 2, 3 };
HashSet otherSet = new HashSet { 3, 4, 5, 6 };
HashSet sameSet = new HashSet { 1, 2, 3, 4, 5 }; // 内容与 largeSet 相同

Console.WriteLine($”smallSet 是 largeSet 的子集吗? {smallSet.IsSubsetOf(largeSet)}”); // 输出: True
Console.WriteLine($”smallSet 是 largeSet 的真子集吗? {smallSet.IsProperSubsetOf(largeSet)}”); // 输出: True
Console.WriteLine($”largeSet 是 smallSet 的超集吗? {largeSet.IsSupersetOf(smallSet)}”); // 输出: True
Console.WriteLine($”largeSet 是 smallSet 的真超集吗? {largeSet.IsProperSupersetOf(smallSet)}”); // 输出: True

Console.WriteLine($”largeSet 是 otherSet 的子集吗? {largeSet.IsSubsetOf(otherSet)}”); // 输出: False
Console.WriteLine($”smallSet 是 otherSet 的子集吗? {smallSet.IsSubsetOf(otherSet)}”); // 输出: False

Console.WriteLine($”sameSet 是 largeSet 的子集吗? {sameSet.IsSubsetOf(largeSet)}”); // 输出: True
Console.WriteLine($”sameSet 是 largeSet 的真子集吗? {sameSet.IsProperSubsetOf(largeSet)}”); // 输出: False (因为它们大小相等)
“`

6.6 判断集合是否相等 (SetEquals)

SetEquals(IEnumerable<T> other) 方法检查当前 HashSet 与另一个集合是否包含完全相同的元素，忽略顺序和重复。

“`csharp
HashSet set1 = new HashSet { 1, 2, 3 };
HashSet set2 = new HashSet { 3, 1, 2 }; // 顺序不同，但元素相同
List list3 = new List { 1, 2, 2, 3 }; // 包含重复项，但去重后元素相同
HashSet set4 = new HashSet { 1, 2, 4 }; // 元素不同

Console.WriteLine($”set1 与 set2 是否相等? {set1.SetEquals(set2)}”); // 输出: True
Console.WriteLine($”set1 与 list3 是否相等? {set1.SetEquals(list3)}”); // 输出: True (list3 被视为去重后的元素集合 {1, 2, 3})
Console.WriteLine($”set1 与 set4 是否相等? {set1.SetEquals(set4)}”); // 输出: False
“`

这些集合论操作极大地简化了处理多个集合的代码，并且由于是内置实现，通常具有较好的性能。

7. 性能考量：O(1) 的秘密与陷阱

HashSet<T> 之所以能够实现平均 O(1) 的查找、添加和删除性能，是因为它内部使用了哈希表。哈希表通过一个散列函数（Hashing Function）将元素的键（在这里就是元素本身）映射到表中的一个索引位置。理想情况下，通过计算元素的哈希码，可以直接定位到元素所在的存储位置，从而实现快速访问。

7.1 平均 O(1)

  • Add(T item): 计算 item 的哈希码，找到对应的桶（bucket）。检查该桶中是否已存在相等的元素。如果不存在，则添加。平均情况下，查找桶和检查桶内元素都非常快。
  • Contains(T item): 计算 item 的哈希码，找到对应的桶。在该桶中查找是否存在相等的元素。平均情况下，查找桶和检查桶内元素都非常快。
  • Remove(T item): 计算 item 的哈希码，找到对应的桶。在该桶中找到相等的元素并移除。平均情况下，查找桶、找到元素和移除都非常快。

7.2 最差情况 O(n)

哈希表的性能严重依赖于散列函数的质量。如果散列函数设计得不好，或者存在恶意输入（称为哈希冲突攻击），可能导致大量不同的元素被映射到同一个桶中。当一个桶中存储了大量元素时，对该桶的操作（查找、添加、删除）就需要遍历桶内的所有元素，此时的性能会退化到 O(n)，其中 n 是集合中元素的总数（或者更精确地说，是该桶中元素的数量）。幸运的是，.NET Framework 和 .NET Core/.NET 平台的默认散列函数（如 string 的哈希函数）通常设计得比较好，能够分散哈希码，使得大多数情况下的性能接近 O(1)。

7.3 Equals() 和 GetHashCode() 的重要性

正如之前提到的，HashSet<T> 使用 Equals() 方法判断相等性，使用 GetHashCode() 方法确定存储位置。要确保 HashSet<T> 正常工作并发挥其性能优势，必须遵循以下约定：

  1. 如果两个对象 a 和 b 通过 Equals(a, b) 方法被判断为相等，那么 a.GetHashCode() 必须等于 b.GetHashCode()。 反之不要求（不同的对象可以有相同的哈希码，这称为哈希冲突，哈希表会处理这种情况，但过多的冲突会降低性能）。
  2. GetHashCode() 方法应该在对象的生存期内返回相同的值，前提是对象的状态没有改变影响其相等性的部分。
  3. Equals() 方法必须满足以下条件：自反性 (a.Equals(a) 为 true)、对称性 (a.Equals(b) == b.Equals(a))、传递性 (如果 a.Equals(b) 为 true 且 b.Equals(c) 为 true，则 a.Equals(c) 为 true)、一致性 (如果对象未修改，多次调用 Equals 返回相同结果)、非空性 (a.Equals(null) 为 false)。

对于自定义类，如果你需要基于其内容而不是引用来判断相等性（例如，两个 Person 对象即使是不同实例，只要姓名和年龄相同就认为是同一个“人”），你就需要覆盖 Equals() 和 GetHashCode()。

示例：使用自定义对象作为 HashSet 元素

“`csharp
public class Person
{
public string Name { get; set; }
public int Age { get; set; }

// 注意: 如果不覆盖 Equals 和 GetHashCode，即使 Name 和 Age 相同，
// 两个不同的 Person 对象实例在 HashSet 中也会被认为是不同的元素。

// 覆盖 Equals 方法以基于 Name 和 Age 进行比较
public override bool Equals(object obj)
{
    if (obj == null || GetType() != obj.GetType())
    {
        return false;
    }

    Person other = (Person)obj;
    // 使用 StringComparer.OrdinalIgnoreCase 进行字符串比较，忽略大小写
    return string.Equals(Name, other.Name, StringComparison.OrdinalIgnoreCase) &&
           Age == other.Age;
}

// 覆盖 GetHashCode 方法
public override int GetHashCode()
{
    // 为 Name 和 Age 计算哈希码，并组合它们。
    // 可以使用 .NET 内置的 HashCode.Combine 或手动组合
    // HashCode.Combine (C# 8.0 及更高版本)
    return HashCode.Combine(Name?.ToUpperInvariant(), Age); // Name 可以为 null
    // 或者手动组合 (兼容旧版本)
    // int hash = 17; // 任意非零素数
    // hash = hash * 23 + (Name != null ? StringComparer.OrdinalIgnoreCase.GetHashCode(Name) : 0); // 另一个素数
    // hash = hash * 23 + Age.GetHashCode();
    // return hash;
}

public override string ToString()
{
    return $"Name: {Name}, Age: {Age}";
}

}

// 使用 Person 对象作为 HashSet 元素
HashSet uniquePeople = new HashSet();

Person p1 = new Person { Name = “Alice”, Age = 30 };
Person p2 = new Person { Name = “Bob”, Age = 25 };
Person p3 = new Person { Name = “Alice”, Age = 30 }; // 内容与 p1 相同

uniquePeople.Add(p1);
uniquePeople.Add(p2);
bool addedP3 = uniquePeople.Add(p3); // 尝试添加内容相同的对象

Console.WriteLine($”添加 p3 ({p3}) 是否成功? {addedP3}”); // 如果正确覆盖了 Equals/GetHashCode, 输出: False
Console.WriteLine($”集合中的人数: {uniquePeople.Count}”); // 如果正确覆盖了 Equals/GetHashCode, 输出: 2

Console.WriteLine(“集合中的人:”);
foreach (Person person in uniquePeople)
{
Console.WriteLine(person); // 输出: Name: Alice, Age: 30; Name: Bob, Age: 25 (顺序不确定)
}

// 检查是否存在一个内容与 p1 相同的对象
Person p4 = new Person { Name = “alice”, Age = 30 }; // 名字大小写不同，但根据 Equals 应该相等
Console.WriteLine($”集合是否包含内容与 p4 ({p4}) 相同的对象? {uniquePeople.Contains(p4)}”); // 如果正确覆盖了 Equals/GetHashCode, 输出: True
``
这个例子强调了为自定义类型正确实现Equals()和GetHashCode()对于HashSet(以及Dictionary` 等其他哈希集合) 的正确性和性能是多么重要。

7.4 与 List<T> 的 Contains 性能对比

正如前面提到的，List<T> 的 Contains() 方法需要线性搜索列表（从头到尾逐个比较），平均时间复杂度是 O(n)，最差也是 O(n)。而 HashSet<T> 的 Contains() 方法在平均情况下是 O(1)。

考虑一个包含 100,000 个元素的集合：
* 在 List<T> 中查找一个元素，平均需要比较 50,000 次，最差需要 100,000 次。
* 在 HashSet<T> 中查找一个元素，平均只需要计算一次哈希码，然后在对应的桶里进行少量比较。这个操作所需的时间几乎不受集合大小的影响。

因此，如果你的应用需要频繁地检查某个元素是否存在于一个大型集合中，使用 HashSet<T> 会比 List<T> 带来显著的性能提升。

8. SortedSet<T> 简介 (与 HashSet 的对比)

虽然本文专注于 HashSet<T>，但了解 SortedSet<T> 有助于理解 Set 的不同实现以及何时选择哪一个。

SortedSet<T> 也实现了 ISet<T> 接口，它提供 Set 的所有功能，但有以下关键区别：

  • 有序性: SortedSet<T> 中的元素总是按照特定的顺序排列，通常是元素的自然顺序（如果实现了 IComparable<T> 或 IComparable 接口）或由构造函数提供的 IComparer<T> 指定的顺序。
  • 底层数据结构: SortedSet<T> 使用平衡二叉搜索树（通常是红黑树）实现。
  • 性能:
    • Add、Remove、Contains 操作的时间复杂度是 O(log n)。虽然不如 HashSet<T> 的平均 O(1)，但对于大型集合仍然非常高效，并且不像 HashSet 那样有 O(n) 的最差情况（假设比较器实现良好）。
    • 支持范围操作，例如获取大于某个值或小于某个值的元素，这是 HashSet<T> 不具备的。

何时选择 HashSet<T> vs SortedSet<T>:

  • 选择 HashSet<T> 当：
    • 你需要最快的元素查找 (O(1) 平均)。
    • 元素的顺序无关紧要。
  • 选择 SortedSet<T> 当：
    • 你需要集合中的元素始终保持有序。
    • 你需要执行范围查询或找到最小值/最大值。
    • O(log n) 的查找性能足够满足需求。

大多数情况下，如果不需要排序，HashSet<T> 是 Set 功能的首选实现，因为它提供了最佳的平均性能。

9. 使用 HashSet 的常见陷阱和注意事项

  • 在迭代时修改集合: 在 foreach 循环中直接修改 HashSet 的内容（通过 Add 或 Remove）是危险的，会导致 InvalidOperationException。如果需要在遍历时移除元素，可以考虑：
    • 先将要移除的元素收集到一个临时列表中，然后在遍历结束后批量移除。
    • 使用 while 循环和迭代器的 MoveNext()、Current 和 Remove() 方法（如果迭代器支持，但 HashSet 的迭代器不支持安全修改）。更简单的做法是使用 LINQ 的 Where() 方法创建一个新的集合。
  • null 元素: HashSet<T> 不支持存储 null。如果需要处理可能为 null 的元素，可能需要在添加到 Set 之前进行过滤，或者使用其他集合类型。
  • 不正确的 Equals 和 GetHashCode 实现: 对于自定义类型，这是导致 HashSet 工作异常（重复元素未被去重，Contains 查找失败）的最常见原因。务必正确覆盖这两个方法，并确保它们满足哈希表的约定。使用 Visual Studio 的代码生成功能或 C# 9 的 record 类型可以简化这个过程。
  • 线程安全性: HashSet<T> 不是线程安全的。如果在多线程环境中同时访问和修改同一个 HashSet 实例，需要使用锁 (lock 关键字) 或其他同步机制来保护集合的访问。或者考虑使用并发集合，如 ConcurrentDictionary (虽然不是 Set，但可以模拟 Set 的行为，例如通过将其值类型设置为 byte 并忽略值)。目前 .NET 标准库中没有 ConcurrentHashSet 的直接实现。

10. 结论

HashSet<T> 是 .NET 集合框架中一个强大且高效的工具，尤其适用于需要存储不重复元素并进行快速成员资格测试（Contains）或集合论操作的场景。它通过基于哈希表的实现，提供了平均 O(1) 的查找、添加和删除性能，远超 List<T> 等线性集合的 O(n) 性能。

理解 Set 的数学概念、ISet<T> 接口的作用，以及 HashSet<T> 基于哈希表的工作原理，是高效使用它的关键。特别是在处理自定义对象时，正确实现 Equals() 和 GetHashCode() 方法是确保 HashSet 行为正确和性能优良的基础。

掌握 HashSet<T> 的基本和高级用法，能够让你在各种需要去重、快速查找或集合运算的编程任务中编写出更简洁、更高效的代码。在选择 Set 实现时，根据是否需要保持元素有序来决定使用 HashSet<T> 还是 SortedSet<T>。记住避免在迭代时修改集合以及处理好多线程访问是安全使用 HashSet 的重要方面。

通过本文的详细解析，希望你对 C# 中的 Set 概念及 HashSet<T> 的用法有了全面而深入的理解，能够在未来的开发中 confidently 应用这一重要的数据结构。

发表评论

您的邮箱地址不会被公开。 必填项已用 * 标注

滚动至顶部