玩转 C# Set：从概念到实战应用 – wiki基地

作者： /

玩转 C# Set：从概念到实战应用

在现代软件开发中，高效地管理和操作数据集合是一项基本技能。我们经常需要处理列表、数组、字典等数据结构，但在某些特定场景下，我们需要一种能够保证元素唯一性，并且在查找、添加、删除操作上表现出卓越性能的数据结构。这时，Set（集合）就闪亮登场了。

在 C#/.NET 中，Set 的概念主要体现在 System.Collections.Generic 命名空间下的 HashSet<T> 和 SortedSet<T> 类。它们为我们提供了强大的工具来处理不包含重复元素的集合，并支持丰富的数学集合运算。

本文将带你深入理解 C# 中的 Set，从基本概念、实现原理，到核心操作、数学运算，再到各种实战应用场景，帮助你彻底玩转 C# Set。

第一部分：C# Set 的核心概念与基础

1. 什么是 Set？

在数学中，集合（Set）是若干元素的总体，最核心的特点是：

  • 无序性 (Unordered): 集合中的元素没有固定的顺序。
  • 唯一性 (Uniqueness): 集合中的元素是互不相同的。

例如，集合 {1, 2, 3} 和 {3, 1, 2} 是同一个集合，因为它们包含相同的唯一元素。集合中不允许出现重复的元素，比如 {1, 2, 2, 3} 不是一个标准的集合表示法，它等同于 {1, 2, 3}。

2. 为什么选择 Set？

在编程中，当我们遇到以下需求时，Set 常常是最佳选择：

  • 需要存储一组不重复的元素： Set 天然地保证了元素的唯一性，无需手动检查和去重。
  • 需要高效地进行成员资格检查： 判断某个元素是否存在于集合中。
  • 需要执行集合间的数学运算： 如求并集、交集、差集等。

相比于 List<T> 或 T[] 等允许重复元素且通常维护元素顺序的数据结构，Set 在处理唯一性需求和特定操作（如 Contains）时具有显著的性能优势。

3. C# 中的 Set 实现：HashSet<T> 和 SortedSet<T>

C#/.NET 提供了两种主要的 Set 实现：

  • HashSet<T>: 基于哈希表（Hash Table）实现。它提供了非常高效的添加、删除和查找操作，平均时间复杂度接近 O(1)。它的一个特点是不保证元素的顺序。元素的存储顺序取决于其哈希码和内部哈希表的实现细节。
  • SortedSet<T>: 基于自平衡二叉搜索树（如红黑树）实现。它不仅保证元素的唯一性，还按照元素的顺序存储。添加、删除和查找操作的平均时间复杂度是 O(log n)，其中 n 是集合中的元素数量。对于需要有序集合的场景，SortedSet<T> 是首选。

理解这两种实现背后的数据结构对于理解它们的性能特征至关重要。

HashSet<T> 详解：哈希的魔力

HashSet<T> 内部使用哈希表来存储元素。当你添加一个元素时，HashSet 会计算该元素的哈希码 (GetHashCode())，然后根据哈希码将元素存储在哈希表的相应位置。当你查找一个元素时，它也计算元素的哈希码，然后直接定位到可能的存储位置进行比较 (Equals())。

  • 优点:
    • 对于大多数操作（Add, Remove, Contains, Count），平均时间复杂度是 O(1)。这意味着无论集合有多大，这些操作通常都能在非常短的时间内完成。
    • 内存使用相对高效（虽然可能比 List 稍微高一些，因为需要额外的哈希表结构）。
  • 缺点:
    • 元素没有顺序，遍历时的顺序是不确定的。
    • 最坏情况下的性能可能退化到 O(n)，但这很少发生，通常是由于哈希冲突非常严重（所有元素的哈希码都相同或冲突严重）。

SortedSet<T> 详解：有序的力量

SortedSet<T> 内部使用一种自平衡二叉搜索树。当你添加一个元素时，它会通过比较操作 (CompareTo() 或提供的比较器) 找到元素在树中的正确位置并插入，同时保持树的平衡。查找和删除也类似，通过树的结构进行定位。

  • 优点:
    • 元素始终保持有序状态。遍历集合时，元素会按照升序排列。
    • 支持高效的范围查询（例如，查找大于某个值且小于另一个值的所有元素，尽管 C# 的 SortedSet 没有直接提供范围查询方法，但其有序性为实现此类操作提供了基础）。
    • 添加、删除、查找操作的时间复杂度是 O(log n)，性能稳定。
  • 缺点:
    • 性能通常不如 HashSet<T>（O(log n) vs O(1)），尤其是在集合非常大时。
    • 要求集合中的元素必须是可比较的（实现 IComparable<T> 或 IComparable 接口，或者在创建 SortedSet 时提供一个 IComparer<T>）。

