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


Answers

正如古德里奇和塔馬西亞指出的那樣,如果你接收超過50,000個英文單詞(形成為Unix變體中提供的單詞列表的聯合),使用常量31,33,37,39和41將產生少於7次的衝突在每種情況下。 知道這一點,許多Java實現選擇這些常量中的一個應該不足為奇。

巧合的是,當我看到這個問題時,我正在閱讀“多項式哈希碼”部分。

編輯:這裡是鏈接到~10mb PDF書我指的是上面。 請參見Java中數據結構和算法的 10.2哈希表(第397頁)

Question

在Java中, String對象的哈希碼計算為

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

使用int算術,其中s[i]是字符串的 i 字符, n是字符串的長度, ^表示取冪。

為什麼31被用作乘數?

我知道乘數應該是一個相對較大的素數。 那麼為什麼不是29,或37,甚至97?




http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622 ,Joshua Bloch描述了為什麼選擇該特定(新) String.hashCode()實現的原因

下表總結了上述各種散列函數的性能,對於三個數據集:

1)所有帶有Merriam-Webster第二國際未刪節詞典中的詞條(311,141個字符串,平均長度為10個字符)。

2)/ bin / ,/ usr / bin / ,/ usr / lib / ,/ usr / ucb /和/ usr / openwin / bin / *中的所有字符串(66,304個字符串,平均長度為21個字符)。

3)一個網絡爬蟲收集的URL列表,昨天晚上運行了幾個小時(28372個字符串,平均長度為49個字符)。

表中顯示的性能指標是散列表中所有元素的“平均鏈大小”(即,查找元素的鍵的數量的期望值)。

                          Webster's   Code Strings    URLs
                          ---------   ------------    ----
Current Java Fn.          1.2509      1.2738          13.2560
P(37)    [Java]           1.2508      1.2481          1.2454
P(65599) [Aho et al]      1.2490      1.2510          1.2450
P(31)    [K+R]            1.2500      1.2488          1.2425
P(33)    [Torek]          1.2500      1.2500          1.2453
Vo's Fn                   1.2487      1.2471          1.2462
WAIS Fn                   1.2497      1.2519          1.2452
Weinberger's Fn(MatPak)   6.5169      7.2142          30.6864
Weinberger's Fn(24)       1.3222      1.2791          1.9732
Weinberger's Fn(28)       1.2530      1.2506          1.2439

從這張表中可以明顯看出,除了當前的Java函數和Weinberger函數的兩個破解版本之外,所有函數都提供了極好的幾乎無法區分的性能。 我強烈猜測,這種表現本質上是“理論上的理想”,如果你使用真正的隨機數發生器代替散列函數,你會得到什麼。

我會排除WAIS函數,因為它的規範包含了隨機數字的頁面,並且它的性能沒有任何更簡單的函數更好。 其餘六項功能中的任何一項看起來都是很好的選擇,但我們必須選擇一項。 我想我會排除Vo的變體和Weinberger的功能,因為它們增加了複雜性,儘管很小。 在其餘四個中,我可能會選擇P(31),因為它是在RISC機器上計算最便宜的(因為31是兩個冪的差)。 P(33)計算起來同樣便宜,但它的表現稍微差一些,33是複合的,這讓我有些緊張。

玩笑




通過乘,位向左移動。 這使用了更多的散列碼可用空間,減少了衝突。

通過不使用2的冪,低位,最右邊的位也被填充,以與下一個進入散列的數據混合。

表達式n * 31相當於(n << 5) - n




其實,37會工作得很好! z:= 37 * x可以計算為y := x + 8 * x; z := x + 4 * y y := x + 8 * x; z := x + 4 * y 。 兩個步驟都對應一個LEA x86指令,所以這個速度非常快。

事實上,通過設置y := x + 8 * x; z := x + 8 * y可以以相同的速度完成乘以更大的素數73 y := x + 8 * x; z := x + 8 * y y := x + 8 * x; z := x + 8 * y

使用73或37(而不是31)可能會更好,因為它會導致代碼更密集 :兩條LEA指令只需要6個字節,而7個字節用於移動+移位+減法乘以31.一個可能的警告是在英特爾的Sandy bridge體系結構中,此處使用的3參數LEA指令變慢,延遲時間增加了3個週期。

此外, 73是謝爾登庫珀最喜歡的數字。




我不確定,但我猜測他們測試了一些素數的樣本,發現31個樣本在可能的字符串樣本中得到了最好的分佈。




Related