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




5 Answers

根據Joshua Bloch的Effective Java (一本不能被推薦的書,以及我在堆棧溢出中不斷提及的感謝):

值31被選擇,因為它是一個奇數的素數。 如果它是偶數並且乘法溢出,則信息將丟失,因為乘以2相當於移位。 使用素數的優點不太清楚,但它是傳統的。 31的一個很好的特性是乘法可以被一個移位和一個減法取代以獲得更好的性能: 31 * i == (i << 5) - i 。 現代虛擬機會自動進行這種優化。

(來自第3章,第9項:覆蓋等於時總是覆蓋哈希碼,第48頁)

sha256 algorithm

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

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

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

為什麼31被用作乘數?

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




在(大部分)舊處理器上,乘以31可能相對便宜。 例如,在ARM上,它只是一條指令:

RSB       r1, r0, r0, ASL #5    ; r1 := - r0 + (r0<<5)

大多數其他處理器將需要單獨的移位和減法指令。 但是,如果你的乘數很慢,這仍然是一個勝利。 現代處理器往往具有快速乘法器,所以它沒有太大的區別,只要32是正確的一方。

這不是一個好的散列算法,但它比1.0代碼更好,更好(並且比1.0規範要好得多)。




您可以在http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622 “評論”下閱讀Bloch的原始推理。 他研究了散列表中關於“平均鏈大小”的不同散列函數的性能。 P(31)是他在K&R書中發現的那個時期的共同功能之一(但是即使Kernighan和Ritchie也記不起它來自哪裡)。 最後,他基本上不得不選擇一個,所以他拿下P(31)因為它表現的很好。 儘管P(33)並不是真的更糟糕,而33的乘法計算速度也是同樣快的(只是一個移位5和一個加法),但他選擇了31,因為33不是素數:

在其餘四個中,我可能會選擇P(31),因為它是在RISC機器上計算最便宜的(因為31是兩個冪的差)。 P(33)計算起來同樣便宜,但它的表現稍微差一些,33是複合的,這讓我有些緊張。

所以這個推理不像這裡的許多答案似乎暗示的那樣理性。 但是,在我們做出決定之後,我們都會很好地提出合理的理由(甚至布洛赫也可能會這樣做)。




Neil Coffey explains為什麼31在熨燙中使用偏差

基本上使用31可以為散列函數提供更均勻的設置位概率分佈。




布洛赫並沒有完全理解這一點,但我一直聽到/相信的基本原理是這是基本的代數。 哈希歸結為乘法和模數運算,這意味著如果您可以提供幫助,您就不會希望使用具有常見因素的數字。 換句話說,相對的素數提供了均勻分佈的答案。

使用散列組成的數字通常是:

  • 您輸入的數據類型的模數(2 ^ 32或2 ^ 64)
  • 哈希表中存儲桶計數的模數(可變,在java中是prime,現在是2 ^ n)
  • 在您的混音功能中乘以或移動幻數
  • 輸入值

你真的只能控制一些這些值,所以要多加小心。




Related