Apa peran GetHashCode dalam IEqualityComparer <T> di .NET?

Saya mencoba memahami peran metode GetHashCode dari antarmuka IEqualityComparer.

Contoh berikut diambil dari MSDN:

using System;
using System.Collections.Generic;
class Example {
    static void Main() {
        try {

            BoxEqualityComparer boxEqC = new BoxEqualityComparer();

            Dictionary<Box, String> boxes = new Dictionary<Box,
                                                string>(boxEqC);

            Box redBox = new Box(4, 3, 4);
            Box blueBox = new Box(4, 3, 4);

            boxes.Add(redBox, "red");
            boxes.Add(blueBox, "blue");

            Console.WriteLine(redBox.GetHashCode());
            Console.WriteLine(blueBox.GetHashCode());
        }
        catch (ArgumentException argEx) {

            Console.WriteLine(argEx.Message);
        }
    }
}

public class Box {
    public Box(int h, int l, int w) {
        this.Height = h;
        this.Length = l;
        this.Width = w;
    }
    public int Height { get; set; }
    public int Length { get; set; }
    public int Width { get; set; }
}

class BoxEqualityComparer : IEqualityComparer<Box> {

    public bool Equals(Box b1, Box b2) {
        if (b1.Height == b2.Height & b1.Length == b2.Length
                            & b1.Width == b2.Width) {
            return true;
        }
        else {
            return false;
        }
    }

    public int GetHashCode(Box bx) {
        int hCode = bx.Height ^ bx.Length ^ bx.Width;
        return hCode.GetHashCode();
    }
}

Bukankah implementasi metode Equals cukup untuk membandingkan dua objek Box? Di situlah kita memberi tahu kerangka kerja aturan yang digunakan untuk membandingkan objek. Mengapa GetHashCode diperlukan?

Terima kasih.

Lucian

Sedikit latar belakang pertama ...

Setiap objek di .NET memiliki metode Equals dan metode GetHashCode.

Metode Persamaan digunakan untuk membandingkan satu objek dengan objek lain - untuk melihat apakah kedua objek tersebut setara.

Metode GetHashCode menghasilkan representasi integer 32-bit dari objek. Karena tidak ada batasan berapa banyak informasi yang dapat dikandung oleh suatu objek, kode hash tertentu digunakan bersama oleh banyak objek - sehingga kode hash belum tentu unik.

Kamus adalah struktur data yang sangat keren yang memperdagangkan jejak memori yang lebih tinggi dengan imbalan (lebih atau kurang) biaya konstan untuk operasi Tambah / Hapus / Dapatkan. Ini adalah pilihan yang buruk untuk iterasi. Secara internal, kamus berisi array ember, tempat nilai dapat disimpan. Saat Anda menambahkan Kunci dan Nilai ke kamus, metode GetHashCode dipanggil pada Kunci. Kode hash yang dikembalikan digunakan untuk menentukan indeks ember tempat pasangan Kunci / Nilai harus disimpan.

Saat Anda ingin mengakses Nilai, Anda memasukkan Kunci lagi. Metode GetHashCode dipanggil pada Kunci, dan ember berisi Nilai terletak.

Ketika IEqualityComparer dilewatkan ke konstruktor kamus, IEqualityComparer.Equals dan IEqualityComparer.GetHashCode metode digunakan sebagai pengganti metode pada objek kunci.

Sekarang untuk menjelaskan mengapa kedua metode ini diperlukan, pertimbangkan contoh ini:

BoxEqualityComparer boxEqC = new BoxEqualityComparer(); 

Dictionary<Box, String> boxes = new Dictionary<Box, string>(boxEqC); 

Box redBox = new Box(100, 100, 25);
Box blueBox = new Box(1000, 1000, 25);

boxes.Add(redBox, "red"); 
boxes.Add(blueBox, "blue"); 

Menggunakan metode BoxEqualityComparer.GetHashCode dalam contoh Anda, kedua kotak ini memiliki kode hash yang sama - 100 ^ 100 ^ 25 = 1000 ^ 1000 ^ 1000 ^ 25 = 25 - meskipun mereka jelas bukan objek yang sama. Alasan bahwa mereka memiliki kode hash yang sama dalam hal ini adalah karena Anda menggunakan operator ^ (bitwise eksklusif-OR) sehingga 100 ^ 100 batal keluar dengan meninggalkan nol, seperti halnya 1000 ^ 1000. Ketika dua objek berbeda memiliki kunci yang sama, kami menyebutnya tabrakan.

Saat kami menambahkan dua pasangan Kunci / Nilai dengan kode hash yang sama ke kamus, keduanya disimpan dalam keranjang yang sama. Jadi ketika kita ingin mengambil Nilai, metode GetHashCode dipanggil pada Kunci kita untuk menemukan ember. Karena ada lebih dari satu nilai di dalam ember, kamus akan mengulangi semua pasangan Kunci / Nilai di dalam ember yang memanggil metode Persamaan pada Tombol untuk menemukan yang benar.

Dalam contoh yang Anda poskan, kedua kotak itu sama, sehingga metode Persamaan mengembalikan nilai true. Dalam hal ini kamus memiliki dua Tombol identik, sehingga mengeluarkan pengecualian.

TLDR

Jadi secara ringkas, metode GetHashCode digunakan untuk menghasilkan alamat tempat objek disimpan. Jadi kamus tidak perlu mencarinya. Itu hanya menghitung kode hash dan melompat ke lokasi itu. Metode Persamaan adalah tes kesetaraan yang lebih baik, tetapi tidak dapat digunakan untuk memetakan objek ke ruang alamat.

GetHashCode digunakan dalam koleksi Kamus dan itu menciptakan hash untuk menyimpan objek di dalamnya. Berikut ini adalah artikel bagus mengapa dan bagaimana cara menggunakan IEqualtyComparer dan GetHashCode http://dotnetperls.com/iequalitycomparer

Meskipun mungkin untuk Dictionary<TKey,TValue>memiliki GetValuedan metode yang serupa memanggil Equalssetiap kunci yang disimpan untuk melihat apakah itu cocok dengan yang dicari, itu akan sangat lambat. Sebaliknya, seperti banyak koleksi berbasis hash, ia mengandalkan GetHashCodeuntuk dengan cepat mengecualikan sebagian besar nilai yang tidak cocok dari pertimbangan. Jika memanggil GetHashCodeitem yang dicari menghasilkan 42, dan koleksi memiliki 53.917 item, tetapi memanggil GetHashCode53.914 item menghasilkan nilai selain 42, maka hanya 3 item yang harus dibandingkan dengan yang dicari. 53.914 lainnya dapat diabaikan dengan aman.

Alasan a GetHashCodetermasuk dalam IEqualityComparer<T>adalah untuk memungkinkan kemungkinan bahwa konsumen kamus mungkin ingin menganggap sebagai objek yang sama yang biasanya tidak menganggap satu sama lain sebagai sama. Contoh paling umum adalah penelepon yang ingin menggunakan string sebagai kunci tetapi menggunakan perbandingan case-insensitive. Untuk membuatnya bekerja secara efisien, kamus harus memiliki beberapa bentuk fungsi hash yang akan menghasilkan nilai yang sama untuk "Fox" dan "FOX", tetapi mudah-mudahan menghasilkan sesuatu yang lain untuk "box" atau "zebra". Karena GetHashCodemetode yang dibangun Stringtidak berfungsi seperti itu, kamus harus mendapatkan metode seperti itu dari tempat lain,IEqualityComparer<T>Equals metode yang menganggap "Fox" dan "FOX" identik satu sama lain, tetapi tidak untuk "kotak" atau "zebra".