哈希函數爲什麼要使用素數模數？

Question

很久以前，我以1.25美元的價格從討價還價的桌子上買了一本數據結構書。其中，哈希函數的解釋說，它應該最終由於「數學的性質」而被素數修改。

你對1.25美元的書有什麼期望？

無論如何，我已經有數年的時間來思考數學的本質，但仍然無法弄清楚。

即使存在桶的素數，分配的數字是否真的更多？或者這是一個老的程序員的故事，每個人都接受，因爲每個人都接受其他接受它？

Answer 1

一般簡單的散列函數的工作原理是服用「組成部件」輸入的（在一個字符串的情況下的字符），並且通過一些恆定的功率乘以它們，並且在一些整數類型一起添加。因此，例如一個字符串的典型（雖然不是特別好）哈希可能是：

(first char) + k * (second char) + k^2 * (third char) + ... 

然後，如果一串字符串的所有具有相同的第一個字符被送入，然後將結果都是相同的模k，至少直到整型溢出。

[作爲一個例子，Java的字符串的hashCode是極其相似此 - 它的字符反序，其中k = 31。因此，你可以在以相同方式結束的字符串之間取模31之間的關係，並且在除了結尾以外的字符串之間以2^32之間的模數顯示關係。這通過利用哈希模量超過桶的數量不認真搞砸了哈希表的行爲。]

散列表的作品。

在散列表中，不要爲可能的情況產生衝突很重要，因爲衝突會降低散列表的效率。

現在，假如有人放了一大堆值成有項目之間的一些關係，像所有具有相同的第一個字符一個哈希表。這是一個相當可預測的使用模式，我想說，所以我們不希望它產生太多的衝突。

事實證明，「由於數學的性質」，如果哈希中使用的常量和桶的數量是coprime，那麼在一些常見情況下碰撞被最小化。如果它們不是coprime，那麼碰撞未被最小化的輸入之間存在一些相當簡單的關係。所有的哈希都等同於公共因子的模數，這意味着它們全部落入具有該公因子模值的桶的第1/n個桶中。你碰到n次碰撞的次數是n次，其中n是公因數。由於n至少是2，所以我認爲用相當簡單的用例來產生至少兩倍於正常的碰撞是不可接受的。如果一些用戶打算將我們的配置分成桶，我們希望它是一個怪胎事故，而不是一些簡單的可預測的用法。

現在，散列表實現顯然無法控制放入它們的項目。他們不能阻止他們相關。所以要做的是確保常量和桶計數是相互矛盾的。這樣，您不依賴於「最後」組件來確定相對於某個小公因子的剷鬥模數。據我所知，他們不一定要做到這一點，只是互相矛盾。

但是，如果散列函數和散列表獨立編寫，那麼散列表不知道散列函數是如何工作的。它可能會使用一個具有小因素的常量。如果幸運的話，它可能會完全不同並且是非線性的。如果哈希足夠好，那麼任何存儲桶計數都很好。但是一個偏執的散列表不能假定一個好的散列函數，所以應該使用一個素數的散列表。同樣，一個偏執散列函數應該使用一個大的素數常量，以減少某人使用多個桶的機會，這個桶恰好與常數有一個共同的因子。

實際上，我認爲使用2的冪作爲桶的數量是相當正常的。這很方便，不必搜索或預先選擇正確幅度的素數。所以你依靠哈希函數不要使用偶數乘法器，這通常是一個安全的假設。但是，您仍然可以根據像上面那樣的哈希函數偶爾獲得不良的哈希行爲，並且主要存儲區計數可以進一步提供幫助。

提到「一切都必須是最好的」原則就我所知足夠但不是通過散列表進行良好分配的必要條件。它允許每個人進行互操作，而不需要假定其他人遵循相同的規則。

