Kedua bilangan ini merupakan bilangan prima yang cukup besar. Silakan baca artikel di Tabel Hash di Wikipedia untuk info lebih lanjut.
Boris Pavlović
Jawaban:
140
1231 dan 1237 hanyalah dua bilangan prima sembarang (cukup besar) . Dua bilangan prima besar lainnya bisa digunakan.
Mengapa bilangan prima?
Misalkan sejenak kita memilih bilangan komposit (bukan bilangan prima), katakanlah 1000 dan 2000. Saat memasukkan boolean ke dalam tabel hash, true dan false akan masuk ke bucket 1000 % Nresp 2000 % N(di mana Njumlah bucket).
Sekarang perhatikan itu
1000 % 8 ember yang sama seperti 2000 % 8
1000 % 10 ember yang sama seperti 2000 % 10
1000 % 20 ember yang sama seperti 2000 % 20
....
dengan kata lain, akan menyebabkan banyak tabrakan .
Hal ini karena faktorisasi 1000 (2 3 , 5 3 ) dan faktorisasi 2000 (2 4 , 5 3 ) memiliki banyak faktor yang sama. Jadi bilangan prima dipilih, karena tidak mungkin memiliki faktor yang sama dengan ukuran keranjang.
Mengapa bilangan prima besar . Bukankah 2 dan 3 bisa?
Saat menghitung kode hash untuk objek komposit, biasanya kode hash ditambahkan untuk komponen tersebut. Jika nilai yang terlalu kecil digunakan dalam kumpulan hash dengan jumlah bucket yang besar, ada risiko berakhir dengan distribusi objek yang tidak merata.
Apakah tabrakan penting? Boolean hanya memiliki dua nilai yang berbeda?
Peta dapat berisi boolean bersama dengan objek lain. Selain itu, seperti yang ditunjukkan oleh Drunix, cara umum untuk membuat fungsi hash dari objek komposit adalah dengan menggunakan kembali implementasi kode hash subkomponen dalam hal ini adalah baik untuk mengembalikan bilangan prima besar.
Saya kira ini cukup besar. Untuk mendapatkan gcd yang lebih besar dari 1, Anda membutuhkan setidaknya beberapa 2*1231 = 2462ember. Apakah tabrakan menjadi masalah dalam situasi seperti itu?
aioobe
2
Menarik meskipun mereka tidak benar-benar "cukup besar" mengingat apa yang bisa masuk ke dalam int. Saya kira mereka cukup besar untuk bekerja dengan baik dengan JDK Hashtable, tetapi masih cukup kecil untuk meminimalkan biaya kalkulasi.
Thilo
2
Ya, aku tersadar juga bahwa mereka tidak yang besar. Tapi apakah Anda yakin ada biaya yang lebih tinggi dengan bilangan prima yang lebih besar?
aioobe
3
@Thilo Anda memerlukan kelipatan 1231 * 1237 = 1.522.747 ember sebelum bertabrakan, itu cukup besar
ratchet freak
2
Saya akan mengatakan bahwa menyebabkan tabrakan dengan jumlah ember sebenarnya bukan masalah dengan boolean, tetapi lebih merupakan konstruksi umum tentang bagaimana kita mendapatkan kode hash dari objek komposit, yaitu dengan mengalikan kode hash komponen dengan beberapa konstanta dan menambahkannya.
Drunix
2
Selain semua yang disebutkan di atas, ini juga bisa menjadi telur paskah kecil dari pengembang:
true: 1231 => 1 + 2 + 3 + 1 = 7
7 - adalah angka keberuntungan dalam tradisi Eropa;
Jawaban:
1231 dan 1237 hanyalah dua bilangan prima sembarang (cukup besar) . Dua bilangan prima besar lainnya bisa digunakan.
Mengapa bilangan prima?
Misalkan sejenak kita memilih bilangan komposit (bukan bilangan prima), katakanlah 1000 dan 2000. Saat memasukkan boolean ke dalam tabel hash, true dan false akan masuk ke bucket
1000 % Nresp2000 % N(di manaNjumlah bucket).Sekarang perhatikan itu
1000 % 8ember yang sama seperti2000 % 81000 % 10ember yang sama seperti2000 % 101000 % 20ember yang sama seperti2000 % 20dengan kata lain, akan menyebabkan banyak tabrakan .
Hal ini karena faktorisasi 1000 (2 3 , 5 3 ) dan faktorisasi 2000 (2 4 , 5 3 ) memiliki banyak faktor yang sama. Jadi bilangan prima dipilih, karena tidak mungkin memiliki faktor yang sama dengan ukuran keranjang.
Mengapa bilangan prima besar . Bukankah 2 dan 3 bisa?
Saat menghitung kode hash untuk objek komposit, biasanya kode hash ditambahkan untuk komponen tersebut. Jika nilai yang terlalu kecil digunakan dalam kumpulan hash dengan jumlah bucket yang besar, ada risiko berakhir dengan distribusi objek yang tidak merata.
Apakah tabrakan penting? Boolean hanya memiliki dua nilai yang berbeda?
Peta dapat berisi boolean bersama dengan objek lain. Selain itu, seperti yang ditunjukkan oleh Drunix, cara umum untuk membuat fungsi hash dari objek komposit adalah dengan menggunakan kembali implementasi kode hash subkomponen dalam hal ini adalah baik untuk mengembalikan bilangan prima besar.
Pertanyaan-pertanyaan Terkait:
sumber
2*1231 = 2462ember. Apakah tabrakan menjadi masalah dalam situasi seperti itu?Selain semua yang disebutkan di atas, ini juga bisa menjadi telur paskah kecil dari pengembang:
7 - adalah angka keberuntungan dalam tradisi Eropa;
13 (alias selusin Iblis) - angka sial.
sumber