本文地址：https://www.cnblogs.com/oberon-zjt0806/p/12355028.html
本文遵循CC BY-NC-SA 4.0协议，转载请注明出处。

一个故事……

在C#中，HashSet是一种叫做哈希集的泛型的数据容器（Generic Collection，巨硬的官方术语称Collection为集合，但区别于Set的数学集合概念，我称之为数据容器（简称容器），泛型数据容器一下简称泛型容器）。
C#中泛型容器是通过系统标准库的命名空间System.Collections.Generic提供的，例如ArrayList、Dictionary……
而HashSet是在.NET Framework 3.5引入的。

一个繁荣的遥远国度：泛型容器

数据容器其实就是用于管理数据的数据结构（Data Structure,DS），用于存储一组数据，而泛型指的是这些容器是针对所有的对象类型的泛型类，因而在使用时必须给出容器所容纳的数据类型，以List为例：

List myList = new List();                 // 错误，List是泛型容器，必须给定List的容纳类型。
List<string> myList = new List<string>(); // 正确，这是一个存储若干字符串的列表容器。

但是我也不确定容器里能放些什么东西啊

尽管不推荐非纯类型的数据容器的存在，泛型约束统一类型的好处在于方便编写通用方法进行统一处理，但实际情况是迫于客观条件这种混合类型的容器是存在并且是大量存在的。
一般来说，我们允许存在共同继承关系的类以多态的形式存在于一个容器中：

Pigeon pigeon = new Pigeon("咕咕咕"); // class Pigeon : Bird
Cuckoo cuckoo = new Cuckoo("子规");   // class Cuckoo : Bird
List<Bird> flock = new List<Bird>() { pigeon,cuckoo }; // 正确，pigeon和cuckoo可以被视为Bird的多态
                                                       // 换句话说，pigeon和cuckoo都可被看作Bird类型

但如果没有共同继承关系呢？？比如同时存储整数和字符串？？

不管怎么说，C#里所有类都隐性继承System.Object即object，因此所有类都可以被装箱为object类型，那么这种情况下可以使用装箱的容器，也就是泛型提供为object的容器：

List<string> texts = new List<string>() { "Hello", "World", "C#" }; //这个列表里只能放入字符串
List<object> stuffs = new List<object>() { 1, "a", 2.0f}; //这个列表什么都能往里放

一个英勇的皇家骑士：HashSet

当然了，HashSet也是一个泛型容器，也就是说在使用的时候也得是HashSet<T>才行。

不过，前面所说的List是一个典型的顺序列表，也就是说List是线性容器，其内部元素有序排列且可重复出现，而HashSet是集合容器，具有与数学上的集合类似的性质：

1. 元素是唯一的
2. 元素是无序的

而HashSet就是保证这两点的容器，在HashSet中每种元素有且仅有一个（唯一性），以及其中的元素不具备严格的顺序性（无序性），此外
注意，这里说的无序，并不是指这些数据是毫无位置关系的，因为无论如何内存管理数据的机制依然是顺序的存储，也就是说即使是HashSet声称其元素无序，但实际上内部的元素是存在一个固有顺序的，只是这个顺序不被外界所关心且在发生修改时很容易打破这种顺序关系，因此HashSet对外体现出一种“顺序无关”的状态，这才是无序性的体现，不管怎么说HashSet也实现了IEnumerable<T>，实现了IEnumerable<T>接口的容器都是有固有的存储位序的，否则迭代是不可能的。

值类型的HashSet

HashSet<int> integers = new HashSet<int>(){ 1,2,3 }; // 一个整数集合，包含1，2，3
integers.Add(4); // 现在包含1，2，3，4了
integers.Add(2); // integers没有变化，因为已经包含2了
var a = integers[1]; // 错误，HashSet是无序容器，不能使用索引器进行位序访问

这里很明显，对于值类型的元素，只要HashSet中有相等者存在，那么他就不会被重复加入到其中，这样保证了唯一性，而HashSet对外不暴露顺序或随机访问的入口，体现了HashSet的无序性。

引用类型的HashSet

// 为了简单这里不封装了，直接上字段
class Student 
{
    public int id; 
    public string name;
    public Student(int id, string name)
    {
        this.id = id;
        this.name = name;
    }
}

