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

本文地址:http://www.nsxko.club/oberon-zjt0806/p/12355028.html
本文遵循CC BY-NC-SA 4.0协议,转载请注明出处

一个故事……

在C#中,HashSet是一种叫做哈希集泛型的数据容器(Generic Collection,巨硬的官方术语称Collection为集?#24076;?#20294;区别于Set的数学集合概念,?#39029;?#20043;为数据容器(简称容器),泛型数据容器一?#24405;?#31216;泛型容器)。
C#中泛型容器是通过系统标准库的命名空间System.Collections.Generic提供的,例如ArrayListDictionary……
HashSet是在.NET Framework 3.5引入的。

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

数据容器其实就是用于管理数据的数据结构(Data Structure,DS),用于存储一组数据,而泛型指的是这些容器是针?#36816;?#26377;的对象类型的泛型类,因而在使用时必须给出容器所容纳的数据类型,以List为例:

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

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

尽管不推荐非纯类型的数据容器的存在,泛型约束统一类型的好处在于方便编写通用方法进?#22411;?#19968;处理,但?#23548;是?#20917;是迫于客观条件这?#21482;?#21512;类型的容器是存在并且是大量存在的。
一般来说,我们允许存在共同?#22363;?#20851;系的类?#36828;?#24577;的形式存在于一个容器中:

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

但如果没有共同?#22363;?#20851;?#30340;兀浚?#27604;如同时存储整数和?#22336;?#20018;??

不管怎么说,C#里所有类?#23478;?#24615;?#22363;?code>System.Object即object,因此所有类都可以被装箱为object类型,那么这种情况下可以使用装箱的容器,也就是泛型提供为object的容器:

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

或者的话,既然类型约束是泛型模板造成的,那么你?#37096;?#20197;使用非泛型版本(位于System.Collections命名空间)。

ArrayList stuffs = new ArrayList(){1, "a", texts}; // ArrayList是List<T>的非泛型版本。

不过,值得注意的是,目前msdn并不倡用(Deprecated)非泛型容器,而提倡使用泛型容器,而且事实上混合类型的容器都使用了装箱处理,所?#36828;?#20803;素还原的时候还必须依照底层类型进行拆箱

当然,自.NET 4.0又出现了dynamic关键字,因此?#37096;?#20197;使用泛型为弱类型的容器(尽管dynamic关键字从一开始就不怎么被msdn提倡):

List<dynamic> stuffs = new List<dynamic>(){ 1, "a", texts }; // 泛型指定为弱类型

dynamic允许不做拆箱操作直接访问属性(当然前提是属性对于其底层类型确实存在),不过元素都被混成dynamic之后,每个元素还有什么属性简?#26412;?#36319;猜谜语一样,所以这个方法也不建议使用(如果情非得已那就无所谓了)。

而?#36965;?#21035;忘了,本文不打算具体讨论怎么让泛型容器成为大众情人,差点就跑题了……

一个英勇的皇家骑士:HashSet

当然了,HashSet也是一个泛型容器,也就是说在使用的时候也得是HashSet<T>?#21028;小?/p>

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

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

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

值类型的HashSet

HashSet<int> integers = new HashSet<int>(){ 1,2,3 }; // 一个整数集?#24076;?#21253;含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已存在
    }
}

可以看?#21073;?#30456;同的元素也并没有被加进去,但是,如果我改一下……

        //前面不写了,直?#26377;碝ain里的东西
        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拷?#38180;?code>s3,而是让两者为同一个东西,而后者的s3只是属性值和s1一致,但?#23548;?#19978;s3是新建出来的对象。

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

另外一个……故……事??(虚假传说)

虚假传说-序言

这并不是真正的故事,也就是说这个大标题下不是真正的解决方案(毕竟都说了嘛,虚假传说)。
尽管这里不是真正的解决方案,我们希望各位勇者也能够读?#37327;矗?#36825;一部?#22336;从?#20102;一种想当然的思维模式。
如果需要真正解决方案,请见下一个大标题:真实印记

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

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