4. 核心操作：增、删、查、清

HashSet<T> 和 SortedSet<T> 都提供了一套相似的核心操作：

“`csharp
// 使用 HashSet 示例
HashSet uniqueNames = new HashSet();

// 1. 添加元素 (Add)
// 如果元素已存在，Add 方法会返回 false，并且不会重复添加
bool addedJohn = uniqueNames.Add(“John”); // addedJohn is true
bool addedJane = uniqueNames.Add(“Jane”); // addedJane is true
bool addedJohnAgain = uniqueNames.Add(“John”); // addedJohnAgain is false (John already exists)

Console.WriteLine($”Set contains {uniqueNames.Count} elements.”); // Output: Set contains 2 elements.

// 2. 检查元素是否存在 (Contains)
bool containsJane = uniqueNames.Contains(“Jane”); // containsJane is true
bool containsPeter = uniqueNames.Contains(“Peter”); // containsPeter is false

// 3. 删除元素 (Remove)
// 如果元素存在并被成功删除，Remove 方法返回 true；否则返回 false
bool removedJane = uniqueNames.Remove(“Jane”); // removedJane is true
bool removedPeter = uniqueNames.Remove(“Peter”); // removedPeter is false (Peter was not in the set)

Console.WriteLine($”Set contains {uniqueNames.Count} elements after removal.”); // Output: Set contains 1 element (John).

// 4. 清空集合 (Clear)
uniqueNames.Clear();
Console.WriteLine($”Set contains {uniqueNames.Count} elements after clear.”); // Output: Set contains 0 elements.

// SortedSet 示例
SortedSet sortedNumbers = new SortedSet();
sortedNumbers.Add(5);
sortedNumbers.Add(2);
sortedNumbers.Add(8);
sortedNumbers.Add(2); // 2 is a duplicate, will not be added again

// 遍历 SortedSet，元素是有序的
Console.Write(“SortedSet elements: “);
foreach (int num in sortedNumbers)
{
Console.Write($”{num} “); // Output: 2 5 8
}
Console.WriteLine();

Console.WriteLine($”SortedSet contains 5: {sortedNumbers.Contains(5)}”); // Output: True
Console.WriteLine($”SortedSet count: {sortedNumbers.Count}”); // Output: 3
“`

5. Set 的数学运算

Set 数据结构最强大的特性之一是支持各种数学集合运算。HashSet<T> 和 SortedSet<T> 都提供了丰富的方法来实现这些运算，通常以 With 结尾，表示修改当前集合。

假设我们有两个集合 A 和 B：

  • A = {1, 2, 3}
  • B = {3, 4, 5}
运算类型 描述 结果示例 C# 方法
并集 (Union) 包含属于 A 或属于 B 的所有唯一元素。 {1, 2, 3, 4, 5} UnionWith(otherSet): 将 otherSet 中的元素添加到当前集合。
交集 (Intersection) 包含同时属于 A 和属于 B 的所有元素。 {3} IntersectWith(otherSet): 移除当前集合中不属于 otherSet 的元素。
差集 (Difference) 包含属于 A 但不属于 B 的所有元素。 {1, 2} ExceptWith(otherSet): 移除当前集合中属于 otherSet 的元素。
对称差集 (Symmetric Difference) 包含属于 A 或属于 B，但不同时属于两者的所有元素。换句话说，并集减去交集。 {1, 2, 4, 5} SymmetricExceptWith(otherSet): 修改当前集合，使其只包含存在于当前集合 或 otherSet 但不同时存在于两者中的元素。

此外，还有用于集合关系的检查：

