Panduan GetHashCode di C #

Saya membaca di buku Essential C # 3.0 dan .NET 3.5 bahwa:

Pengembalian GetHashCode () selama masa pakai objek tertentu harus konstan (nilai yang sama), bahkan jika data objek berubah. Dalam banyak kasus, Anda harus meng-cache metode pengembalian untuk memberlakukan ini.

Apakah ini pedoman yang valid?

Saya telah mencoba beberapa tipe bawaan di .NET dan mereka tidak berperilaku seperti ini.

Jawabannya sebagian besar, ini adalah pedoman yang valid, tetapi mungkin bukan aturan yang valid. Itu juga tidak menceritakan keseluruhan cerita.

Intinya adalah bahwa untuk tipe yang bisa berubah, Anda tidak dapat mendasarkan kode hash pada data yang bisa berubah karena dua objek yang sama harus mengembalikan kode hash yang sama dan kode hash harus valid selama masa pakai objek. Jika kode hash berubah, Anda akan berakhir dengan objek yang hilang dalam kumpulan hash karena tidak lagi berada di hash bin yang benar.

Misalnya, objek A mengembalikan hash 1. Jadi, ia masuk ke bin 1 dari tabel hash. Kemudian Anda mengubah objek A sehingga mengembalikan hash 2. Ketika tabel hash mencarinya, ia mencari di bin 2 dan tidak dapat menemukannya - objek tersebut menjadi yatim piatu di bin 1. Inilah sebabnya mengapa kode hash harus tidak berubah selama masa pakai objek , dan hanya satu alasan mengapa menulis implementasi GetHashCode sangat merepotkan.

Perbarui
Eric Lippert telah memposting blog yang memberikan informasi yang sangat baik tentang GetHashCode.

Pembaruan Tambahan
Saya telah membuat beberapa perubahan di atas:

1. Saya membuat perbedaan antara pedoman dan aturan.
2. Saya menerobos "seumur hidup objek".

Pedoman hanyalah pedoman, bukan aturan. Pada kenyataannya, GetHashCodehanya harus mengikuti pedoman ini jika ada sesuatu yang mengharapkan objek mengikuti pedoman, seperti saat disimpan dalam tabel hash. Jika Anda tidak pernah bermaksud untuk menggunakan objek Anda dalam tabel hash (atau apa pun yang bergantung pada aturan GetHashCode), implementasi Anda tidak perlu mengikuti pedoman.

Ketika Anda melihat "seumur hidup objek", Anda harus membaca "untuk waktu yang dibutuhkan objek untuk bekerja sama dengan tabel hash" atau serupa. Seperti kebanyakan hal, GetHashCodeadalah tentang mengetahui kapan harus melanggar aturan.

Sudah lama sekali, namun menurut saya masih perlu memberikan jawaban yang benar atas pertanyaan ini, termasuk penjelasan tentang kenapa dan bagaimana. Jawaban terbaik sejauh ini adalah yang mengutip MSDN secara lengkap - jangan mencoba membuat aturan Anda sendiri, orang-orang MS tahu apa yang mereka lakukan.

Tetapi hal pertama yang pertama: Pedoman seperti yang dikutip dalam pertanyaan itu salah.

Sekarang mengapa - ada dua di antaranya

Pertama mengapa : Jika hashcode dihitung dengan cara, itu tidak berubah selama masa pakai objek, bahkan jika objek itu sendiri berubah, daripada itu akan melanggar kontrak yang sama.

Ingat: "Jika dua objek dibandingkan sama, metode GetHashCode untuk setiap objek harus mengembalikan nilai yang sama. Namun, jika dua objek tidak dibandingkan sebagai sama, metode GetHashCode untuk dua objek tidak harus mengembalikan nilai yang berbeda."

Kalimat kedua sering disalahartikan sebagai "Satu-satunya aturan adalah, pada saat pembuatan objek, kode hash dari objek yang sama harus sama". Tidak benar-benar tahu mengapa, tapi itulah inti dari sebagian besar jawaban di sini.

Pikirkan dua objek yang berisi nama, di mana nama tersebut digunakan dalam metode sama dengan: Nama yang sama -> hal yang sama. Buat Instance A: Name = Joe Buat Instance B: Name = Peter

Hashcode A dan Hashcode B kemungkinan besar tidak akan sama. Apa yang sekarang akan terjadi, ketika Nama instance B diubah menjadi Joe?

