如何測試我的哈希函數在最大負載方面是否好？

Question

我已閱讀了關於'球和箱'問題的各種論文，並且似乎如果散列函數工作正確（即它實際上是一個隨機分佈），那麼如果我散列n值，則以下內容應該/必須爲真與n槽（或容器）哈希表：

1. 概率，一個倉是空的，對於大n是1/e。
2. 預計空箱數量爲n/e。
3. bin有k球的概率是<= 1/ek!（已更正）。
4. bin至少有k次碰撞的概率是<= ((e/k)**k)/e（已更正）。

這些看起來很容易檢查。但是max-load測試（高概率碰撞的最大數量）通常隱約表示。

大多數文本指出，任何bin中的最大碰撞次數爲O(ln(n)/ln(ln(n)))。 有人說這是3*ln(n)/ln(ln(n))。其他論文混合使用ln和log - 通常沒有定義它們，或者指出log是以log爲基礎的e，然後在其他地方使用ln。

是ln立足e或2日誌，是這個max-load配方權，有多大應該n是運行試驗？

這個講座似乎很好地涵蓋了它，但我不是數學家。

http://pages.cs.wisc.edu/~shuchi/courses/787-F07/scribe-notes/lecture07.pdf

BTW，with high probability似乎意味着1 - 1/n。

Answer 1

這是一篇引人入勝的論文/講座 - 讓我希望我已經參加了一些正式的算法課。

基於我剛剛讀過的內容，我會在這裏嘗試一些答案，並隨時給我投票。不過，我會欣賞一個更正，而不僅僅是一個downvote :)我也會在這裏交替使用n和N，這在一些圈子中是一個很大的禁忌，但因爲我只是複製粘貼公式，我希望你能原諒我。

首先，日誌的基礎。這些數字以大O符號給出，而不是絕對公式。這意味着你正在尋找'ln（n）/ ln（ln（n））'的順序，而不是絕對答案的預期，但是隨着n越來越大，n與最大碰撞次數應該遵循該公式。你可以繪製的實際曲線的細節會因實現而有所不同（我不太瞭解實際的實現方式，告訴你什麼是「好」曲線，除了它應該遵循這種大O關係）。您發佈的這兩個公式實際上在大O符號中是等效的。第二個公式中的3只是一個常數，並且與特定的實現有關。效率不高的實現會有更大的常量。

考慮到這一點，我會進行經驗性測試，因爲我是一位生物學家，而且我接受過培訓，以避免作爲世界實際工作方式的指示的硬性和快速證明。以N開頭，例如100，然後找到碰撞數量最大的箱子。這是你運行的最大負荷。現在，您的示例應該儘可能接近您期望實際用戶使用的示例，因此您可能希望隨機抽取字典中的單詞或與輸入類似的內容。

運行該測試多次，至少30次或40次。由於您使用的是隨機數，因此您需要確保您獲得的平均最大負載接近理論上的「期望值」你的算法。期望值只是平均值，但你仍然需要找到它，並且你的std dev/std err越接近該平均值，你越可以說你的經驗平均值與理論預期相符。一次運行是不夠的，因爲第二次運行（很可能）會給出不同的答案。

然後，增加N，例如1000,10000等。因爲你的公式是對數的，所以增加它的對數。隨着你的N增加，你的最大負載應該按照ln（n）/ ln（ln（n））的順序增加。如果它以3 * ln（n）/ ln（ln（n））的速度增長，那就意味着你正在按照他們在那次演講中提出的理論。

這種實證測試也會告訴你你的方法在哪裏崩潰。這可能是因爲你的算法適用於1000萬（或其他數字）的N <，但在此之上，它開始崩潰。爲什麼會這樣？也許你在代碼中有32位的限制而沒有意識到它（即使用'float'而不是'double'）或者其他一些實現細節。這些類型的細節可以讓你知道你的代碼在實際中的工作情況，然後當你的實際需求發生變化時，你可以修改你的算法。也許讓算法適用於非常大的數據集使其對於非常小的數據集非常低效，反之亦然，所以指出這種折衷將幫助您進一步表徵如何使算法適應特定情況。總是一個有用的技能。

編輯：爲什麼日誌功能的基礎不與大O記法關係的證明：

log N = log_10 (N) = log_b (N)/log_b (10)= (1/log_b(10)) * log_b(N) 

1/log_b（10）是一個常數，在大O記法，常量被忽略。基礎變化是免費的，這就是爲什麼你在論文中遇到這種變化。

Answer 2

經過一些更多的研究和反覆試驗後，我認爲我可以提供一些方法來回答問題。

1. 要開始了，ln和log似乎是指登錄以e爲基數，如果你看看背後的理論的數學。但正如mmr所指出的那樣，對於O（...）的估計，這並不重要。

2. max-load可以定義爲您喜歡的任何概率。所用的典型配方是

   1-1/N **ç