我们当然会很容易的想?#21073;?/p>

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

巧合的是,任何一个(?#22363;?#33258;object的)类都提供了两个东西:Equals方法和==运算符。
而?#36965;?#25105;们了解,对于引用类型来说(string?#33618;?#25913;过除外,我个人理解是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确实有不同之处,主要是体现在值类型和装箱的情况下,但我们目前不打算考虑这个区别。

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

因此我们很容易的会考虑改写这两个函数中的?#25105;?#19968;个,?#21482;?#32773;两个一起做,类似于:

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));
    }
    public static bool operator!=(Student s1,Student s2)    //重载==必须同时重载!=
    {
        return ! s1==s2;
    }
}

当然这样做了一溜十三招之后,带回去重新?#38405;?#20250;发现:

毛用都没有!!!

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

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

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

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

重载ReferenceEquals……说的轻松,轻松得我们都迫不及待要做了,然后我?#19988;?#22806;的发现:

因为object.ReferenceEquals静态方法,所以子类无法改写……
又因为object.ReferenceEquals(object,object),两个参数都是object,所以无法重载成同样的两个其他类型参数的副本。

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

最后的故事(真实印记)

绕了这么一大圈,我们不妨回到HashSet自身?#32431;礎?br> HashSet提供了如?#24405;?#20010;构造函数:

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是一个接口,用于容器内元素的相等性判定,但是接口并不能?#30343;?#20363;化,而对于构造函数的参数而言必须提供一个能?#30343;?#29992;的实例,因为不管怎么说,我们也不能

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

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

尽管不能实例化接口,我们可以实?#32456;?#20010;接口,而?#36965;?#22240;为接口只是提供方法约定而不提供实现,实现接口的类和接口之间也存在类似父子类之间的多态关系。

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?#37096;?#20197;被多态性视为一个IEqualityComparer<T>,因此我们的构造函数中就可以写:

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

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

终于骑士可以携圣剑踏向?#22336;?#24694;魔的征途

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

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#的泛型容器的了解……不,对整个数据容器体系的了解?#25925;荖AIVE as we are!

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

此外,?#32972;?#35797;外力去解决问题无果时,不?#20004;?#35270;野跳回起点,可能会有不一样的收获。

附录 - 番外的故事

一把名声赫赫的“除魔”之杖(虚假传说番外):GetHashCode

?#34892;?a href="http://www.nsxko.club/coredx/">@coredx在评论中对我的提醒,这里?#36816;?#30340;这条评论作?#36816;?#26126;,评论内容如下:

#8楼 2020-02-24 19:15 coredx
还有,hash set ?#23548;?#19978;是先调用 gethashcode,如果相等就直接认为是同一个对象。否则再调用相等判断。所以微软在这两个函数没?#22411;?#26102;重写的时候会警告你要同时重写两个函数,避免逻辑错?#36965;?#21644; dictionary 一样。

这里面提到了object提供的另外一个函数:object.GetHashCode()。此函数用于获得当前实例的哈希值,也就是一个哈希函数,返回一个Int32类型的哈希码。

可能是因为HashSet这个名字的原因,想到这个函数是很正常的,毕竟那个东西叫做“哈希集?#20445;?#20250;不会可能用到这个哈希函数呢??

然而名声赫赫也不过是信口开河

我们修改了尝试修改一下这个函数:

class Student
{
    //...别的不写了
    public override int GetHashCode() => id;
}

然后再带回去尝试,我们会发现……

As FUTILE as it ever been.

原来此魔非彼魔

其实,就别说HashSet了,连object.Equals==都不用HashCode来判断是否相等,如果只重写GetHashCode的话,我们甚至会发现==Equals完全不受影响。

但是看这位朋友的语气并不像子虚乌有,于是我特地去msdn上又查阅了一下object.GetHashCode(),结果得到了一个有趣的说法:

重写 GetHashCode() 的派生类还必须重写 Equals(Object),以保证视为相等的两个对象具有相同的哈希代码;否则,Hashtable 类型可能无法正常工作。