关系类型 描述 结果示例 (A, B) C# 方法
子集 (Subset) A 的所有元素都在 B 中。可以是真子集 (A ≠ B) 或非真子集 (A = B)。 A⊆{1,2,3,4} 为 True IsSubsetOf(otherSet)
超集 (Superset) B 的所有元素都在 A 中。可以是真超集 (A ≠ B) 或非真超集 (A = B)。 {1,2,3,4}⊇A 为 True IsSupersetOf(otherSet)
真子集 (Proper Subset) A 的所有元素都在 B 中，且 A 不等于 B。 A⊂{1,2,3,4} 为 True IsProperSubsetOf(otherSet)
真超集 (Proper Superset) B 的所有元素都在 A 中，且 B 不等于 A。 {1,2,3,4}⊃A 为 True IsProperSupersetOf(otherSet)
重叠 (Overlap) A 和 B 至少有一个共同元素。 A 与 B={3,4,5} 为 True Overlaps(otherSet)
相等 (Set Equal) A 和 B 包含完全相同的元素（忽略顺序）。 A = {3,1,2} 为 True SetEquals(otherSet)

让我们看一些代码示例：

“`csharp
HashSet setA = new HashSet() { 1, 2, 3 };
HashSet setB = new HashSet() { 3, 4, 5 };

// 并集
HashSet unionSet = new HashSet(setA); // 创建 A 的副本
unionSet.UnionWith(setB);
Console.WriteLine($”Union of A and B: {string.Join(“, “, unionSet)}”); // Output: 1, 2, 3, 4, 5 (order may vary for HashSet)

// 交集
HashSet intersectSet = new HashSet(setA); // 创建 A 的副本
intersectSet.IntersectWith(setB);
Console.WriteLine($”Intersection of A and B: {string.Join(“, “, intersectSet)}”); // Output: 3

// 差集 (A – B)
HashSet differenceSet = new HashSet(setA); // 创建 A 的副本
differenceSet.ExceptWith(setB);
Console.WriteLine($”Difference (A – B): {string.Join(“, “, differenceSet)}”); // Output: 1, 2

// 对称差集
HashSet symmetricDifferenceSet = new HashSet(setA); // 创建 A 的副本
symmetricDifferenceSet.SymmetricExceptWith(setB);
Console.WriteLine($”Symmetric Difference: {string.Join(“, “, symmetricDifferenceSet)}”); // Output: 1, 2, 4, 5 (order may vary)

// 集合关系
HashSet setC = new HashSet() { 1, 2 };
HashSet setD = new HashSet() { 1, 2, 3, 4 };

Console.WriteLine($”Is C a subset of D? {setC.IsSubsetOf(setD)}”); // Output: True
Console.WriteLine($”Is D a superset of C? {setD.IsSupersetOf(setC)}”); // Output: True
Console.WriteLine($”Is C a proper subset of D? {setC.IsProperSubsetOf(setD)}”); // Output: True
Console.WriteLine($”Do setA and setC overlap? {setA.Overlaps(setC)}”); // Output: True (contain 1, 2)
Console.WriteLine($”Are setA and {{3, 1, 2}} set equals? {setA.SetEquals(new HashSet(){3, 1, 2})}”); // Output: True
“`

注意：除了 SetEquals 和关系检查方法 (IsSubsetOf, IsSupersetOf, IsProperSubsetOf, Overlaps) 不修改原集合外，UnionWith, IntersectWith, ExceptWith, SymmetricExceptWith 方法都会直接修改调用它们的集合。如果需要保留原集合，应先创建副本再进行运算。

6. 元素相等性：Equals 与 GetHashCode 的重要性

Set 的核心在于元素的唯一性。那么 Set 是如何判断两个元素是否相同的呢？

对于值类型（如 int, double, struct 等），Set 使用其值的比较来判断相等性。
对于引用类型（如 class），Set 默认使用对象的引用相等性（即是否指向同一个内存地址）。

然而，在大多数实际应用中，我们判断两个对象是否“相同”是基于它们的内容而不是引用。例如，两个不同的 Person 对象，如果它们的姓名和年龄都相同，我们可能认为它们是同一个“人”。

为了让 HashSet<T> 和 SortedSet<T>（以及 Dictionary<TKey, TValue> 等基于哈希或比较的数据结构）正确地处理自定义引用类型的唯一性，你需要为你的类重写 (override) Equals(object obj) 方法和 GetHashCode() 方法。

  • Equals(object obj)：定义了两个对象在逻辑上是否相等。
  • GetHashCode()：返回一个基于对象内容计算出的哈希码。对于相等的对象，GetHashCode() 必须返回相同的哈希码。反之不一定成立（不同的对象可能产生哈希冲突，返回相同的哈希码），但一个好的哈希函数应该尽量减少冲突。

