Mengapa lebih baik menggunakan bilangan prima sebagai mod dalam fungsi hashing?

Jika saya memiliki daftar nilai kunci dari 1 hingga 100 dan saya ingin mengaturnya dalam array 11 ember, saya telah diajarkan untuk membentuk fungsi mod

Sekarang semua nilai akan ditempatkan satu demi satu dalam 9 baris. Misalnya, dalam ember pertama akan ada $0, 11, 22 \dots$ . Dalam yang kedua, akan ada $1, 12, 23 \dots$ dll.

Katakanlah saya memutuskan untuk menjadi anak nakal dan menggunakan non-prime sebagai fungsi hashing saya - ambil 12. Menggunakan fungsi Hashing

akan menghasilkan tabel hash dengan nilai $0, 12, 24 \dots$ dalam bucket pertama, $1, 13, 25 \dots$ dll di kedua dan seterusnya.

Pada dasarnya mereka adalah hal yang sama. Saya tidak mengurangi tabrakan dan saya tidak menyebar lebih baik dengan menggunakan kode hash bilangan prima dan saya tidak bisa melihat bagaimana itu selalu bermanfaat.

Pertimbangkan kumpulan kunci dan tabel hash di mana jumlah ember adalah . Karena adalah faktor , kunci yang merupakan kelipatan dari akan di-hash ke bucket yang merupakan kelipatan dari :$K=\{0,1,...,100\}$$m=12$$3$$12$$3$$3$

• Kunci akan di-hash ke bucket .$\{0,12,24,36,...\}$$0$
• Kunci akan di-hash ke bucket .$\{3,15,27,39,...\}$$3$
• Kunci akan di-hash ke bucket .$\{6,18,30,42,...\}$$6$
• Kunci akan di-hash ke bucket .$\{9,21,33,45,...\}$$9$

Jika terdistribusi secara merata (yaitu, setiap kunci dalam kemungkinan sama terjadi), maka pilihan tidak begitu kritis. Tetapi, apa yang terjadi jika tidak terdistribusi secara merata? Bayangkan bahwa kunci yang paling mungkin terjadi adalah kelipatan . Dalam hal ini, semua bucket yang bukan kelipatan akan kosong dengan probabilitas tinggi (yang benar-benar buruk dalam hal kinerja tabel hash).$K$$K$$m$$K$$3$$3$

Situasi ini lebih sering terlihat. Bayangkan, misalnya, bahwa Anda melacak objek berdasarkan tempat mereka disimpan dalam memori. Jika ukuran kata komputer Anda adalah empat byte, maka Anda akan hashing kunci yang merupakan kelipatan dari . Tidak perlu dikatakan bahwa memilih menjadi kelipatan akan menjadi pilihan yang mengerikan: Anda akan memiliki ember yang benar-benar kosong, dan semua kunci Anda bertabrakan dalam ember tersisa .$4$$m$$4$$3m/4$$m/4$

Secara umum:

Setiap kunci dalam yang berbagi faktor umum dengan jumlah ember akan di-hash ke sebuah ember yang merupakan kelipatan dari faktor ini.$K$$m$

Oleh karena itu, untuk meminimalkan tabrakan, penting untuk mengurangi jumlah faktor umum antara dan unsur . Bagaimana ini bisa dicapai? Dengan memilih menjadi bilangan yang memiliki beberapa faktor: bilangan prima .$m$$K$$m$

Apakah kemungkinan tabrakan menggunakan bilangan prima tergantung pada distribusi kunci Anda.

Jika banyak dari kunci Anda memiliki bentuk dan fungsi hash Anda adalah , maka tombol-tombol ini pergi ke subset kecil dari ember IFF membagi . Jadi, Anda harus meminimalkan jumlah seperti itu , yang dapat dicapai dengan memilih bilangan prima.$a+k\cdot b$$H(n)=n \bmod m$$b$$n$$b$

Jika di sisi lain Anda suka memiliki hingga ember dan Anda tahu bahwa perbedaan yang merupakan kelipatan dari lebih mungkin daripada perbedaan yang merupakan kelipatan dari dan , Anda dapat memilih untuk aplikasi yang sangat spesial.$11$$12$$11$$2$$3$$12$

Apakah ini berdampak (juga) tergantung pada bagaimana Anda memperlakukan tabrakan. Saat menggunakan beberapa varian hashing terbuka , menggunakan bilangan prima menjamin slot kosong ditemukan selama tabel cukup kosong.

Coba perlihatkan yang berikut ini, misalnya:

Asumsikan kita ingin memasukkan elemen yang hash ke alamat dan menyelesaikan collision dengan mencoba posisi selanjutnya untuk .a + i 2 i = 1 , 2 , $a$$a + i^2$$i=1,2,\dots$

Tunjukkan bahwa prosedur ini selalu menghasilkan posisi kosong jika tabel hash berukuran , a perdana lebih besar dari , dan setidaknya setengah dari semua posisi bebas.p $p$$p$$3$

Petunjuk: Gunakan fakta bahwa modulo cincin residu kelas adalah bidang jika adalah prima dan karena itu memiliki paling banyak solusi.p i 2 = c $p$$p$$i^2=c$$2$

Jika fungsi hash Anda dalam bentuk mana adalah prima dan dipilih secara acak, maka probabilitas bahwa 2 hash kunci yang berbeda untuk bucket yang sama adalah . Jadi untuk , yang sangat kecil.$h(k)=a\times k \mod m$$m$$a$$1\over m$$m=1009$$Pr\{h(x)=h(y), x\neq y\}=0.00099108027$

Skema ini dikenal sebagai: Universal Hashing.