看来这位朋友把HashSetHashtable弄混了。两者虽然?#21152;?#20010;Hash,但其实除了都位于System.Collections这一大的命名空间下之外,几乎一点关系都没有

HashSet<T>是位于System.Collections.Generic下的泛型容器,而Hashtable是位于System.Collections下的非泛型容器(Non-generic Collection)。而?#36965;?strong>前者也并非后者的泛型版本,事实?#24076;?code>Hashtable对应的泛型版本是Dictionary<TK,TV>

也就是说,Hashtable其实类似于Dictionary<object,object>(尽管?#23548;?#19978;不是),这也就意味着,Hashtable的元素也是KV对(Key-Value Pair,键值对)。

Hashtable既然类似于Dictionary,那么Hashtable也要保证一种唯一性——Key的唯一性,为了保证键值的唯一性,Hashtable使用GetHashCode函数的结果是否相等作为判断依据,当有特别的判等需求时,可改写GetHashCode做适配。

不过?#23548;?#19978;msdn还提到了GetHashCode的重载和Equals函数之间的关联规范。上面引用的部分也提到了,本文不对此做过多阐述。

圣剑背后的故事(真实印记番外)

其实,尽管Hashtable使用GetHashCode(),但泛型版本的Dictionary<TK,TV>却依?#30343;?#29992;IEqualityComparer<TK>进行TK类型的相等性判断。

为什么会这样??

其实,无论是HashSet<T>?#25925;?code>Dictionary<TK,TV>,这两个泛型容器?#23548;?#19978;?#21152;?#19968;个属性叫做Comparer,类型为IEqualityComparer<T>
不过,这并不是因为他们共同?#22363;?#20102;什么类,也不是因为他们共同实现了什么接口,这只是这两种容器相仿的唯一性所带来的一个巧合。
HashSet<T>希望其中的T类型元素具有唯一性,而Dictionary<TK,TV>则希望TK类型的键值具有唯一性,然后很巧合的都使用了泛型版本的相等比较器IEqualityComparer<T>(?#23548;?#19978;这个接口有个非泛型版本,但这里不做介绍)。

HashSet<T>的其中一个构造函数:

HashSet<T>(IEqualityComparer<T>);

这个函数的参数?#23548;?#19978;就是给了Comparer属性。

当然,您可能要问:

如果我使用了没有此类型参数版本的构造函数,那这个属性会是null么??

答案是否定的,?#23548;?#19978;用调试器观察会发现,?#31508;?#20040;也不给Comparer的时候,Comparer被描述为一个类型为System.Collections.Generic.ObjectEqualityComparer<T>的类型,但是很有趣的是,无论是在msdn上?#25925;?#22312;对象浏览器中,都?#20063;?#21040;名为ObjectEqualityComparer<T>的类型,虽然原因不明,但推测是被巨硬写成了private class

原来圣剑与生俱来

事实?#24076;?#20851;于这一点,msdn上也是有所提示的:

HashSet()

  • Initializes a new instance of the HashSet class that is empty and uses the default equality comparer for the set type.

就是说,即使用无参的构造函数,HashSet实例?#25925;?#20250;被分配一个默认的IEqualityComparer<T>,这也就得出了这样的结论:无论哪种情况下,object.GetHashCode()HashSet都是没有什么关系的。
而?#23548;噬希?code>IEqualityComparer<T>接口要求我们必须实现两个函数:EqualsGetHashCode,但这两个函数是IEqualityComparer<T>?#32422;?#30340;,和这个也不发生关系。

posted @ 2020-02-24 10:48  Oberon  阅读(...)  评论(...编辑  收藏
三剑客和女王APP
山东十一选五历史开 韩国棒球比分怎么看 贵州11选5 中国体育彩票比分竞猜 之书Oz 及时比分网500 广东南粤风彩36选7 浪潮软件股票 竞彩比分投注规则 22选5 雪缘圆即时赔率 贵州十一选五一一定 球探竞彩比分直播 排列3走势图 贵州茅台股票分析2019 安徽十一选五