SortedSet<T> 除了依赖 Equals 来判断唯一性外，还需要元素是可比较的，以便进行排序。默认情况下，它会尝试将元素转换为 IComparable<T> 或 IComparable 接口。如果你需要自定义排序逻辑，或者处理不可比较的类型，你需要提供一个实现了 IComparer<T> 接口的比较器。

示例：重写 Equals 和 GetHashCode

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

public Person(string name, int age)
{
    Name = name;
    Age = age;
}

// 重写 Equals 方法，基于内容判断相等性
public override bool Equals(object obj)
{
    if (obj == null || GetType() != obj.GetType())
    {
        return false;
    }

    Person other = (Person)obj;
    // 使用字符串比较Name，使用int比较Age
    return Name == other.Name && Age == other.Age;
}

// 重写 GetHashCode 方法，基于内容计算哈希码
// 对于相等的对象，哈希码必须相同
public override int GetHashCode()
{
    // 结合 Name 和 Age 的哈希码来生成新的哈希码
    // 可以使用 .NET Core / .NET 5+ 的 HashCode.Combine 方法 (推荐)
    // 或手动组合哈希码
    return HashCode.Combine(Name, Age); // 假设 Name 和 Age 不会为 null
    // 如果 Name 或 Age 可能为 null，需要进行 null 检查或处理
    // int hash = 17; // 选择一个素数
    // hash = hash * 23 + (Name != null ? Name.GetHashCode() : 0); // 乘以另一个素数
    // hash = hash * 23 + Age.GetHashCode();
    // return hash;
}

// 为了方便输出
public override string ToString()
{
    return $"{Name} ({Age})";
}

}

// 使用重写了 Equals 和 GetHashCode 的 Person 类
HashSet uniquePeople = new HashSet();

Person p1 = new Person(“Alice”, 30);
Person p2 = new Person(“Bob”, 25);
Person p3 = new Person(“Alice”, 30); // 和 p1 内容相同，但引用不同

uniquePeople.Add(p1);
uniquePeople.Add(p2);
bool addedP3 = uniquePeople.Add(p3); // 由于重写了 Equals 和 GetHashCode，p3 被认为是重复元素，不会被添加

Console.WriteLine($”Set contains {uniquePeople.Count} unique people.”); // Output: Set contains 2 unique people.
foreach (var person in uniquePeople)
{
Console.WriteLine(person); // Output: Alice (30), Bob (25) (顺序不确定)
}

// 对于 SortedSet，如果 Person 需要放到 SortedSet 里，它需要实现 IComparable 或提供 IComparer
// 例如，按年龄排序
public class PersonAgeComparer : IComparer
{
public int Compare(Person x, Person y)
{
if (x == null || y == null)
{
if (x == null && y == null) return 0;
return x == null ? -1 : 1; // null 被认为小于非 null
}
// 按照年龄比较
return x.Age.CompareTo(y.Age);
}
}

SortedSet sortedPeopleByAge = new SortedSet(new PersonAgeComparer());
sortedPeopleByAge.Add(new Person(“Charlie”, 28));
sortedPeopleByAge.Add(new Person(“Alice”, 30));
sortedPeopleByAge.Add(new Person(“David”, 25));
sortedPeopleByAge.Add(new Person(“Charlie”, 28)); // 内容重复，不会添加

Console.WriteLine(“\nSortedSet people by age:”);
foreach (var person in sortedPeopleByAge)
{
Console.WriteLine(person); // Output: David (25), Charlie (28), Alice (30)
}
“`

注意： 如果你使用自定义类作为 Set 的元素类型而没有正确重写 Equals 和 GetHashCode，HashSet 将会错误地将内容相同的不同对象实例视为不相同的元素，导致 Set 中出现“逻辑上”重复的元素。对于 SortedSet，如果你没有实现 IComparable<T> 或提供 IComparer<T>，且类型不是基本类型，会抛出运行时错误。

第二部分：C# Set 的实战应用

掌握了 Set 的基本概念和操作，我们来看看它在实际开发中有哪些常见的应用场景。

1. 高效去重

这是 Set 最常见和直接的应用。如果你有一个包含重复元素的集合（如 List<T>），并想快速得到一个只包含唯一元素的新集合，使用 HashSet<T> 是非常方便且高效的方法。

“`csharp
List numbersWithDuplicates = new List() { 1, 2, 3, 2, 4, 1, 5, 3 };