Menurut pedoman dari pertanyaan, kode hash B tidak akan berubah. Hasilnya akan menjadi: A.Equals (B) ==> true Tetapi pada saat yang sama: A.GetHashCode () == B.GetHashCode () ==> false.

Tapi sebenarnya perilaku ini dilarang secara eksplisit oleh sama & hashcode-contract.

Kedua mengapa : Meskipun - tentu saja - benar, bahwa perubahan dalam kode hash dapat merusak daftar hash dan objek lain yang menggunakan kode hash, kebalikannya juga benar. Tidak mengubah kode hash, dalam kasus terburuk, akan mendapatkan daftar hash, di mana semua banyak objek yang berbeda akan memiliki kode hash yang sama dan karenanya berada dalam bin hash yang sama - terjadi ketika objek diinisialisasi dengan nilai standar, misalnya.

Sekarang datang ke bagaimana Nah, pada pandangan pertama, tampaknya ada kontradiksi - bagaimanapun, kode akan rusak. Tetapi tidak ada masalah yang berasal dari kode hash yang diubah atau tidak berubah.

Sumber masalah dijelaskan dengan baik di MSDN:

Dari entri hashtable MSDN:

Objek kunci harus tidak dapat diubah selama digunakan sebagai kunci di Hashtable.

Artinya:

Objek apa pun yang membuat nilai hash harus mengubah nilai hash, saat objek berubah, tetapi tidak boleh - mutlak tidak boleh - mengizinkan perubahan apa pun pada dirinya sendiri, saat digunakan di dalam Hashtable (atau objek lain yang menggunakan Hash, tentu saja) .

Pertama, cara termudah tentu saja untuk mendesain objek yang tidak dapat diubah hanya untuk digunakan dalam hashtable, yang akan dibuat sebagai salinan dari objek normal yang bisa berubah saat diperlukan. Di dalam objek yang tidak dapat diubah, tidak apa-apa untuk menyimpan kode hash, karena itu tidak dapat diubah.

Kedua bagaimana Atau berikan objek "Anda sedang di-hash sekarang" -bendera, pastikan semua data objek bersifat pribadi, centang bendera di semua fungsi yang dapat mengubah data objek dan melempar data pengecualian jika perubahan tidak diizinkan (yaitu, bendera disetel ). Sekarang, saat Anda meletakkan objek di sembarang area yang di-hash, pastikan untuk menyetel benderanya, dan - juga - hapus setel benderanya, jika sudah tidak diperlukan lagi. Untuk kemudahan penggunaan, saya menyarankan untuk menyetel flag secara otomatis di dalam metode "GetHashCode" - cara ini tidak dapat dilupakan. Dan panggilan eksplisit dari metode "ResetHashFlag" akan memastikan, bahwa programmer harus berpikir, apakah diperbolehkan atau tidak untuk mengubah data objek sekarang.

Ok, apa yang harus dikatakan juga: Ada kasus, di mana dimungkinkan untuk memiliki objek dengan data yang bisa berubah, di mana kode hash tetap tidak berubah, ketika data objek diubah, tanpa melanggar sama & kontrak-kode hash.

Namun ini membutuhkan, bahwa metode yang sama tidak didasarkan pada data yang bisa berubah juga. Jadi, jika saya menulis objek, dan membuat metode GetHashCode yang menghitung nilai hanya sekali dan menyimpannya di dalam objek untuk mengembalikannya pada panggilan berikutnya, maka saya harus, sekali lagi: mutlak harus, membuat metode Equals, yang akan digunakan nilai yang disimpan untuk perbandingan, sehingga A.Equals (B) tidak akan pernah berubah dari salah menjadi benar juga. Jika tidak, kontrak akan diputus. Hasil dari ini biasanya adalah bahwa metode Sama dengan tidak masuk akal - ini bukan referensi asli yang sama, tetapi juga tidak ada nilai yang sama. Kadang-kadang, ini mungkin merupakan perilaku yang disengaja (misalnya catatan pelanggan), tetapi biasanya tidak.

Jadi, cukup buat perubahan hasil GetHashCode, ketika data objek berubah, dan jika penggunaan objek di dalam hash yang menggunakan daftar atau objek dimaksudkan (atau hanya mungkin) maka buat objek tersebut tidak dapat diubah atau buat bendera hanya-baca untuk digunakan untuk seumur hidup daftar hash yang berisi objek.