大多數在話題使用

1-1/n 

一個例子可能是最簡單的論文。

假設你有一個散列表1000插槽，你想散列1000東西。假設您還想知道max-load，概率爲1-1/1000或0.999。

max-load是散列值的最大數量，它們的結果是相同的 - 即。碰撞（假設你的散列函數是好的）。

使用用於獲取準確k相同散列值的概率的公式值

Pr[ exactly k ] = ((e/k)**k)/e 

然後通過累積的確切0..k項的概率總和等於直到或超過0.999告訴你k是max-load。

例如。

Pr[0] = 0.37 
Pr[1] = 0.37 
Pr[2] = 0.18 
Pr[3] = 0.061 
Pr[4] = 0.015 
Pr[5] = 0.003  // here, the cumulative total is 0.999 
Pr[6] = 0.0005 
Pr[7] = 0.00007 

因此，在這種情況下，max-load是5。

因此，如果我的散列函數在我的數據集上運行良好，那麼我應該期望相同散列值（或衝突）的最大數量爲5。

如果不是那麼這可能是由於以下原因：

1. 您的數據的較小值（如短字符串），散列爲相同的值。任何單個ASCII字符的散列都會從128個散列值中選擇1個散列值（例如，可以使用多個散列函數，但會減慢散列速度，對此我也不太瞭解）。

2. 您的散列函數不適用於您的數據 - 嘗試使用隨機數據。

3. 你的散列函數不能正常工作。

我在我的問題中提到的其他測試也有助於看到您的散列函數按預期運行。

順便說一下，我的散列函數很好地工作 - 除了短（1..4個字符）的字符串。

我還實現了一個簡單的拆分表版本，它將哈希值放置在2個位置中最少使用的位置。這大大減少了碰撞次數，並且意味着添加和搜索哈希表會稍微慢一些。

我希望這會有所幫助。

Answer 3

下面是涉及均勻分佈和最大負荷的這個問題的解決方案的粗略開始。

除了垃圾桶，垃圾桶，垃圾箱或垃圾箱或m和n，人們（p）和門（d）都將被用作名稱。

給定一定數量的人每個門的確切預期值。例如，對於5人和5個門，期望的最大門正好是平均值（p/d）以上的1.2864 {（1429-625）/ 625}，並且最小門正好是-0.9616 {（24-625）/ 625 }低於平均值。最高門距離平均值的絕對值比最小門的距離大一點，因爲所有的人都可以通過一扇門，但不小於零的門可以通過其中一扇門。隨着大量人員（p/d> 3000），最高門與平均值的距離與最低門之間的差異變得可以忽略不計。

對於奇數門，中心門基本爲零，不可擴展，但所有其他門都可以從表示p = d的某些值進行縮放。爲d = 5這些四捨五入值：

-1.163 -0.495 0 * 0.495 1.163 *慢慢地從-0.12

從這些值接近零，您可以計算人的預期數量的人的任何數通過5個門中的每一個，包括最大的門。除中間門外，與平均值的差值可以按sqrt（p/d）進行縮放。

因此，對於p = 50,000和d = 5：
預期通過最大門的人數，可能是5個門中的任何一個，= 1.163 * sqrt（p/d）+ p/d。 = 1.163 * sqrt（10,000）+ 10,000 = 10,116.3 對於p/d < 3,000，該等式的結果必須稍微增加。

隨着人數的增加，中間門從p = 100和d = 5時的-0.11968慢慢變得越來越接近於零。它總是可以被舍入到零，並且像其他4個門一樣有差異。

6米的門的值是： -1.272 -0.643 -0.202 0.202 0.643 1.272

對於1000門，近似值是： -3.25，-2.95，-2.79 ... 2.79，2.95，3.25

對於任何d和p，每個有序門都有確切的期望值。希望存在一個很好的近似值（相對誤差爲< 1％）。某個教授或數學家必須知道。

爲了測試均勻分配，您需要一些平均的有序會話（750-1000），而不是更多的人。無論如何，有效會話之間的差異都很大。這就是隨機性的本質。碰撞是不可避免的。 *

5門和6門的期望值是通過使用640位整數進行純粹的強力計算並平均對應相對門的絕對值的收斂來獲得的。 對於d = 5和p = 170： -6.63901 -2.95905 -0.119342 2.81054 6.90686 （27.36099 31.04095 33.880658 36.81054 40.90686） 對於d = 6且p = 108： -5.19024 -2.7711 -0.973979 0.734434 2.66716 5.53372 （12.80976 15.2289 17.026021 18.734434 20.66716 23.53372）

我希望你可以平均分配你的數據。

• 這幾乎可以保證喬治福爾曼的所有兒子或類似的情況都會對抗你的散列函數。適當的應急計劃是所有優秀程序員的工作。