IT教程 ·

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

SpringCloud微服务:阿里开源组件Nacos,服务和配置管理

 

一个故事……

在C#中,HashSet是一种叫做哈希集泛型的数据容器(Generic Collection,巨硬的官方术语称Collection为鸠合,但区分于Set的数学鸠合观点,我称之为数据容器(简称容器),泛型数据容器一下简称泛型容器)。
C#中泛型容器是经由过程系统规范库的定名空间System.Collections.Generic供应的,比方ArrayListDictionary……
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.Objectobject,因而一切类都可以被装箱为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中

明显s1s3长得也一毛一样,为何此次加进去了呢??

固然,假如晓得什么是援用范例的朋侪一定看出了问题症结,前者的s1s3统一个援用,也就是统一个对象,由于Student s3 = s1;的时刻并不将s1拷贝给s3,而是让二者为统一个东西,而后者的s3只是属性值和s1一致,但实际上s3是新建出来的对象。

由此可以看出,HashSet关于援用范例的唯一性保证采用的是援用一致性推断,这也是我为何在前者中对students.Add(s3)操纵给的解释是// 没有变化,s1已存在而不是// 没有变化,s3已存在

别的一个……故……事??(子虚传说)

子虚传说-序文

这并不是真正的故事,也就是说这个大标题下不是真正的解决方案(毕竟都说了嘛,子虚传说)。
只管这里不是真正的解决方案,我们愿望列位勇者也可以读读看,这一部份反应了一种想固然的头脑形式。
假如须要真正解决方案,请见下一个大标题:。

固然,平常情况下我们以为只需idname相称的两个Student实在就是统一个人。纵然是s1s3都被定义为new Student(1,"Tom"),我们也不愿望会被反复增加进来。
我们相识了HashSet的唯一性,因而我们要千方百计让HashSet以为s1s3是雷同的。

一对众所周知的双刀:==和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静态要领,所以子类没法改写……
又由于object.ReferenceEquals(object,object),两个参数都是object,所以没法重载成一样的两个其他范例参数的副本。

没法改写的话就没有意义了,看来这个要领也行不通,是啊,反过来细致想一想的话,假如最底层的援用一致性推断被能被改写的话那才是真正的灾害,所以这玩意怎么大概随意让你乱改。

末了的故事(实在印记)

绕了这么一大圈,我们无妨回到HashSet本身看看。
HashSet供应了以下几个组织函数:

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

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

Equality……相称性……看来没错了,就是这个东西在直接掌握HashSet的相称性推断了。
IEqualityComparerSystem.Collections.Generic定名空间供应的一个接口……

竟然和HashSet的出处都是一样的!!看来找对了。IEqualityComparer是用于相称推断的比较器。供应了两个要领:EqualsGetHashCode

但是,圣剑好像还没有开锋……

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表达式等等。

别的,当尝试外力去解决问题无果时,无妨将视野跳回出发点,大概会有不一样的收成。

风物长宜放眼量,人间正道是沧桑 - 一位北美 IT 技术人破局

参与评论