// 使用 HashSet 快速去重
HashSet uniqueNumbers = new HashSet(numbersWithDuplicates);

Console.WriteLine($”Original list count: {numbersWithDuplicates.Count}”); // Output: 8
Console.WriteLine($”Unique set count: {uniqueNumbers.Count}”); // Output: 5

Console.Write(“Unique numbers: “);
foreach (int num in uniqueNumbers)
{
Console.Write($”{num} “); // Output: 1 2 3 4 5 (顺序不确定)
}
Console.WriteLine();

// 如果需要去重后的结果仍然是 List
List uniqueNumbersList = new List(new HashSet(numbersWithDuplicates));
// 或者使用 LINQ 的 Distinct() 方法，但对于大集合，Set 方式通常更高效
// List uniqueNumbersListLinq = numbersWithDuplicates.Distinct().ToList();
“`

性能考量： 使用 new HashSet<T>(collection) 构造函数进行去重，其时间复杂度大致取决于原集合的大小 n，平均为 O(n)。而如果使用 LINQ 的 Distinct() 方法，它内部也可能采用类似哈希表的方式进行去重，性能相似，但 HashSet 的意图更明确，有时性能表现更稳定。对于需要保留原始顺序的去重，Set 则不适用，这时需要使用 LINQ 的 Distinct()（它保留第一个出现的元素顺序）或其他自定义方法。

2. 快速成员资格检查

当需要频繁检查某个元素是否存在于一个大型集合中时，Set 的 Contains() 方法提供了 O(1) 的平均时间复杂度，远优于 List<T> 的 O(n) 查找。

“`csharp
// 假设有一个包含百万级用户ID的列表，我们需要快速判断一个ID是否存在
List allUserIdsList = Enumerable.Range(0, 1000000).Select(i => $”user_{i}”).ToList();
// 将这些ID放入 HashSet
HashSet allUserIdsSet = new HashSet(allUserIdsList);

string userIdToFind1 = “user_500000”;
string userIdToFind2 = “non_existent_user”;

// 使用 List 查找 (O(n))
var watchList = System.Diagnostics.Stopwatch.StartNew();
bool foundInList = allUserIdsList.Contains(userIdToFind1);
watchList.Stop();
Console.WriteLine($”Found ‘{userIdToFind1}’ in List: {foundInList} (Time: {watchList.ElapsedMilliseconds}ms)”);

// 使用 HashSet 查找 (O(1) 平均)
var watchSet = System.Diagnostics.Stopwatch.StartNew();
bool foundInSet = allUserIdsSet.Contains(userIdToFind1);
watchSet.Stop();
Console.WriteLine($”Found ‘{userIdToFind1}’ in Set: {foundInSet} (Time: {watchSet.ElapsedMilliseconds}ms)”);

watchSet.Restart();
bool foundInSet2 = allUserIdsSet.Contains(userIdToFind2);
watchSet.Stop();
Console.WriteLine($”Found ‘{userIdToFind2}’ in Set: {foundInSet2} (Time: {watchSet.ElapsedMilliseconds}ms)”);

// 你会发现对于大集合，HashSet 的查找时间几乎恒定且非常快。
“`

这个特性在许多场景下都非常有用，例如：

  • 用户权限检查： 检查用户 ID 是否在“管理员”集合中。
  • 黑名单/白名单： 快速判断一个 IP 地址、邮箱地址等是否在黑名单或白名单中。
  • 数据验证： 检查输入的某个值是否在允许的值集合中。

3. 集合比较与分析

Set 的数学运算方法在比较和分析不同集合时非常强大。

  • 找出两个列表中共同的元素 (交集): 比如，找出两个用户的共同好友。
  • 找出在一个列表但不在另一个列表的元素 (差集): 比如，找出某个用户关注了但没有被对方关注的人。
  • 找出至少存在于其中一个列表的元素 (并集): 比如，统计所有参与过某项活动的用户总数（即使有人参与多次，也只统计一次）。
  • 检查包含关系： 判断一个小的集合是否是另一个大集合的子集（例如，检查用户选择的标签是否都在系统预设的有效标签集合内）。

“`csharp
List user1Interests = new List() { “Programming”, “Music”, “Reading”, “Coding” };
List user2Interests = new List() { “Music”, “Sports”, “Reading”, “Hiking” };

