Mengapa menggunakan nomor utama dalam kode hash?

Saya hanya bertanya-tanya mengapa bilangan prima digunakan dalam metode kelas hashCode()? Misalnya, ketika menggunakan Eclipse untuk menghasilkan hashCode()metode saya selalu ada bilangan prima yang 31digunakan:

public int hashCode() {
     final int prime = 31;
     //...
}

Referensi:

Berikut ini adalah primer yang bagus pada Hashcode dan artikel tentang bagaimana hashing bekerja yang saya temukan (C # tetapi konsepnya dapat ditransfer): Pedoman dan aturan Eric Lippert untuk GetHashCode ()

Karena Anda ingin jumlah yang Anda kalikan dengan dan jumlah ember yang Anda masukkan untuk memiliki faktorisasi prima ortogonal.

Misalkan ada 8 ember untuk dimasukkan. Jika nomor yang Anda gunakan untuk mengalikan dengan adalah kelipatan 8, maka ember yang dimasukkan hanya akan ditentukan oleh entri yang paling tidak signifikan (yang tidak dikalikan sama sekali). Entri yang serupa akan bertabrakan. Tidak bagus untuk fungsi hash.

31 adalah bilangan prima yang cukup besar sehingga jumlah ember tidak mungkin dapat dibagi olehnya (dan pada kenyataannya, implementasi HashMap java modern menjaga jumlah ember pada kekuatan 2).

Nomor prima dipilih untuk mendistribusikan data terbaik di antara ember hash. Jika distribusi input acak dan tersebar merata, maka pilihan kode hash / modulus tidak masalah. Itu hanya berdampak ketika ada pola tertentu pada input.

Ini sering terjadi ketika berhadapan dengan lokasi memori. Misalnya, semua bilangan bulat 32-bit disejajarkan dengan alamat yang dapat dibagi oleh 4. Periksa tabel di bawah ini untuk memvisualisasikan efek menggunakan modulus prime vs non-prime:

Input       Modulo 8    Modulo 7
0           0           0
4           4           4
8           0           1
12          4           5
16          0           2
20          4           6
24          0           3
28          4           0

Perhatikan distribusi yang hampir sempurna ketika menggunakan modulus prima vs modulus non-prima.

Namun, meskipun contoh di atas sebagian besar dibuat-buat, prinsip umumnya adalah bahwa ketika berhadapan dengan pola input , menggunakan modulus bilangan prima akan menghasilkan distribusi terbaik.

Untuk apa nilainya, Efektif Java 2nd Edition mengesampingkan masalah matematika dan hanya mengatakan bahwa alasan untuk memilih 31 adalah:

• Karena ini adalah prime yang aneh, dan "tradisional" menggunakan bilangan prima
• Ini juga satu kurang dari kekuatan dua, yang memungkinkan untuk optimasi bitwise

Ini kutipan lengkapnya, dari Butir 9: Selalu timpa hashCodeketika Anda menggantiequals :

Nilai 31 dipilih karena ini adalah prime yang aneh. Jika itu genap dan multiplikasi meluap, informasi akan hilang, karena penggandaan 2 sama dengan pergeseran. Keuntungan menggunakan prime kurang jelas, tetapi tradisional.

Properti 31 yang bagus adalah bahwa perkalian dapat diganti dengan shift ( §15.19 ) dan pengurangan untuk kinerja yang lebih baik:

 31 * i == (i << 5) - i

VM modern melakukan optimasi semacam ini secara otomatis.

---

Sementara resep dalam item ini menghasilkan fungsi hash yang cukup baik, itu tidak menghasilkan fungsi hash yang canggih, juga pustaka platform Java tidak menyediakan fungsi hash tersebut pada rilis 1.6. Menulis fungsi hash seperti itu adalah topik penelitian, sebaiknya diserahkan kepada ahli matematika dan ilmuwan komputer teoretis.

Mungkin rilis nanti dari platform akan menyediakan fungsi hash yang canggih untuk kelasnya dan metode utilitas untuk memungkinkan programmer rata-rata untuk membangun fungsi hash tersebut. Sementara itu, teknik yang dijelaskan dalam item ini harus memadai untuk sebagian besar aplikasi.

Agak disederhanakan, dapat dikatakan bahwa menggunakan pengganda dengan banyak pembagi akan menghasilkan lebih banyak tabrakan hash . Karena untuk hashing yang efektif kami ingin meminimalkan jumlah tabrakan, kami mencoba menggunakan pengganda yang memiliki lebih sedikit pembagi. Bilangan prima menurut definisi memiliki dua pembagi positif yang berbeda.

Pertanyaan-pertanyaan Terkait

• Kode hash Java dari satu bidang - resep, plus contoh menggunakan pembangun Apache Commons Lang
• apakah salah untuk mendefinisikan kode hash dari suatu objek sebagai jumlah, perkalian, apa pun, dari semua variabel kelas kode hash?
• Panduan Pemula Mutlak untuk Menggeser Bit?

Saya mendengar bahwa 31 dipilih sehingga kompiler dapat mengoptimalkan penggandaan ke shift 5 bit kemudian kurangi nilainya.

Berikut ini kutipan yang sedikit lebih dekat dengan sumbernya.

Intinya adalah:

• 31 adalah prima, yang mengurangi tabrakan
• 31 menghasilkan distribusi yang baik, dengan
• tradeoff yang wajar dalam kecepatan

Pertama Anda menghitung nilai hash modulo 2 ^ 32 (ukuran an int), jadi Anda menginginkan sesuatu yang relatif prima ke 2 ^ 32 (relatif prima berarti tidak ada pembagi umum). Angka ganjil akan melakukan untuk itu.

Kemudian untuk tabel hash yang diberikan indeks biasanya dihitung dari nilai hash modulo ukuran tabel hash, jadi Anda menginginkan sesuatu yang relatif prima dengan ukuran tabel hash. Seringkali ukuran tabel hash dipilih sebagai bilangan prima karena alasan itu. Dalam kasus Java, implementasi Sun memastikan bahwa ukuran selalu merupakan kekuatan dua, sehingga angka ganjil juga cukup di sini. Ada juga beberapa pemijatan tambahan dari kunci hash untuk membatasi tabrakan lebih lanjut.

Efek buruk jika tabel hash dan pengali memiliki faktor yang sama nadalah bahwa dalam keadaan tertentu hanya 1 / n entri dalam tabel hash yang akan digunakan.

Alasan mengapa bilangan prima digunakan adalah untuk meminimalkan tabrakan ketika data menunjukkan beberapa pola tertentu.

Hal pertama yang pertama: Jika data acak maka tidak perlu untuk bilangan prima, Anda dapat melakukan operasi mod terhadap nomor apa pun dan Anda akan memiliki jumlah tabrakan yang sama untuk setiap kemungkinan nilai modulus.

Tetapi ketika data tidak acak maka hal-hal aneh terjadi. Misalnya pertimbangkan data numerik yang selalu kelipatan 10.

Jika kami menggunakan mod 4, kami menemukan:

10 mod 4 = 2

20 mod 4 = 0

30 mod 4 = 2

40 mod 4 = 0

50 mod 4 = 2

Jadi dari 3 kemungkinan nilai modulus (0,1,2,3) hanya 0 dan 2 yang akan bertabrakan, itu buruk.

Jika kita menggunakan bilangan prima seperti 7:

10 mod 7 = 3

20 mod 7 = 6

30 mod 7 = 2

40 mod 7 = 4

50 mod 7 = 1

dll

Kami juga mencatat bahwa 5 bukan pilihan yang baik tetapi 5 adalah prima alasannya adalah bahwa semua kunci kami adalah kelipatan 5. Ini berarti kita harus memilih bilangan prima yang tidak membagi kunci kami, memilih bilangan prima besar adalah biasanya cukup.

Jadi keliru di sisi berulang-ulang alasan bilangan prima digunakan adalah untuk menetralisir efek pola dalam kunci dalam distribusi tabrakan fungsi hash.

31 juga khusus untuk Java HashMap yang menggunakan tipe data hash int. Dengan demikian kapasitas maks 2 ^ 32. Tidak ada gunanya menggunakan Fermat yang lebih besar atau bilangan prima Mersenne.

Ini biasanya membantu mencapai penyebaran data Anda yang lebih merata di antara hash bucket, terutama untuk kunci dengan entropi rendah.