class Program
{
    public static void Main(string[] args)
    {
        Student s1 = new Student(1, "Tom");
        Student s2 = new Student(2, "Jerry");        
        Student s3 = s1;
        HashSet<Student> students = new HashSet<Student>();
        students.Add(s1); // s1被加入students中
        students.Add(s2); // s2被加入students中
        students.Add(s3); // 没有变化，s1已存在
    }
}

可以看到，相同的元素也并没有被加进去，但是，如果我改一下……

        //前面不写了，直接写Main里的东西
        Student s1 = new Student(1, "Tom");
        Student s2 = new Student(2, "Jerry");  
        Student s3 = new Student(1, "Tom");
        HashSet<Student> students = new HashSet<Student>();
        students.Add(s1); // s1被加入students中
        students.Add(s2); // s2被加入students中
        students.Add(s3); // s3被加入students中

明明s1和s3长得也一毛一样，为什么这次加进去了呢？？

当然，如果知道什么是引用类型的朋友肯定看出了问题关键，前者的s1和s3是同一个引用，也就是同一个对象，因为Student s3 = s1;的时候并不将s1拷贝给s3，而是让两者为同一个东西，而后者的s3只是属性值和s1一致，但实际上s3是新建出来的对象。

由此可以看出，HashSet对于引用类型的唯一性保障采取的是引用一致性判断，这也是我为什么在前者中对students.Add(s3)操作给的注释是// 没有变化，s1已存在而不是// 没有变化，s3已存在。

另外一个……故……事？？

当然，一般情况下我们认为只要id和name相等的两个Student其实就是同一个人。即使是s1和s3都被定义为new Student(1,"Tom")，我们也不希望会被重复添加进来。
我们了解了HashSet的唯一性，因此我们要想方设法让HashSet认为s1和s3是相同的。

一对家喻户晓的双刀：==和Equals

我们当然会很容易的想到：

不就是让你们看起来被认为相等嘛，那我就重写你们的相等判定的不就好了么？？

巧合的是，任何一个（继承自object的）类都提供了两个东西：Equals方法和==运算符。
而且，我们了解，对于引用类型来说（string被魔改过除外，我个人理解是string已经算是值类型化了），==和Equals都是可重载的，即使不重载，在引用类型的视角下==和Equals从功能上是一致的。

Student s4 = new Student(1,"Tom");
Student s5 = new Student(1,"Tom");
Student s6 = s4;

Console.WriteLine($"s4==s5:{s4==s5} s4.Equals(s5):{s4.Equals(s5)}");
Console.WriteLine($"s4==s6:{s4==s6} s4.Equals(s6):{s4.Equals(s6)}");

输出结果为：

s4==s5:False s4.Equals(s5):False
s4==s6:True s4.Equals(s6):True

注意：
在引用视角下，==和Equals在默认条件下完全相同的，都是判别引用一致性，只是可以被重载或改写为不同的功能函数。但==和Equals确实有不同之处，主要是体现在值类型和装箱的情况下，但我们目前不打算考虑这个区别。

然而家喻户晓终究成了旧日传说

因此我们很容易的会考虑改写这两个函数中的任意一个，又或者两个一起做，类似于：

class Student 
{
    public int id; 
    public string name;
    public Student(int id, string name)
    {
        this.id = id;
        this.name = name;
    }
    
    public override bool Equals(object o)
    {
        if(o is Student s)
            return id == s.id && name = s.name;
        else
            return false;
    }
    public static bool operator==(Student s1,Student s2)
    {
        return (s1 is null ^ s2 is null) && (s1.Equals(s2));
    }
}

当然这样做了一溜十三招之后，带回去重新试你会发现：

毛用都没有！！！

是的，这给了我们一个结论：和C++里的set不一样，HashSet的相等性判定并不依赖于这两个函数。

一把开天辟地的神坛巨锤：ReferenceEquals

万念俱灰的我们查阅了msdn，发现引用的一致性判断工作最终落到了object的另外一个方法上：object.ReferenceEquals，当其他==或者Equals被改写掉而丧失引用一致性判断的时候这个方法做最后的兜底工作，那么从上面的结论来看的话，既然HashSet使用引用一致性判定相等的话，那么我们如果能重载这个函数使之认为两者相等，目的就达成了……