HashSet set1Interests = new HashSet(user1Interests);
HashSet set2Interests = new HashSet(user2Interests);

// 共同兴趣 (交集)
HashSet commonInterests = new HashSet(set1Interests);
commonInterests.IntersectWith(set2Interests);
Console.WriteLine($”Common Interests: {string.Join(“, “, commonInterests)}”); // Output: Music, Reading (顺序不确定)

// User1 有但 User2 没有的兴趣 (差集)
HashSet user1OnlyInterests = new HashSet(set1Interests);
user1OnlyInterests.ExceptWith(set2Interests);
Console.WriteLine($”User1 only Interests: {string.Join(“, “, user1OnlyInterests)}”); // Output: Programming, Coding (顺序不确定)

// User2 有但 User1 没有的兴趣 (差集)
HashSet user2OnlyInterests = new HashSet(set2Interests);
user2OnlyInterests.ExceptWith(set1Interests);
Console.WriteLine($”User2 only Interests: {string.Join(“, “, user2OnlyInterests)}”); // Output: Sports, Hiking (顺序不确定)

// 总共有哪些不同的兴趣 (并集)
HashSet allInterests = new HashSet(set1Interests);
allInterests.UnionWith(set2Interests);
Console.WriteLine($”All unique Interests: {string.Join(“, “, allInterests)}”); // Output: Programming, Music, Reading, Coding, Sports, Hiking (顺序不确定)

// 判断一个兴趣集合是否是另一个的子集
HashSet programmingRelated = new HashSet() { “Programming”, “Coding” };
Console.WriteLine($”Are programming interests subset of User1 interests? {programmingRelated.IsSubsetOf(set1Interests)}”); // Output: True
“`

4. 实现特定算法

Set 是实现许多算法的基础。例如：

  • 查找文本中唯一的单词： 遍历文本，将每个单词添加到 HashSet<string> 中。
  • 图遍历算法 (如 BFS/DFS 中的访问标记): 使用 HashSet 来存储已经访问过的节点，以便 O(1) 检查是否重复访问。
  • 查找数组中是否存在重复元素： 将数组元素逐个添加到 HashSet 中，如果在添加时 Add 方法返回 false，则说明找到了重复元素。

“`csharp
// 查找文本中的唯一单词
string text = “This is a sample text with sample words. This text contains words.”;
string[] words = text.ToLower().Replace(“.”, “”).Split(new[] { ‘ ‘, ‘,’ }, StringSplitOptions.RemoveEmptyEntries);

HashSet uniqueWords = new HashSet(words);

Console.WriteLine($”Original word count: {words.Length}”); // Output: 11
Console.WriteLine($”Unique word count: {uniqueWords.Count}”); // Output: 8

Console.WriteLine(“Unique words:”);
foreach (string word in uniqueWords)
{
Console.WriteLine(word); // Output: this, is, a, sample, text, with, words, contains (顺序不确定)
}

