C# HashSet：唯一元素、Contains 与集合运算

HashSet<T> 是一种每个元素最多只出现一次的集合。它没有索引，也没有保证的顺序，作为交换，它能在大约常数时间内判断元素是否存在：在一百万个标签中找一个，和在十个中找一个花的时间差不多。

添加元素：Add 返回 bool

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var tags = new HashSet<string> { "sale", "new" };

        Console.WriteLine(tags.Add("gift"));  // added
        Console.WriteLine(tags.Add("sale"));  // already present
        Console.WriteLine(tags.Count);

        Console.WriteLine(tags.Contains("new"));
        Console.WriteLine(tags.Remove("new"));
        Console.WriteLine(tags.Remove("used")); // not there: false, no exception
        Console.WriteLine(tags.Count);
    }
}

输出：

True
False
3
True
True
False
2

添加重复项不算错误；Add 只是返回 false，集合保持不变。这个返回值是该方法最有用的地方。它把“我见过这个吗？”和“记住它”合并成了一次调用：

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string[] signups = { "ana@x.com", "ben@x.com", "ana@x.com", "cy@x.com", "ben@x.com" };
        var seen = new HashSet<string>();

        foreach (string email in signups)
        {
            if (!seen.Add(email))
            {
                Console.WriteLine("Duplicate: " + email);
            }
        }
        Console.WriteLine(seen.Count + " unique");
    }
}

输出：

Duplicate: ana@x.com
Duplicate: ben@x.com
3 unique

为什么 Contains 很快

List<T>.Contains 会依次把值和每个元素比较，所以它的开销随列表增长。HashSet<T> 则计算元素的哈希码，直接跳到这个哈希码对应的桶，只比较存放在那里的少数几个元素。对于循环内部的存在性检查，这会把一个 O(n) 的步骤变成 O(1)，也会把两个列表的嵌套循环变成一次遍历：

// Slow on large inputs: Contains scans bannedList for every order.
var flagged = orders.Where(o => bannedList.Contains(o.CustomerId));

// Fast: build the set once, then each lookup is constant time.
var banned = new HashSet<int>(bannedList);
var flagged2 = orders.Where(o => banned.Contains(o.CustomerId));

构建集合需要遍历一次列表，所以只有当你查找的次数不止寥寥几次时才划算。

对列表去重

常见的方法有三种，区别在于顺序会怎样：

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        var cities = new List<string> { "Lima", "Oslo", "Lima", "Pune", "Oslo", "Kyiv" };

        // 1. LINQ Distinct: new list, first occurrences in original order
        List<string> unique = cities.Distinct().ToList();
        Console.WriteLine(string.Join(", ", unique));

        // 2. A set: unique, but a set has no guaranteed order
        var set = new HashSet<string>(cities);
        Console.WriteLine(set.Count);

        // 3. In place, keeping order: RemoveAll with a seen-set
        var seen = new HashSet<string>();
        cities.RemoveAll(c => !seen.Add(c));
        Console.WriteLine(string.Join(", ", cities));
    }
}

输出：

Lima, Oslo, Pune, Kyiv
4
Lima, Oslo, Pune, Kyiv

当你想得到一个列表时，Distinct 是合适的默认选择。原地去重的版本之所以可行，是因为 RemoveAll 会按顺序对每个元素调用一次谓词：对于第二个及之后的副本，seen.Add 返回 false，所以被删除的正好是这些副本。

集合运算：并集、交集、差集

HashSet<T> 提供了集合论中的各种运算。...With 系列方法会修改调用它们的那个集合，并且不返回任何值。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string Show(HashSet<string> s)
    {
        return string.Join(", ", s.OrderBy(x => x));
    }

    static void Main()
    {
        string[] monday = { "Ana", "Ben", "Chloe" };
        string[] tuesday = { "Ben", "Chloe", "Dev" };

        var either = new HashSet<string>(monday);
        either.UnionWith(tuesday);             // in either list
        Console.WriteLine("Union:     " + Show(either));

        var both = new HashSet<string>(monday);
        both.IntersectWith(tuesday);           // in both
        Console.WriteLine("Intersect: " + Show(both));

        var onlyMonday = new HashSet<string>(monday);
        onlyMonday.ExceptWith(tuesday);        // in monday, not tuesday
        Console.WriteLine("Except:    " + Show(onlyMonday));

        var oneDay = new HashSet<string>(monday);
        oneDay.SymmetricExceptWith(tuesday);   // in exactly one
        Console.WriteLine("Symmetric: " + Show(oneDay));

        Console.WriteLine(both.IsSubsetOf(monday));
        Console.WriteLine(either.IsSupersetOf(tuesday));
        Console.WriteLine(onlyMonday.Overlaps(tuesday));
        Console.WriteLine(new HashSet<int> { 1, 2 }.SetEquals(new[] { 2, 1, 1 }));
    }
}