然而开天辟地需要使出洪荒之力

重载ReferenceEquals……说的轻松，轻松得我们都迫不及待要做了，然后我们意外的发现：

object.ReferenceEquals是静态方法，无法改写……

无法改写的话就没有意义了，看来这个方法也行不通，是啊，反过来仔细想想的话，如果最底层的引用一致性判断被能被改写的话那才是真正的灾难，所以这玩意怎么可能随便让你乱改。

最后的故事

绕了这么一大圈，我们不妨回到HashSet自身看看。
HashSet提供了如下几个构造函数：

HashSet<T>(); // 这是默认构造函数，没什么好期待的
HashSet<T>(IEnumerable<T>); // 这是把其他的容器转成HashSet的，也不是我们想要的
HashSet<T>(Int32); // 这个参数是为了定容的，pass
HashSet<T>(SerializationInfo, StreamingContext); // 我们并不拿他来序列化，这个也不用
HashSet<T>(IEqualityComparer<T>); //……咦？？

一支量身打造的骑士圣剑：IEqualityComparer

Equality……相等性……看来没错了，就是这个东西在直接控制HashSet的相等性判断了。
IEqualityComparer是System.Collections.Generic命名空间提供的一个接口……

居然和HashSet的出处都是一样的！！看来找对了。IEqualityComparer是用于相等判断的比较器。提供了两个方法：Equals和GetHashCode。

可是，圣剑似乎尚未开锋……

IEqualityComparer是一个接口，用于容器内元素的相等性判定，但是接口并不能被实例化，而对于构造函数的参数而言必须提供一个能够使用的实例，因为不管怎么说，我们也不能

var comparer = new IEqualityComparer<Student>(); //错误，IEqualityComparer<Student>是接口。

没事，只需稍加淬火打磨……

尽管不能实例化接口，我们可以实现这个接口，而且，因为接口只是提供方法约定而不提供，实现接口的类和接口之间也存在类似父子类之间的多态关系。

class StudentComparer : IEqualityComparer<Student>
{
    public bool Equals([AllowNull] Student x, [AllowNull] Student y)
    {
        return x.id == y.id && x.name == y.name;
    }

    public int GetHashCode([DisallowNull] Student obj)
    {
        return obj.id.GetHashCode();
    }
}

当然，这个StudentComparer也可以被多态性视为一个IEqualityComparer<T>，因此我们的构造函数中就可以写：

HashSet<Student> students = new HashSet<Student>(new StudentComparer());

这样的HashSet<Student>采取了StudentComparer作为相等比较器，如果满足这一比较器的相等条件，那就会被认为是一致的元素而被加进来，也就是说问题的关键并不是对等号算符的重载，而是选择适合于HashSet容器的比较装置。

终于骑士可以携圣剑踏向讨伐恶魔的征途

我们找到了一个可行的解决方案，于是我们再次尝试一下：

public static void Main(string[] args)
{
    HashSet<Student> students = new HashSet<Student>(new StudentComparer()); // 空的HashSet
    Student s1 = new Student(1,"Tom");
    Student s2 = s1;
    Student s3 = new Student(1,"Tom");
    students.Add(s1); // students现在包含了s1
    students.Add(s2); // 没有变化，s1已存在
    students.Add(s3); // 没有变化，s3和s1相等
    
    Console.WriteLine($"There's {students.Count} student(s).")
    // 迭代输出看结果
    foreach(var s in students)
    {
        Console.WriteLine($"{s.id}.{s.name}");
    }
}

输出结果：

There's 1 student(s).
1.Tom

故事之后的尾声

这次探索得到的结论就是……

我曾经对C#的泛型容器的了解……不，对整个数据容器体系的了解还是NAIVE as we are！

C#的泛型容器中其实提供了比想象中更多的东西，尤其是System.Collections.Generic提供了一些很重要的接口，如列举器和比较器等等，甚至还有.NET为泛型容器提供了强大的CRUD工具——LINQ表达式和Lambda表达式等等。

此外，当尝试外力去解决问题无果时，不妨将视野跳回起点，可能会有不一样的收获。

C#中HashSet的重复性与判等运算重载