// 判断数组中是否有重复元素
int[] numbers = { 1, 5, 2, 8, 2, 9, 5 };
HashSet seenNumbers = new HashSet();
bool hasDuplicates = false;
foreach (int number in numbers)
{
if (!seenNumbers.Add(number)) // TryAdd 在 .NET Core 2.1+ 或 .NET Standard 2.1+ 也可用
{
hasDuplicates = true;
Console.WriteLine($”Duplicate found: {number}”); // Output: Duplicate found: 2, Duplicate found: 5
// 如果只需要知道是否有重复，找到第一个就可以 break
// break;
}
}
Console.WriteLine($”Array has duplicates: {hasDuplicates}”); // Output: Array has duplicates: True
“`

5. 性能考量与选择：HashSet vs SortedSet vs List vs Dictionary

理解不同数据结构的性能特性对于做出正确的选择至关重要。

特性/数据结构 List<T> Dictionary<TKey, TValue> HashSet<T> SortedSet<T>
存储元素 有序，允许重复 键值对，键唯一，值允许重复 无序，元素唯一 有序，元素唯一
底层实现 数组 哈希表 哈希表 自平衡二叉搜索树（如红黑树）
Add O(1) 平均 (扩容时 O(n)) O(1) 平均 (扩容时 O(n)) O(1) 平均 (扩容时 O(n)) O(log n)
Remove O(n) O(1) 平均 O(1) 平均 O(log n)
Contains O(n) O(1) 平均 O(1) 平均 O(log n)
查找/索引 O(1) 按索引 O(1) 平均 按键 不支持按索引，按值 O(1) 平均 O(log n) 按值
遍历顺序 添加顺序 不确定 (通常取决于哈希) 不确定 (取决于哈希) 元素自然顺序或比较器顺序
内存占用 相对较低 中等 (键值对) 中等 (哈希表结构) 中等 (树节点结构)
元素要求 无特定要求 键需要重写 Equals/GetHashCode 需要重写 Equals/GetHashCode 需要 IComparable<T> 或 IComparer<T>

选择建议：

  • 需要有序序列且允许重复： List<T> 或 T[]。
  • 需要通过唯一键快速查找值： Dictionary<TKey, TValue>。
  • 需要快速进行成员检查和去重，且顺序不重要： HashSet<T> (首选)。
  • 需要快速进行成员检查和去重，且元素必须保持有序： SortedSet<T>。
  • 需要执行集合数学运算： HashSet<T> 或 SortedSet<T>。如果顺序不重要，HashSet 通常更快；如果需要有序结果或元素本身需要比较才能判断相等（对于 SortedSet 而言，顺序和相等性都依赖比较器），则使用 SortedSet。

什么时候不适合用 Set？

  • 需要根据索引访问元素。
  • 需要存储重复的元素。
  • 需要严格按照元素添加的顺序或自定义的其他顺序（如果 HashSet 顺序不满足需求）。

第三部分：进阶话题与注意事项

1. 并发：线程安全问题

HashSet<T> 和 SortedSet<T> 都不是线程安全的。如果在多线程环境中对同一个 Set 实例进行写操作（Add, Remove, Clear 等），可能会导致不可预测的行为或数据损坏。

如果你需要在多线程环境中安全地使用 Set，可以考虑以下方法：

  • 加锁： 在访问 Set 时使用 lock 关键字或其他同步机制保护 Set。
  • 使用并发集合： .NET 提供了 System.Collections.Concurrent 命名空间下的并发集合。虽然没有直接的 ConcurrentSet<T>，但你可以使用 ConcurrentDictionary<TKey, TValue> 来模拟 Set，例如使用元素本身作为键，值设为占位符（如 bool 或 byte），利用 TryAdd 方法的原子性来保证添加的唯一性。

“`csharp
// 模拟线程安全的 Set
ConcurrentDictionary concurrentSet = new ConcurrentDictionary();

// 多线程添加元素
Parallel.ForEach(Enumerable.Range(0, 10000), i =>
{
string item = $”item_{i % 100}”; // 会产生重复
concurrentSet.TryAdd(item, 0); // TryAdd 是原子的，如果键已存在返回 false
});

Console.WriteLine($”Concurrent set count: {concurrentSet.Count}”); // Output: 100 (unique items)
“`

2. 容量与性能

HashSet<T> 在内部使用哈希表，其性能受哈希表的容量和负载因子影响。当你添加的元素数量超过哈希表的当前容量乘以负载因子时，哈希表需要重新分配更大的空间并重新计算所有元素的哈希值并重新分布（rehashing），这是一个 O(n) 的操作，会影响添加操作的平均性能。

如果你事先知道集合的大致大小，可以在创建 HashSet 时指定一个初始容量，这可以减少重新哈希的次数，从而提高性能。

csharp
// 创建一个预计存放10000个元素的 HashSet
HashSet<string> largeSet = new HashSet<string>(10000);

对于 SortedSet<T>，由于其基于树结构，容量的概念不那么直接影响单次操作性能，但树的高度会随着元素数量的增加而增加，O(log n) 中的 n 就是集合大小。

3. 自定义比较器 (IEqualityComparer<T> 和 IComparer<T>)

之前提到，对于自定义引用类型，你需要重写 Equals 和 GetHashCode 来定义相等性，以及实现 IComparable<T> 或提供 IComparer<T> 来定义排序。

HashSet<T> 允许你在创建时提供一个实现了 IEqualityComparer<T> 接口的对象。这个接口包含 Equals(T x, T y) 和 GetHashCode(T obj) 方法。提供自定义比较器的好处是：

  • 你可以为同一个类型定义不同的相等性规则（例如，字符串比较是否区分大小写）。
  • 你可以对你不拥有源代码的类型定义相等性规则（因为你不能修改它的 Equals 和 GetHashCode 方法）。

SortedSet<T> 允许你在创建时提供一个实现了 IComparer<T> 接口的对象。这个接口包含 Compare(T x, T y) 方法。提供自定义比较器的好处与 HashSet 类似：

  • 为同一个类型定义不同的排序规则（例如，Person 可以按年龄排序，也可以按姓名排序）。
  • 对不实现 IComparable<T> 的类型进行排序。

“`csharp
// 示例：不区分大小写的字符串 HashSet
public class CaseInsensitiveStringComparer : IEqualityComparer
{
public bool Equals(string x, string y)
{
return string.Equals(x, y, StringComparison.OrdinalIgnoreCase);
}

public int GetHashCode(string obj)
{
    return obj?.ToLowerInvariant().GetHashCode() ?? 0;
    // 或者使用 string.GetHashCode(StringComparison.OrdinalIgnoreCase) 在 .NET Core / .NET 5+
    // return obj?.GetHashCode(StringComparison.OrdinalIgnoreCase) ?? 0;
}

}

