為什麼Java的String hashCode()要使用31作為乘數？

為什麼Java 中String 的hashCode() 使用31 作為乘數

在Java 中，String 物件的雜湊碼是使用公式：

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

其中s[i] 是字串的第i 個字符， n是字串的長度，^ 表示求冪。

素數乘數的重要性

此公式的一個關鍵方面是素數乘數的使用，在本例中為 31。使用質數的優點是減少哈希衝突的可能性。如果使用非素數乘數，兩個具有相同哈希值的字串可以共享一個公因子，從而更容易發生哈希衝突。

為什麼不用另一個質數？

雖然 31 是奇質數，但也可以選擇其他質數，例如 29、37 或 97。 31 基於多種因素的組合：

• 避免溢位： 31 是一個相對較小的質數，這降低了乘法過程中整數溢位的風險。如果使用偶素數，乘以 2 時可能會發生溢出，可能會遺失資訊。
• 效能最佳化： 如同Joshua Bloch 在《Effective Java》中所指出的，乘以31 可以被更有效的移位和減法運算取代：31 * i == (i
• 傳統：對雜湊函數使用質數乘數是一種長期的做法，31 是特別受歡迎的選擇。雖然沒有明確選擇 31 的原因，但它已成為許多程式語言和應用程式的標準選擇。

以上是為什麼Java的String hashCode()要使用31作為乘數？的詳細內容。更多資訊請關注PHP中文網其他相關文章！