Mengapa ember hashtable mengambil bilangan prima?
Memiliki fungsi hash
H (c) = c % n;
Ketika n mengambil bilangan gabungan, contoh paling sederhana adalah mengambil 2^n, misalnya, ambil 2^3 = 8, saat ini
H (11100 (biner)) = h (28) = 4
H (10100 (biner)) = h (20) = 4
Pada saat ini, bit biner ke -4 (dari kanan ke kiri) dari C akan "gagal", yang berarti apa pun nilai yang diambil dalam bit ke -4 C, itu akan mengarah pada nilai h (C) yang sama. Pada saat ini, bit keempat C tidak berpartisipasi dalam pengoperasian H (C) sama sekali, sehingga H (c) tidak dapat sepenuhnya mencerminkan karakteristik C, meningkatkan kemungkinan konflik.
Saat mengambil angka komposit lainnya, beberapa bit C akan "gagal" pada berbagai tingkat, yang mengakibatkan konflik dalam beberapa aplikasi umum.
Namun, mengambil bilangan prima pada dasarnya dapat memastikan bahwa setiap bit C berpartisipasi dalam pengoperasian H (C), sehingga mengurangi kemungkinan konflik dalam aplikasi umum. ．
(Opini Pribadi: Terkadang efisiensi tidak mengambil bilangan prima tidak terlalu buruk ... tetapi tidak diragukan lagi lebih aman untuk mengambil bilangan prima ...)
Di atas adalah pemahaman saya
Untuk menambah ini, ini berarti bahwa dalam aplikasi umum, beberapa data seringkali serupa. Lebih baik menggunakan bilangan prima saat ini. Misalnya, data yang akan disimpan dalam keadaan terkompresi, seperti menyimpan tabel yang menggambarkan keadaan pencarian saat ini. Pada saat ini, probabilitas hashing tanpa bilangan prima relatif tinggi.
Jika itu adalah integer yang didistribusikan secara acak, maka modulus hash akan sama selama itu diambil cukup besar, tetapi ini jelas keluar dari aplikasi praktis.
Apa yang Anda katakan adalah situasi khusus, karena ketika bilangan prima yang relatif kecil dipilih, ketika bilangan prima yang besar dipilih, ia hanya dapat gagal dalam bit tertentu dari sistem N-digit. Dikombinasikan dengan karakteristik sistem komputer, representasi N digit seringkali tidak kritis, sedangkan sistem 2^n-digit yang umum digunakan lebih kritis, sehingga konflik dapat dihindari.
Bahkan, saya telah menggunakan beberapa angka besar untuk mengujinya untuk menyimpan matriks adjacency yang dikompres menjadi biner. Ketika modulus cukup besar, bahkan bilangan komposit dapat memiliki efek yang sangat dekat dengan bilangan prima, tetapi dalam beberapa (beberapa lusin) angka gabungan, efisiensinya akan sangat berkurang, sehingga bilangan prima relatif aman.
Anda mungkin melakukan eksperimen Anda sendiri, tidak memilih bilangan bulat acak, tetapi pertimbangkan beberapa aplikasi umum, gunakan bilangan prima dan bilangan komposit untuk diuji, terutama memeriksa faktor pemuatan rata -rata, dan kesimpulan yang Anda dapatkan mungkin sama dengan tambang: angka gabungan juga bagus di sebagian besar waktu, tetapi efeknya secara mengejutkan buruk dalam beberapa angka komposit, dan hampir semua angka utama memiliki hasil yang baik.
Saya pribadi berpikir bahwa dalam arti yang lebih umum, jika Anda tidak mengambil bilangan prima, akan ada beberapa bahaya. Bahaya terjadi ketika angka non-prime m = x*y diasumsikan dipilih, dan jika kunci hash terkait dengan pembagi ini, itu akan menyedihkan. Dalam kasus terburuk, semua menganggap bahwa itu adalah kelipatan x, maka Anda dapat membayangkan bahwa hasil hash adalah: 1 ~ y, bukan 1 ~ m. Namun, jika ukuran ember dipilih sebagai bilangan prima, tidak akan ada masalah.
Terima kasih telah membaca, saya harap ini dapat membantu Anda. Terima kasih atas dukungan Anda untuk situs ini!