HashSet caseInsensitiveSet = new HashSet(new CaseInsensitiveStringComparer());
caseInsensitiveSet.Add(“Apple”);
caseInsensitiveSet.Add(“apple”); // 视为重复，不会添加
caseInsensitiveSet.Add(“Banana”);

Console.WriteLine($”Case-insensitive set count: {caseInsensitiveSet.Count}”); // Output: 2
Console.WriteLine($”Contains ‘APPLE’? {caseInsensitiveSet.Contains(“APPLE”)}”); // Output: True

// 示例：Person 按姓名长度排序的 SortedSet
public class PersonNameLengthComparer : IComparer
{
public int Compare(Person x, Person y)
{
if (x == null || y == null)
{
if (x == null && y == null) return 0;
return x == null ? -1 : 1;
}
// 按照姓名长度比较
int lengthComparison = x.Name.Length.CompareTo(y.Name.Length);
if (lengthComparison != 0)
{
return lengthComparison;
}
// 如果长度相同，则按姓名本身比较以保证唯一性
return string.Compare(x.Name, y.Name, StringComparison.Ordinal);
}
}

SortedSet sortedPeopleByNameLength = new SortedSet(new PersonNameLengthComparer());
sortedPeopleByNameLength.Add(new Person(“Bob”, 25)); // Length 3
sortedPeopleByNameLength.Add(new Person(“Alice”, 30)); // Length 5
sortedPeopleByNameLength.Add(new Person(“David”, 28)); // Length 5
sortedPeopleByNameLength.Add(new Person(“Eve”, 22)); // Length 3

Console.WriteLine(“\nSortedSet people by name length:”);
foreach (var person in sortedPeopleByNameLength)
{
Console.WriteLine(person);
// Output (顺序):
// Bob (25)
// Eve (22)
// Alice (30)
// David (28)
// 注意：相同长度的元素 (Alice/David, Bob/Eve) 内部顺序取决于比较器对相等长度的处理，以及 SortedSet 的内部结构。
// 在这个例子中，我们按姓名本身比较，所以 Bob 在 Eve 前面，Alice 在 David 前面。
}
“`

总结

C# 中的 HashSet<T> 和 SortedSet<T> 是处理唯一元素集合的强大工具。

  • HashSet<T> 提供平均 O(1) 的高性能，适用于顺序不重要且需要快速查找、添加、删除和去重的场景。
  • SortedSet<T> 提供 O(log n) 的性能，并保证元素的有序性，适用于需要有序集合或依赖元素比较器的场景。

理解它们底层的数据结构（哈希表和平衡二叉树）以及它们如何处理元素相等性（Equals 和 GetHashCode）和排序（IComparable<T> 或 IComparer<T>）是高效使用它们的关键。

从基本的去重和成员检查，到复杂的集合数学运算，再到特定算法的实现，Set 在各种实战应用中都能发挥重要作用。在面对需要管理唯一数据集合的问题时，请务必考虑 Set，它往往能提供比 List<T> 或其他集合类型更简洁、更高效的解决方案。

希望本文能帮助你全面理解并熟练应用 C# Set，在你的开发工作中游刃有余！

发表评论

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

滚动至顶部