输出：

Union:     Ana, Ben, Chloe, Dev
Intersect: Ben, Chloe
Except:    Ana
Symmetric: Ana, Dev
True
True
False
True

参数可以是任何 IEnumerable<T>：数组、列表或另一个集合。SetEquals 会忽略参数中的顺序和重复项。辅助方法 Show 在打印前先排序，因为集合的遍历顺序是不能依赖的。

LINQ 有对应的方法，它们返回一个新序列，不改动输入：monday.Union(tuesday)、monday.Intersect(tuesday)、monday.Except(tuesday)。当你不想修改集合，或者输入是列表时，就用这些方法。

为自己的类自定义相等比较

集合通过 GetHashCode 和 Equals 判断“是否是同一个元素”。对于没有重写这两个方法的类，它们都基于对象的标识，所以两个字段相同的对象是两个不同的元素：

using System;
using System.Collections.Generic;

class Point
{
    public int X, Y;
    public Point(int x, int y) { X = x; Y = y; }
}

class Coord
{
    public int X, Y;
    public Coord(int x, int y) { X = x; Y = y; }

    public override bool Equals(object obj)
    {
        var other = obj as Coord;
        return other != null && other.X == X && other.Y == Y;
    }

    public override int GetHashCode()
    {
        unchecked { return X * 397 ^ Y; }
    }
}

class Program
{
    static void Main()
    {
        var points = new HashSet<Point> { new Point(1, 2), new Point(1, 2) };
        Console.WriteLine(points.Count); // 2: compared by reference

        var coords = new HashSet<Coord> { new Coord(1, 2), new Coord(1, 2) };
        Console.WriteLine(coords.Count); // 1: compared by value
        Console.WriteLine(coords.Contains(new Coord(1, 2)));
    }
}

输出：

2
1
True

规则是：Equals 相等的对象必须返回相同的 GetHashCode。如果只重写 Equals，集合会去错误的桶里查找，仍然会出现重复项。在 .NET Core 2.1 及以上版本中，HashCode.Combine(X, Y) 无需手写运算就能生成一个好的哈希码。

当你无法修改这个类，或者某个集合需要不同的“相同”标准时，给构造函数传入一个 IEqualityComparer<T>。字符串自带现成的比较器：

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var extensions = new HashSet<string>(StringComparer.OrdinalIgnoreCase) { ".jpg", ".png" };
        Console.WriteLine(extensions.Contains(".JPG"));
        Console.WriteLine(extensions.Add(".PNG"));
        Console.WriteLine(extensions.Count);
    }
}

输出：

True
False
2

在 C# 9 及以上版本中，record 会为你生成基于值的 Equals 和 GetHashCode，所以 record Point(int X, int Y); 不需要额外代码就能用在集合中。

对象在集合中时，永远不要修改参与计算 GetHashCode 的字段。对象仍然留在按旧哈希码对应的桶里，于是 Contains 和 Remove 就再也找不到它了。

顺序与 SortedSet

HashSet<T> 的遍历顺序应当视为任意的。如果需要元素有序，就在打印时排序（set.OrderBy(x => x)），或者使用 SortedSet<T>，它始终保持元素有序，并提供 Min、Max 和范围查询，每次操作的开销是 O(log n)：

var ranks = new SortedSet<int> { 30, 10, 20 };
Console.WriteLine(string.Join(", ", ranks)); // 10, 20, 30
Console.WriteLine(ranks.Min);                // 10

HashSet、List 与 Dictionary 的对比

集合就是只有键、没有值的字典。如果你发现自己写 Dictionary<string, bool> 只是为了记录某个元素是否存在，那么 HashSet<string> 能更清楚地表达同样的意思。

常见错误

• 指望有顺序。 集合没有可以依赖的顺序；请排序，或者使用 SortedSet<T>。
• 自定义类没有 Equals 和 GetHashCode。 看起来相等的对象会成为不同的元素。
• 只重写 Equals。 一定要同时重写 GetHashCode。
• 添加元素后再修改它。 集合就再也找不到它了。
• 对集合使用索引。 set[0] 无法编译；集合没有索引。如果需要位置，用 ToList() 转换。