Bagaimana HashSet membandingkan elemen untuk kesetaraan?

127

Saya memiliki kelas yaitu IComparable:

public class a : IComparable
{
    public int Id { get; set; }
    public string Name { get; set; }

    public a(int id)
    {
        this.Id = id;
    }

    public int CompareTo(object obj)
    {
        return this.Id.CompareTo(((a)obj).Id);
    }
}

Ketika saya menambahkan daftar objek dari kelas ini ke kumpulan hash:

a a1 = new a(1);
a a2 = new a(2);
HashSet<a> ha = new HashSet<a>();
ha.add(a1);
ha.add(a2);
ha.add(a1);

Semuanya baik-baik saja dan ha.countini 2, tapi:

a a1 = new a(1);
a a2 = new a(2);
HashSet<a> ha = new HashSet<a>();
ha.add(a1);
ha.add(a2);
ha.add(new a(1));

Sekarang ha.countadalah 3.

  1. Mengapa tidak HashSetmenghormati a's CompareTometode.
  2. Apakah HashSetcara terbaik untuk memiliki daftar benda unik?
nima
sumber
Tambahkan implementasi IEqualityComparer<T>dalam konstruktor atau implementasikan di kelas a. msdn.microsoft.com/en-us/library/bb301504(v=vs.110).aspx
Jaider

Jawaban:

137

Menggunakan IEqualityComparer<T>( EqualityComparer<T>.Defaultkecuali Anda menentukan yang berbeda pada konstruksi).

Ketika Anda menambahkan elemen ke set, itu akan menemukan kode hash menggunakan IEqualityComparer<T>.GetHashCode, dan menyimpan kode hash dan elemen (setelah memeriksa apakah elemen sudah di set, tentu saja).

Untuk mencari elemen, pertama-tama akan menggunakan IEqualityComparer<T>.GetHashCodeuntuk menemukan kode hash, kemudian untuk semua elemen dengan kode hash yang sama, itu akan digunakan IEqualityComparer<T>.Equalsuntuk membandingkan kesetaraan yang sebenarnya.

Itu berarti Anda memiliki dua opsi:

  • Lewati kebiasaan IEqualityComparer<T>ke konstruktor. Ini adalah opsi terbaik jika Anda tidak dapat memodifikasi Tsendiri, atau jika Anda ingin hubungan kesetaraan non-standar (misalnya "semua pengguna dengan ID pengguna negatif dianggap sama"). Ini hampir tidak pernah diimplementasikan pada tipe itu sendiri (yaitu Footidak mengimplementasikan IEqualityComparer<Foo>) tetapi dalam tipe terpisah yang hanya digunakan untuk perbandingan.
  • Menerapkan kesetaraan dalam tipe itu sendiri, dengan mengesampingkan GetHashCodedan Equals(object). Idealnya, implementasikan IEquatable<T>dalam tipe juga, terutama jika itu tipe nilai. Metode-metode ini akan dipanggil oleh pembanding kesetaraan default.

Perhatikan bagaimana tidak satu pun dari ini dalam hal perbandingan yang dipesan - yang masuk akal, karena pasti ada situasi di mana Anda dapat dengan mudah menentukan kesetaraan tetapi bukan total pemesanan. Ini semua sama dengan Dictionary<TKey, TValue>, pada dasarnya.

Jika Anda menginginkan set yang menggunakan pemesanan alih-alih hanya perbandingan kesetaraan, Anda harus menggunakan SortedSet<T>dari .NET 4 - yang memungkinkan Anda untuk menentukan IComparer<T>bukan IEqualityComparer<T>. Ini akan menggunakan IComparer<T>.Compare- yang akan didelegasikan ke IComparable<T>.CompareToatau IComparable.CompareTojika Anda menggunakan Comparer<T>.Default.

Jon Skeet
sumber
7
+1 Perhatikan juga jawaban tyriker (bahwa IMO harus menjadi komentar di sini) yang menunjukkan bahwa cara paling sederhana untuk meningkatkan kata IEqualityComparer<T>.GetHashCode/Equals()adalah dengan menerapkan Equalsdan GetHashCodepada Tdirinya sendiri (dan saat Anda melakukan itu, Anda juga akan menerapkan mitra yang sangat diketikkan : - bool IEquatable<T>.Equals(T other))
Ruben Bartelink
5
Walaupun sangat akurat jawaban ini mungkin agak membingungkan, terutama untuk pengguna baru karena tidak secara jelas menyatakan bahwa untuk kasus paling sederhana Equalsdan GetHashCodecukup - seperti yang disebutkan dalam jawaban @ tyriker.
BartoszKP
Imo begitu Anda menerapkan IComparable(atau IComparerdalam hal ini) Anda tidak boleh diminta untuk menerapkan kesetaraan secara terpisah (tapi adil GetHashCode). Dalam arti antarmuka komparabilitas harus mewarisi dari antarmuka kesetaraan. Saya mengerti manfaat kinerja dalam memiliki dua fungsi yang terpisah (di mana Anda dapat mengoptimalkan kesetaraan secara terpisah hanya dengan mengatakan jika ada sesuatu yang sama atau tidak) tapi masih .. Sangat membingungkan jika ketika Anda telah ditentukan ketika kasus yang sama dalam CompareTofungsi dan kerangka wont mempertimbangkan bahwa.
nawfal
@nawfal tidak semuanya memiliki urutan logis. jika Anda membandingkan dua hal yang berisi properti bool itu sekadar mengerikan harus menulis sesuatu seperti a.boolProp == b.boolProp ? 1 : 0atau harus itu a.boolProp == b.boolProp ? 0 : -1atau a.boolProp == b.boolProp ? 1 : -1. Yuk!
Simon_Weaver
1
@Simon_Weaver itu. Saya ingin menghindarinya dalam fitur hipotetis yang saya usulkan.
nawfal
77