[編輯：有另一個更專業的理由使用素數桶，這是如果你處理碰撞與線性探測。然後你從哈希碼計算出一個步幅，如果這個步幅是桶數的一個因素，那麼你只能在你回到開始位置之前進行（bucket_count/stride）探測。你最想避免的情況是stride = 0，當然，它必須是特殊的，但爲了避免特殊情況下的bucket_count/stride等於一個小整數，你可以使bucket_count成爲prime，而不用關心提供的步長不爲0.]

Answer 2

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

相當清楚的解釋，用圖片了。

編輯：作爲一個總結，使用素數是因爲當將數值乘以所選素數並將它們全部加起來時，您有最佳機會獲得唯一值。例如給定一個字符串，將每個字母值與素數相乘，然後將這些加起來就會得到它的哈希值。

更好的問題是，爲什麼數字31？

Answer 3

素數是唯一的數字。他們是 獨特之處在於，一個主要 與其他任何數量的產品擁有最佳的 機會是獨一無二的（不是唯一 作爲課程的主要本身）由於 一個主要用於 事實撰寫它。該屬性用於散列函數 。

給出一個字符串「塞繆爾」，你可以 生成每個乘法 的組成部分數字或字母 唯一哈希與一個素數和增加 起來。這就是使用素數的原因。

但是使用素數是舊的 技術。瞭解 的關鍵在於，只要您可以生成足夠唯一的密鑰，您就可以將 移動到其他哈希技術。去 這裏瞭解更多關於這個主題有關 http://www.azillionmonkeys.com/qed/hash.html

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

Answer 4

只是提供一個備用的觀點有這個網站：

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth

哪些爭辯說，你應該使用人數最多的桶可能，而不是四捨五入到大量的桶。這似乎是一個合理的可能性。直覺上，我當然可以看到更多數量的桶會更好，但我無法對此進行數學論證。

Answer 5

這取決於散列函數的選擇。

許多散列函數乘以它們與一些因素模的兩個對應於機器的字的大小（即彈性模量是通過僅讓計算溢出免費）的功率相結合的數據的各種元素。

你不想爲一個數據元素和哈希表大小的乘數之間的共同因素，因爲那可能發生變化的數據元素不超過整個表傳播數據。如果您選擇表中的素數，那麼這樣一個公共因素是不太可能的。另一方面，這些因素通常由奇素數組成，因此您應該也可以安全地使用散列表的兩個冪（例如，Eclipse在生成Java hashCode（）方法時使用31）。

Answer 6

對於散列函數，它不僅非常重要，以儘量減少colisions，但使chan幾個字節時不可能保持相同的散列。

假設你有一個方程： (x + y*z) % key = x與0<x<key和0<z<key。 如果密鑰是素數n * y =密鑰對於N中的每個n都是對的，對於其他每個數都是false。因爲key/z = 4仍然是一個自然數，所以4成爲我們方程的解，在這個例子中，對於N中的每個n，情況（n/2）* y =關鍵是成立的。由於8不是素數，所以方程的解的數量已經成倍增加。

如果我們的攻擊者已經知道8是可能的解決方案，他可以將文件從生成8更改爲4，仍然獲得相同的散列。

Answer 7

從哈希表插入/返回時，您要做的第一件事就是計算給定鍵的hashCode，然後通過執行hashCode％table_length將hashCode修剪爲hashTable的大小來查找正確的桶。下面是你，如果你對table_length使用2的冪，找到最有可能已經在某處讀到

1. 2「的語句」（的hashCode（鍵）％2^n）是一樣簡單和快捷（的hashCode（關鍵）&（2^n-1））。但是如果你的函數爲一個給定的密鑰計算hashCode並不好，你肯定會遭受來自幾個哈希桶中許多密鑰的聚集。
2. 但是，如果你使用素數的table_length，hashCodes計算可以映射到不同的哈希桶，即使你有一個愚蠢的hashCode函數。

這裏是證明。