(Ngomong-ngomong: Semua ini bukan C # oder .NET spesifik - ini adalah sifat dari semua implementasi hashtable, atau lebih umum dari daftar yang diindeks, bahwa mengidentifikasi data objek tidak boleh berubah, sementara objek ada dalam daftar . Perilaku tak terduga dan tak terduga akan terjadi, jika aturan ini dilanggar. Di suatu tempat, mungkin ada implementasi daftar, yang memantau semua elemen di dalam daftar dan melakukan pengindeksan ulang daftar secara otomatis - tetapi kinerjanya pasti paling mengerikan.)

Dari MSDN

Jika dua objek dibandingkan sebagai sama, metode GetHashCode untuk setiap objek harus mengembalikan nilai yang sama. Namun, jika dua objek tidak dibandingkan sebagai sama, metode GetHashCode untuk dua objek tidak harus mengembalikan nilai yang berbeda.

Metode GetHashCode untuk sebuah objek harus secara konsisten mengembalikan kode hash yang sama selama tidak ada modifikasi pada status objek yang menentukan nilai kembalian dari metode Equals objek. Perhatikan bahwa ini benar hanya untuk eksekusi aplikasi saat ini, dan kode hash yang berbeda dapat ditampilkan jika aplikasi dijalankan lagi.

Untuk performa terbaik, fungsi hash harus menghasilkan distribusi acak untuk semua input.

Ini berarti bahwa jika nilai dari objek berubah, kode hash harus berubah. Misalnya, kelas "Orang" dengan properti "Nama" yang disetel ke "Tom" harus memiliki satu kode hash, dan kode yang berbeda jika Anda mengubah nama menjadi "Jerry". Kalau tidak, Tom == Jerry, yang mungkin bukan yang Anda inginkan.

Edit :

Juga dari MSDN:

Kelas turunan yang menimpa GetHashCode juga harus menimpa Sama dengan untuk menjamin bahwa dua objek yang dianggap sama memiliki kode hash yang sama; jika tidak, jenis Hashtable mungkin tidak berfungsi dengan benar.

Dari entri hashtable MSDN :

Objek kunci harus tidak dapat diubah selama digunakan sebagai kunci di Hashtable.

Cara saya membaca ini adalah bahwa objek yang bisa berubah harus mengembalikan kode hash yang berbeda saat nilainya berubah, kecuali jika dirancang untuk digunakan dalam hashtable.

Dalam contoh System.Drawing.Point, objek bisa berubah, dan tidak kembali kode hash yang berbeda ketika X atau Y nilai perubahan. Ini akan membuatnya menjadi kandidat yang buruk untuk digunakan apa adanya dalam hashtable.

Saya pikir dokumentasi tentang GetHashcode agak membingungkan.

Di satu sisi, MSDN menyatakan bahwa kode hash suatu objek tidak boleh berubah, dan konstan Di sisi lain, MSDN juga menyatakan bahwa nilai yang dikembalikan dari GetHashcode harus sama untuk 2 objek, jika 2 objek tersebut dianggap sama.

MSDN:

Fungsi hash harus memiliki properti berikut:

• Jika dua objek dibandingkan sebagai sama, metode GetHashCode untuk setiap objek harus mengembalikan nilai yang sama. Namun, jika dua objek tidak dibandingkan sebagai sama, metode GetHashCode untuk dua objek tidak harus mengembalikan nilai yang berbeda.
• Metode GetHashCode untuk sebuah objek harus secara konsisten mengembalikan kode hash yang sama selama tidak ada modifikasi pada status objek yang menentukan nilai kembalian dari metode Equals objek. Perhatikan bahwa ini benar hanya untuk eksekusi aplikasi saat ini, dan kode hash yang berbeda dapat dikembalikan jika aplikasi dijalankan lagi.
• Untuk performa terbaik, fungsi hash harus menghasilkan distribusi acak untuk semua input.

Kemudian, ini berarti bahwa semua objek Anda harus tidak dapat diubah, atau metode GetHashcode harus didasarkan pada properti objek Anda yang tidak dapat diubah. Misalkan Anda memiliki kelas ini (implementasi naif):

public class SomeThing
{
      public string Name {get; set;}

      public override GetHashCode()
      {
          return Name.GetHashcode();
      }

      public override Equals(object other)
      {
           SomeThing = other as Something;
           if( other == null ) return false;
           return this.Name == other.Name;
      }
}

Implementasi ini telah melanggar aturan yang dapat ditemukan di MSDN. Misalkan Anda memiliki 2 instance dari kelas ini; properti Nama instance1 disetel ke 'Pol', dan properti Nama instance2 disetel ke 'Piet'. Kedua contoh mengembalikan kode hash yang berbeda, dan keduanya juga tidak sama. Sekarang, misalkan saya mengubah Nama instance2 menjadi 'Pol', lalu, menurut metode Equals saya, kedua instance harus sama, dan menurut salah satu aturan MSDN, mereka harus mengembalikan kode hash yang sama.
Namun, ini tidak dapat dilakukan, karena kode hash dari instance2 akan berubah, dan MSDN menyatakan bahwa ini tidak diperbolehkan.

Kemudian, jika Anda memiliki entitas, Anda mungkin dapat mengimplementasikan kode hash sehingga menggunakan 'pengidentifikasi utama' dari entitas tersebut, yang mungkin idealnya adalah kunci pengganti, atau properti yang tidak dapat diubah. Jika Anda memiliki objek nilai, Anda dapat mengimplementasikan kode hash sehingga ia menggunakan 'properti' dari objek nilai tersebut. Properti tersebut membentuk 'definisi' dari objek nilai. Ini tentu saja merupakan sifat dari objek nilai; Anda tidak tertarik pada identitasnya, melainkan pada nilainya.
Dan, oleh karena itu, objek nilai harus tidak dapat diubah. (Sama seperti mereka dalam kerangka .NET, string, Tanggal, dll ... semuanya adalah objek yang tidak dapat diubah).

Hal lain yang muncul dalam pikiran:
Selama 'sesi' (saya tidak benar-benar tahu bagaimana saya harus memanggil ini) harus 'GetHashCode' mengembalikan nilai konstan. Misalkan Anda membuka aplikasi Anda, memuat instance objek keluar dari DB (entitas), dan mendapatkan kode hashnya. Ini akan mengembalikan angka tertentu. Tutup aplikasi, dan muat entitas yang sama. Apakah kali ini kode hash harus memiliki nilai yang sama seperti saat Anda memuat entitas pertama kali? IMHO, tidak.

Ini adalah nasihat yang bagus. Inilah yang dikatakan Brian Pepin tentang masalah ini:

Ini telah membuat saya tersandung lebih dari sekali: Pastikan GetHashCode selalu mengembalikan nilai yang sama selama masa pakai sebuah instance. Ingatlah bahwa kode hash digunakan untuk mengidentifikasi "keranjang" di sebagian besar penerapan hashtable. Jika "keranjang" objek berubah, hashtable mungkin tidak dapat menemukan objek Anda. Ini bisa menjadi bug yang sangat sulit ditemukan, jadi lakukan dengan benar pada kali pertama.

Tidak langsung menjawab pertanyaan Anda, tetapi - jika Anda menggunakan Resharper, jangan lupa resharper memiliki fitur yang menghasilkan implementasi GetHashCode yang wajar (serta metode Equals) untuk Anda. Anda tentu saja dapat menentukan anggota kelas mana yang akan diperhitungkan saat menghitung kode hash.

Lihat posting blog ini dari Marc Brooks:

VTO, RTO, dan GetHashCode () - oh, astaga!

Dan kemudian periksa posting tindak lanjut (tidak dapat menautkan karena saya baru, tetapi ada tautan di artikel initlal) yang membahas lebih lanjut dan mencakup beberapa kelemahan kecil dalam implementasi awal.

Ini adalah semua yang perlu saya ketahui tentang membuat implementasi GetHashCode (), dia bahkan menyediakan download metodenya bersama dengan beberapa utilitas lain, singkatnya emas.

Kode hash tidak pernah berubah, tetapi penting juga untuk memahami dari mana kode Hash tersebut berasal.

Jika objek Anda menggunakan semantik nilai, yaitu identitas objek ditentukan oleh nilainya (seperti String, Warna, semua struct). Jika identitas objek Anda tidak bergantung pada semua nilainya, maka Kode Hash diidentifikasi oleh sebagian nilainya. Misalnya, entri StackOverflow Anda disimpan dalam database di suatu tempat. Jika Anda mengubah nama atau email, entri pelanggan Anda tetap sama, meskipun beberapa nilai telah berubah (pada akhirnya Anda biasanya diidentifikasi oleh beberapa id pelanggan yang panjang #).

Singkatnya:

Semantik tipe nilai - Kode has ditentukan oleh nilai Semantik tipe referensi - Kode has ditentukan oleh beberapa id

Saya sarankan Anda membaca Desain Didorong Domain oleh Eric Evans, di mana dia membahas entitas vs tipe nilai (yang kurang lebih seperti yang saya coba lakukan di atas) jika ini masih tidak masuk akal.

Lihat Panduan dan aturan untuk GetHashCode oleh Eric Lippert