我知道在xoring之前乘以大數應該有助於分佈不良的操作數,但爲什麼乘數應該是一個素數?爲什麼在許多GetHashCode實現中xoring之前乘以一個素數?
相關:
Why should hash functions use a prime number modulus?關閉,但並不完全是重複的:
Why does Java’s hashCode() in String use 31 as a multiplier?
我知道在xoring之前乘以大數應該有助於分佈不良的操作數,但爲什麼乘數應該是一個素數?爲什麼在許多GetHashCode實現中xoring之前乘以一個素數?
相關:
Why should hash functions use a prime number modulus?關閉,但並不完全是重複的:
Why does Java’s hashCode() in String use 31 as a multiplier?
有一個good article on the Computing Life blog,詳細討論這個話題。它最初是作爲對問題中鏈接到的Java hashCode()問題的迴應發佈的。根據文章:
素數是唯一的數字。它們的獨特之處在於,由於使用素數來構成素數,所以素數與其他數字的乘積具有獨特性的最佳機會(並不像素數本身那樣獨特)。該屬性用於散列函數。
給定一個字符串「Samuel」,您可以通過將每個組成數字或字母與素數相乘並將它們相加來生成獨特的哈希。這就是使用素數的原因。
然而使用素數是一種古老的技術。這裏需要了解的關鍵是,只要您可以生成足夠獨特的密鑰,您就可以轉移到其他散列技術。請點擊此處查看關於hashes without primes的更多信息。
是的,我明白。 – gkdm 2009-10-04 14:13:04
乘以一個非黃金具有循環重複模式遠小於號碼。如果你使用素數,那麼循環重複模式被保證至少與素數一樣大。
不幸的是,這是不正確的。你需要一個乘法羣的生成器來獲得最大週期。這與素質無關。 – Accipitridae 2009-09-30 17:03:15
考慮最簡單的乘法:x2。
它相當於左移位。換句話說,它確實沒有「隨機化」數據,它只是將其移交。
與x4一樣,或兩個任何冪。原始數據完好無損,剛剛移位。
現在,乘以其他數字(兩個非冪次)並不明顯,但仍然有相同的問題,或多或少。原始數據是完整的,或簡單地轉換。 (例如,x5與left-bitshift兩個地方相同,然後添加原始數據)。
GetHashCode的要點是基本上儘可能隨機地分配數據。乘以素數可以保證答案不會像比特移位或向自身添加數字那樣簡單。
@abelenky:字符串's'的一個更常見的哈希是'31 * s [0] + 31^2 * s [1] + ... + 31 ^(n-1)* s [n- 1]'。 '31'是素數。 「31」的乘法與位移和減法相同(即,「a * 31 =(a << 5)-a」)。這很簡單。所有這一切都是要指出,使用素數的原因不是僅僅混淆數據。 – jason 2009-09-28 20:02:24
這個散列,但33作爲乘數被稱爲djb散列。由於伯恩斯坦是數論的專家,所以他不使用素數當然不是偶然的。 – Accipitridae 2009-09-30 17:30:23
@Accipitridae:使用31的一個主要弱點是主要的是來自一對匹配連續字符的哈希貢獻將是32的倍數,有效地丟失5位。使用33會使得貢獻是34的倍數,這隻會丟失一位。 – supercat 2015-02-21 21:49:47
我不確定你正在談論哪種算法,但通常這些算法中的常量需要相對較好。否則,你會得到週期,並不是所有可能的值都顯示在結果中。
這個數字可能不需要在你的情況下是素數,只是相對於其他數字的素數,但是使它成爲主要保證。它也涵蓋了其他幻數改變的情況。例如,如果你正在談論取某個數字的最後一位,那麼乘數不需要是2的倍數。所以,即使它不是素數,9也可以工作。
我在這裏沒有真正的答案(我的老實人會是「因爲Josh Bloch這樣說!」),但http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx讓人感興趣讀。 – 2009-09-28 19:50:25
Duplicate:http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus – 2009-09-28 19:51:20
這是爲什麼關閉?一個因素和一個模數顯然不是一回事。 – Accipitridae 2009-09-30 16:59:16