如果假設您的hashCode函數產生了其他{x，2x，3x，4x，5x，6x ...}中的以下哈希代碼，那麼所有這些將僅聚集在m個桶中，其中m = table_length/GreatestCommonFactor（table_length，x）。 （這是微不足道的驗證/派生這個）。現在，您可以執行以下操作之一以避免羣集

請確保您不會生成太多的hashCode，它們是{x，2x，3x，4x，5x，6x ...}中另一個hashCode的倍數但如果你的hashTable應該有數以百萬計的條目，這可能會有點困難。 或者通過使GreatestCommonFactor（table_length，x）等於1，即通過使table_length與x互質來簡單地使m等於table_length。如果x可以是任何數字，那麼請確保table_length是一個素數。

從 - http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html

Answer 8

TL;博士

index[hash(input)%2]會導致所有可能的哈希值的一半和值範圍的衝突。 index[hash(input)%prime]導致所有可能的哈希碰撞。將除數修正爲表格大小還可確保該數字不能大於表格。

Answer 9

使用素數是因爲您有很好的機會獲得使用多項式模P的典型散列函數的唯一值。假設您對長度爲< = N的字符串使用這種散列函數，並且您擁有碰撞。這意味着2個不同的多項式產生相同的P值模。這些多項式的差異又是一個相同度N（或更小）的多項式。它不超過N根（這是數學演示本身的本質，因爲這種說法只適用於一個場上的多項式=>素數）。所以如果N比P小得多，你很可能不會碰撞。之後，實驗可能會顯示37足夠大以避免碰撞長度爲5-10的字符串散列表，並且足夠小以用於計算。

Answer 10

我想爲Steve Jessop的回答添加一些內容（由於我沒有足夠的聲望，我無法評論它）。但是我找到了一些有用的材料。他的回答是非常有幫助的，但他犯了一個錯誤：桶大小不應該是2的冪。我將引用Thomas Cormen，Charles Leisersen等人的書籍「Introduction to Algorithm」第263頁：

當使用除法時，我們通常會避免m的某些值。例如，m不應該是2的冪，因爲如果m = 2^p，那麼h（k）就是k的p個最低位。除非我們知道所有低階p位模式具有相同的可能性，否則我們最好設計散列函數以取決於密鑰的所有位。當練習11.3-3要求你展示時，當k是以2×p解釋的字符串時，選擇m = 2^p-1可能是一個糟糕的選擇，因爲置換k的字符不會改變它的散列值。

希望它有幫助。

Answer 11

假設你的表大小（或模數）是T =（B * C）。現在如果你的輸入的散列是（N * A * B），其中N可以是任何整數，那麼你的輸出將不會很好地分佈。因爲每當n變成C，2C，3C等時，你的輸出將開始重複。即您的輸出將僅分佈在C位置。請注意，這裏的C是（T/HCF（表大小，散列））。

這個問題可以通過使HCF 1消除。素數是非常好的。

另一個有趣的事情是當T是2^N時。這些將輸出與輸入散列的所有較低N位完全相同。由於每個數字都可以表示爲2的冪，所以當我們用T對任意數字進行模數化時，我們將減去2個數字形式的所有冪數，這是≥= N，因此總是根據輸入給出特定模式的數字。這也是一個不好的選擇。

類似地，由於類似的原因，T爲10^N也不好，因爲類似的原因（用十進制表示而不是二進制數字）。

所以，素數往往會給出更好的分佈式結果，因此是表大小的不錯選擇。

Answer 12

複製從我的其他答案https://stackoverflow.com/a/43126969/917428。查看更多細節和示例。

我認爲它只是一個事實，即計算機與基地2試想在同樣的事情是如何工作的基地10個工作要做：

• 8％10 = 8
• 18％10 = 8
• 87865378％10 = 8

不要緊數目是什麼：只要它具有8個端部，其模10將8.

選擇一個足夠大的非冪次數字將確保散列函數真的是所有輸入位的函數，而不是它們的子集。