Implementasi default untuk Object.GetHashCode ()

Bagaimana cara kerja implementasi default GetHashCode()? Dan apakah itu menangani struktur, kelas, array, dll secara efisien dan cukup baik?

Saya mencoba memutuskan dalam hal apa saya harus mengemas sendiri dan dalam kasus apa saya dapat dengan aman mengandalkan implementasi default untuk melakukannya dengan baik. Saya tidak ingin menemukan kembali roda, jika memungkinkan.

namespace System {
    public class Object {
        [MethodImpl(MethodImplOptions.InternalCall)]
        internal static extern int InternalGetHashCode(object obj);

        public virtual int GetHashCode() {
            return InternalGetHashCode(this);
        }
    }
}

InternalGetHashCode dipetakan ke fungsi ObjectNative :: GetHashCode di CLR, yang terlihat seperti ini:

FCIMPL1(INT32, ObjectNative::GetHashCode, Object* obj) {  
    CONTRACTL  
    {  
        THROWS;  
        DISABLED(GC_NOTRIGGER);  
        INJECT_FAULT(FCThrow(kOutOfMemoryException););  
        MODE_COOPERATIVE;  
        SO_TOLERANT;  
    }  
    CONTRACTL_END;  

    VALIDATEOBJECTREF(obj);  

    DWORD idx = 0;  

    if (obj == 0)  
        return 0;  

    OBJECTREF objRef(obj);  

    HELPER_METHOD_FRAME_BEGIN_RET_1(objRef);        // Set up a frame  

    idx = GetHashCodeEx(OBJECTREFToObject(objRef));  

    HELPER_METHOD_FRAME_END();  

    return idx;  
}  
FCIMPLEND

Implementasi penuh GetHashCodeEx cukup besar, jadi lebih mudah untuk hanya menautkan ke kode sumber C ++ .

Untuk sebuah kelas, default pada dasarnya adalah referensi kesetaraan, dan itu biasanya baik-baik saja. Jika menulis struct, lebih umum untuk mengesampingkan kesetaraan (paling tidak untuk menghindari tinju), tetapi sangat jarang Anda menulis struct juga!

Ketika mengesampingkan kesetaraan, Anda harus selalu memiliki kecocokan Equals()dan GetHashCode()(yaitu untuk dua nilai, jika Equals()mengembalikan true mereka harus mengembalikan kode hash yang sama, tetapi sebaliknya tidak diperlukan) - dan biasanya juga disediakan ==/ !=operator, dan sering kali untuk terapkan IEquatable<T>juga.

Untuk menghasilkan kode hash, adalah umum untuk menggunakan jumlah faktor, karena ini menghindari tabrakan pada nilai-nilai berpasangan - misalnya, untuk hash bidang 2 dasar:

unchecked // disable overflow, for the unlikely possibility that you
{         // are compiling with overflow-checking enabled
    int hash = 27;
    hash = (13 * hash) + field1.GetHashCode();
    hash = (13 * hash) + field2.GetHashCode();
    return hash;
}

Ini memiliki keuntungan bahwa:

• hash {1,2} tidak sama dengan hash {2,1}
• hash dari {1,1} tidak sama dengan hash dari {2,2}

dll - yang umum jika hanya menggunakan jumlah tidak tertimbang, atau xor ( ^), dll.

Dokumentasi untuk GetHashCodemetode untuk Objek mengatakan "implementasi default metode ini tidak boleh digunakan sebagai pengidentifikasi objek unik untuk tujuan hashing." dan yang untuk ValueType mengatakan "Jika Anda memanggil metode GetHashCode tipe turunan, nilai kembali kemungkinan tidak cocok untuk digunakan sebagai kunci dalam tabel hash." .

Tipe data dasar seperti byte, short, int, long, chardan stringmenerapkan metode yang baik GetHashCode. Beberapa kelas dan struktur lain, seperti Pointmisalnya, menerapkan GetHashCodemetode yang mungkin cocok atau tidak cocok untuk kebutuhan spesifik Anda. Anda hanya perlu mencobanya untuk melihat apakah itu cukup baik.

Dokumentasi untuk setiap kelas atau struktur dapat memberi tahu Anda apakah itu menimpa implementasi standar atau tidak. Jika tidak menimpanya, Anda harus menggunakan implementasi Anda sendiri. Untuk setiap kelas atau struct yang Anda buat sendiri di mana Anda perlu menggunakan GetHashCodemetode ini, Anda harus membuat implementasi Anda sendiri yang menggunakan anggota yang sesuai untuk menghitung kode hash.

Karena saya tidak dapat menemukan jawaban yang menjelaskan mengapa kita harus mengganti GetHashCodedan Equalsuntuk custom structs dan mengapa implementasi default "sepertinya tidak cocok untuk digunakan sebagai kunci dalam tabel hash", saya akan meninggalkan tautan ke blog ini posting , yang menjelaskan mengapa dengan contoh kasus nyata dari masalah yang terjadi.

Saya sarankan membaca seluruh posting, tetapi di sini adalah ringkasan (penekanan dan klarifikasi ditambahkan).

Alasan hash default untuk struct lambat dan tidak terlalu baik:

Cara CLR dirancang, setiap panggilan ke anggota yang ditentukan dalam System.ValueTypeatau System.Enummengetik [dapat] menyebabkan alokasi tinju [...]

