Mengapakah Java's String hashCode() Menggunakan 31 sebagai Pengganda?

Mengapa Java's hashCode() dalam String Menggunakan 31 sebagai Pengganda

Di Java, kod cincang untuk objek String dikira menggunakan formula:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

di mana s[i] ialah aksara ke-i rentetan, n ialah panjang rentetan, dan ^ menunjukkan eksponen.

Kepentingan Pengganda Perdana

Satu aspek utama formula ini ialah penggunaan pengganda perdana, dalam kes ini, 31. Menggunakan nombor perdana mempunyai kelebihan untuk mengurangkan kemungkinan perlanggaran cincang. Jika pengganda bukan perdana digunakan, dua rentetan dengan nilai cincang yang sama boleh berkongsi faktor yang sama, menjadikannya lebih mudah untuk perlanggaran cincang berlaku.

Mengapa Bukan Nombor Perdana Lain?

Walaupun 31 ialah perdana ganjil, terdapat nombor perdana lain yang boleh dipilih, seperti 29, 37, atau 97. Pilihan 31 adalah berdasarkan gabungan faktor:

• Mengelakkan Limpahan: 31 ialah bilangan perdana yang agak kecil, yang mengurangkan risiko limpahan integer semasa proses pendaraban. Jika perdana genap digunakan, limpahan boleh berlaku apabila mendarab dengan 2, yang berpotensi kehilangan maklumat.
• Pengoptimuman Prestasi: Seperti yang dinyatakan oleh Joshua Bloch dalam "Effective Java," darab dengan 31 boleh digantikan dengan operasi anjakan-dan-tolak yang lebih cekap: 31 * i == (i << 5) - i. Pengoptimuman ini biasanya dilakukan oleh mesin maya moden untuk tujuan prestasi.
• Tradisi: Menggunakan pengganda utama untuk fungsi cincang ialah amalan yang telah lama wujud dan 31 telah menjadi pilihan yang sangat popular. Walaupun tiada sebab pasti mengapa 31 dipilih secara khusus, ia telah menjadi pilihan standard dalam banyak bahasa pengaturcaraan dan aplikasi.

Atas ialah kandungan terperinci Mengapakah Java's String hashCode() Menggunakan 31 sebagai Pengganda?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!