Berikut ini klarifikasi pada bagian dari jawaban yang tidak diucapkan: Jenis objek Anda HashSet<T>tidak harus diimplementasikan IEqualityComparer<T>tetapi alih-alih hanya perlu mengganti Object.GetHashCode()dan Object.Equals(Object obj).

Alih-alih ini:

public class a : IEqualityComparer<a>
{
  public int GetHashCode(a obj) { /* Implementation */ }
  public bool Equals(a obj1, a obj2) { /* Implementation */ }
}

Anda melakukan ini:

public class a
{
  public override int GetHashCode() { /* Implementation */ }
  public override bool Equals(object obj) { /* Implementation */ }
}

Ini halus, tetapi ini membuat saya tersandung untuk bagian yang lebih baik dari hari mencoba untuk membuat HashSet berfungsi seperti yang dimaksudkan. Dan seperti orang lain katakan, HashSet<a>akan berakhir menelepon a.GetHashCode()dan a.Equals(obj)seperlunya ketika bekerja dengan set.

tyriker
sumber
2
Poin yang bagus. BTW seperti yang disebutkan pada komentar saya pada jawaban @ JonSkeet, Anda juga harus menerapkan bool IEquatable<T>.Equals(T other)untuk mendapatkan efisiensi sedikit tetapi yang lebih penting manfaat kejelasan. Untuk alasan obv, di samping kebutuhan untuk mengimplementasikan GetHashCodebersama IEquatable<T>, dokumen untuk IEquatable <T> menyebutkan bahwa untuk tujuan konsistensi Anda juga harus mengganti object.Equalskonsistensi
Ruben Bartelink
Saya mencoba menerapkan ini. The ovveride getHashcodebekerja, tapi override bool equalsmendapat kesalahan: tidak ada metode ditemukan override. ada ide?
Stefanvds
Akhirnya info yang saya cari. Terima kasih.
Mauro Sampietro
Dari komentar saya pada jawaban di atas - Dalam kasus "Alih-alih", Anda dapat melakukannya public class a : IEqualityComparer<a> {, lalu new HashSet<a>(a).
HankCa
Tetapi lihat komentar Jon Skeets di atas.
HankCa
9

HashSetmenggunakan Equalsdan GetHashCode().

CompareTo untuk set yang dipesan.

Jika Anda menginginkan objek unik, tetapi Anda tidak peduli dengan urutan iterasi mereka, HashSet<T>biasanya merupakan pilihan terbaik.

CodesInChaos
sumber
5

constructor HashSet menerima objek apa yang mengimplementasikan IEqualityComparer untuk menambahkan objek baru. jika Anda ingin menggunakan metode di HashSet Anda tidak akan mengesampingkan Equals, GetHashCode

namespace HashSet
{
    public class Employe
    {
        public Employe() {
        }

        public string Name { get; set; }

        public override string ToString()  {
            return Name;
        }

        public override bool Equals(object obj) {
            return this.Name.Equals(((Employe)obj).Name);
        }

        public override int GetHashCode() {
            return this.Name.GetHashCode();
        }
    }

    class EmployeComparer : IEqualityComparer<Employe>
    {
        public bool Equals(Employe x, Employe y)
        {
            return x.Name.Trim().ToLower().Equals(y.Name.Trim().ToLower());
        }

        public int GetHashCode(Employe obj)
        {
            return obj.Name.GetHashCode();
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            HashSet<Employe> hashSet = new HashSet<Employe>(new EmployeComparer());
            hashSet.Add(new Employe() { Name = "Nik" });
            hashSet.Add(new Employe() { Name = "Rob" });
            hashSet.Add(new Employe() { Name = "Joe" });
            Display(hashSet);
            hashSet.Add(new Employe() { Name = "Rob" });
            Display(hashSet);

            HashSet<Employe> hashSetB = new HashSet<Employe>(new EmployeComparer());
            hashSetB.Add(new Employe() { Name = "Max" });
            hashSetB.Add(new Employe() { Name = "Solomon" });
            hashSetB.Add(new Employe() { Name = "Werter" });
            hashSetB.Add(new Employe() { Name = "Rob" });
            Display(hashSetB);

            var union = hashSet.Union<Employe>(hashSetB).ToList();
            Display(union);
            var inter = hashSet.Intersect<Employe>(hashSetB).ToList();
            Display(inter);
            var except = hashSet.Except<Employe>(hashSetB).ToList();
            Display(except);

            Console.ReadKey();
        }

        static void Display(HashSet<Employe> hashSet)
        {
            if (hashSet.Count == 0)
            {
                Console.Write("Collection is Empty");
                return;
            }
            foreach (var item in hashSet)
            {
                Console.Write("{0}, ", item);
            }
            Console.Write("\n");
        }

        static void Display(List<Employe> list)
        {
            if (list.Count == 0)
            {
                Console.WriteLine("Collection is Empty");
                return;
            }
            foreach (var item in list)
            {
                Console.Write("{0}, ", item);
            }
            Console.Write("\n");
        }
    }
}
Nikolai Nechai
sumber
Bagaimana jika Nama itu nol? apa nilai hash dari null?
joe