Seorang pelaksana fungsi hash menghadapi dilema: membuat distribusi fungsi hash yang baik atau membuatnya cepat. Dalam beberapa kasus, mungkin untuk mencapai mereka berdua, tetapi sulit untuk melakukan hal ini umum di ValueType.GetHashCode.

Fungsi hash kanonik dari struct "menggabungkan" kode hash dari semua bidang. Tetapi satu-satunya cara untuk mendapatkan kode hash dari suatu bidang dalam ValueTypemetode adalah dengan menggunakan refleksi . Jadi, penulis CLR memutuskan untuk berdagang kecepatan atas distribusi dan GetHashCodeversi default hanya mengembalikan kode hash dari bidang non-nol pertama dan "munges" dengan tipe id [...] Ini adalah perilaku yang wajar kecuali jika tidak . Misalnya, jika Anda kurang beruntung dan bidang pertama struct Anda memiliki nilai yang sama untuk sebagian besar contoh, maka fungsi hash akan memberikan hasil yang sama sepanjang waktu. Dan, seperti yang Anda bayangkan, ini akan menyebabkan dampak kinerja yang drastis jika instance ini disimpan dalam hash set atau tabel hash.

[...] Implementasi berbasis refleksi lambat . Sangat lambat.

[...] Keduanya ValueType.Equalsdan ValueType.GetHashCodememiliki optimasi khusus. Jika suatu tipe tidak memiliki "pointer" dan dikemas dengan benar [...] maka versi yang lebih optimal digunakan: GetHashCodeiterates atas instance dan XOR blok 4 byte dan Equalsmetode membandingkan dua instance menggunakan memcmp. [...] Tetapi pengoptimalannya sangat rumit. Pertama, sulit untuk mengetahui kapan optimasi diaktifkan [...] Kedua, perbandingan memori tidak selalu memberi Anda hasil yang benar . Berikut adalah contoh sederhana: [...] -0.0dan +0.0sama tetapi memiliki representasi biner yang berbeda.

Masalah dunia nyata yang dijelaskan dalam pos:

private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount;
readonly struct ErrorLocation
{
    // Empty almost all the time
    public string OptionalDescription { get; }
    public string Path { get; }
    public int Position { get; }
}

Kami menggunakan tuple yang berisi struct kustom dengan implementasi kesetaraan default. Dan sayangnya, struct memiliki bidang pertama opsional yang hampir selalu sama dengan [string kosong] . Performanya OK sampai jumlah elemen dalam set meningkat secara signifikan menyebabkan masalah kinerja nyata, mengambil menit untuk menginisialisasi koleksi dengan puluhan ribu item.

Jadi, untuk menjawab pertanyaan "dalam kasus apa saya harus mengemas sendiri dan dalam kasus apa saya dapat dengan aman mengandalkan implementasi default", setidaknya dalam kasus struct , Anda harus mengganti Equalsdan GetHashCodekapan pun struct kustom Anda dapat digunakan sebagai kunci dalam tabel hash atau Dictionary.
Saya juga merekomendasikan menerapkan IEquatable<T>dalam hal ini, untuk menghindari tinju.

Seperti jawaban lain mengatakan, jika Anda menulis kelas , hash default menggunakan referensi kesetaraan biasanya baik-baik saja, jadi saya tidak akan repot dalam hal ini, kecuali jika Anda perlu menimpa Equals(maka Anda harus menimpa yang GetHashCodesesuai).

Secara umum, jika Anda mengganti Equals, Anda ingin mengganti GetHashCode. Alasan untuk ini adalah karena keduanya digunakan untuk membandingkan persamaan kelas / struct Anda.

Persamaan digunakan saat memeriksa Foo A, B;

jika (A == B)

Karena kita tahu bahwa pointer cenderung tidak cocok, kita dapat membandingkan anggota internal.

Equals(obj o)
{
    if (o == null) return false;
    MyType Foo = o as MyType;
    if (Foo == null) return false;
    if (Foo.Prop1 != this.Prop1) return false;

    return Foo.Prop2 == this.Prop2;
}

GetHashCode umumnya digunakan oleh tabel hash. Kode hash yang dihasilkan oleh kelas Anda harus selalu sama untuk status pemberian kelas.

Saya biasanya melakukannya,

GetHashCode()
{
    int HashCode = this.GetType().ToString().GetHashCode();
    HashCode ^= this.Prop1.GetHashCode();
    etc.

    return HashCode;
}

Beberapa orang akan mengatakan bahwa kode hash hanya boleh dihitung sekali per objek seumur hidup, tapi saya tidak setuju dengan itu (dan saya mungkin salah).

Menggunakan implementasi default yang disediakan oleh objek, kecuali jika Anda memiliki referensi yang sama ke salah satu kelas Anda, mereka tidak akan sama satu sama lain. Dengan mengganti Equals dan GetHashCode, Anda dapat melaporkan kesetaraan berdasarkan nilai internal daripada referensi objek.

Jika Anda hanya berurusan dengan POCO, Anda dapat menggunakan utilitas ini untuk menyederhanakan hidup Anda:

var hash = HashCodeUtil.GetHashCode(
           poco.Field1,
           poco.Field2,
           ...,
           poco.FieldN);

...

public static class HashCodeUtil
{
    public static int GetHashCode(params object[] objects)
    {
        int hash = 13;

        foreach (var obj in objects)
        {
            hash = (hash * 7) + (!ReferenceEquals(null, obj) ? obj.GetHashCode() : 0);
        }

        return hash;
    }
}