哈希碼計算爲什麼要乘和忽略溢出位？

這個問題不是關於爲什麼一個乘法，這是相當明顯的 - 它的分佈。哈希碼計算爲什麼要乘和忽略溢出位？

而恰恰這是成爲更多的因素包括在散列碼計算公式更重要乘法更多關於一個性質。

一個簡單的計算顯然可能會溢出，但這並不重要。

a * 31 + b

真正的問題是當許多項目在公式中被證明。

((a * 31) + b) * 31 ... 6n.

一旦超過5或6項是包括作爲其位由哈希碼值是至多包括5+術語時有溢出的第一項的值被丟失。使用這個系統只有最後5個左右的術語纔是最終價值的重要貢獻者。

31^7 > Integer.MAX_VALUE

那麼，爲什麼大多數計算沒有回滾周圍的溢出位，並且xor w /結果的低位。我讚賞這需要一些小竅門，並且計算必須使用長整數（64位）來完成，所以前32位可以與整數結果進行XOR運算，但至少不會丟失任何位。

溢出被忽略的原因是什麼？如前所述，使用長時間並不昂貴。

EDIT

100000*31^7=   2751261411100000  0x9C641F717C560 
6553600000*31^7 180306667837849600000 0xC641F717C5600000

注意，後者的值比以前更大的準確65536倍這也意味着它的答案是16位大。請注意，整數值 0xC641F717C5600000是0xC5600000實際有效值從16位值丟失。

*SAMPLE A* 
65536*4096*27512614111 

=7385361114638319616 
=0x667E12CDF0000000 
    12345678 
=0xF0000000 

*SAMPLE B* 
9*65536*4096*27512614111 

=66468250031744876544 
=0x9A6EA93D70000000 
    12345678 
=0x70000000

注意樣品B的最頂部位這正是9X 樣品A使得在最後的32位的值幾乎絕對沒有差異 - 如果我改變9X到17倍，然後較低位將是相同。但是，如果由於溢出而導致最高位未被「丟失」並且低32位的xord值則會不同。

來源

2011-02-10 mP.

溢出被忽略了嗎？如前所述，使用長時間並不昂貴。

但是它幾乎沒有任何收益。這種方法通常會產生一個很好的價值分佈。

來源

2011-02-10 00:56:21 jason

不僅如此，而且很長一段時間會遇到同樣的問題，只會花費一點點時間。（對不起，這是一個糟糕的...） – corsiKa 2011-02-10 08:22:08

素數作爲乘數的全部原因是因爲可能性意味着數值向左移動，最終所有位都丟失。然而，素數仍然有相同的概率，他們會更好一點，需要更長的時間消失。 – 2011-02-11 12:03:06

這是乘以奇數的好處;早期的數字不會完全落在整數的末尾。對於丟失的元素，31^n將需要是2的冪，並且不會發生。例如，在你的情況下，用31^7，你得到一個32位數的0x67E12CDF;因此，儘管溢出，輸入元素乘以該值仍將對結果作出貢獻。

來源

2011-02-10 00:57:18

是的，但隨着時間的推移，只有非常低的位實際存在於散列碼中。 – 2011-02-10 02:46:26

我在示例中看不到這一點。對我而言，它們看起來與您計算哈希代碼的方式無關：a * 31 + b。

你也許可以找到一些a和b，這會給出相同的散列碼（但高位不同）。然後將高位反轉回散列碼是有意義的。

或者，((a * 31) + b)*31 + ... + z的另一個例子是。然後找到一些a,b，...，z，其中哈希碼不再依賴於a。所以a不會是一個重要的貢獻者。

當然，如果您將31更改爲65536，則很容易找到那些a，...，z。任何值都可以，a位全部都會掉線，a會被移到左邊並被切斷。但是，你可以這樣做爲31？或者類似的，你可以把高位反回來。但是，爲什麼？你能找到一個有用的案例嗎？

65536的問題是，在二進制中它看起來像這樣10000000000000000。所以，當你用它乘以一個數字時，二進制數就會有那16個零。對於31，二進制，這不會發生。

哦，我不是說那些例子不存在，因爲它們（它畢竟只是一個散列）。但是，你不會找到很多或類似的例子。

來源

2011-02-10 14:01:16 Ishtar

哈希碼計算爲什麼要乘和忽略溢出位？

回答

相關問題