通用哈希誤解

我想了解通用哈希如何工作。它被定義爲h(x) = [(a*x + b) mod p] mod m其中a,b - 隨機數，m - 散列表的大小，x - 密鑰和p - 素數。例如，我有幾個不同的鑰匙：通用哈希誤解

92333 
23347 
20313

而且爲了創建一個通用散列函數我一定要到以下幾點：

Let a = 10, b = 22, p = 313, m = 100 
h(92333) = [(10 * 92333 + 22) mod 313] mod 100 = 2 mod 100 = 2 
h(23347) = [(10 * 23347 + 22) mod 313] mod 100 = 307 mod 100 = 7 
...

但可能每次我都會得到範圍從0到99，可能會有很多碰撞。

所以我的問題是：我理解並正確應用通用哈希？

來源

2014-10-08 Bob

爲什麼你會得到2到10之間的數字？應該在0到99之間。 – Thilo 2014-10-08 05:53:25

假設你哈希數字有均勻分佈的，你的函數向水桶0至12

偏置假設哈希運算直至幷包括mod 313操作發生。該操作的結果會爲您提供範圍爲0..312的值。同樣，如果該操作的結果是均勻分佈的，然後採取mod 100將得到以下效果：

result of  Occurs for these 
    mod 100  mod 313 results 
-----------  ------------------ 
    0   0, 100, 200, 300 
    1   1, 101, 201, 301 
    2   2, 102, 202, 302 
    3   3, 103, 203, 303 
    4   4, 104, 204, 304 
    5   5, 105, 205, 305 
    6   6, 106, 206, 306 
    7   7, 107, 207, 307 
    8   8, 108, 208, 308 
    9   9, 109, 209, 309 
    10   10, 110, 210, 310 
    11   11, 111, 211, 311 
    12   12, 112, 212, 312 
    13   13, 113, 213 
    14   14, 114, 214 
    15   15, 115, 215

通知機會的數量如何讓12後的特定結果下降？有你的偏見。這裏有更多的證據表明，計算散列數字0到5,000,000的結果會帶來這種效果：

counts[0]: 63898 
counts[1]: 63896 
counts[2]: 63899 
counts[3]: 63900 
counts[4]: 63896 
counts[5]: 63896 
counts[6]: 63900 
counts[7]: 63896 
counts[8]: 63896 
counts[9]: 63900 
counts[10]: 63898 
counts[11]: 63896 
counts[12]: 63899 
counts[13]: 47925 
counts[14]: 47922 
counts[15]: 47922 
counts[16]: 47925 

... elided similar counts ... 

counts[97]: 47922 
counts[98]: 47922 
counts[99]: 47925

來源

2014-10-08 06:22:41

我誤解了一點。所以爲了解決這個問題，我必須採取非常大的p，a，b？ – Bob 2014-10-08 06:28:37

我不確定我可以給出如何最好地選擇散列函數的各種參數的建議。另外，我在互聯網上找到的講座似乎沒有給出很多關於你正在討論的「MAD」（乘法，加法，除法）散列壓縮函數的建議或分析。這非常令人失望。我所知道的是，你所看到的特定數字似乎表明了這種偏見。 – 2014-10-08 07:03:16

但可能每次我都會得到範圍從0到99的數字，並且可能會有很多碰撞。

沒錯。但是你的散列表只有100個桶，所以如果你試圖插入多於幾十個鍵，你就不能避免衝突。

你可以希望的最好的結果是將碰撞均勻地分佈在整個一百個桶中，而你的哈希函數應該能夠粗略地做到這一點。這樣，在表格填滿之前，您不會碰到很多碰撞，碰撞也不會涉及太多的各方。

如果你想存儲更多的密鑰，你需要使表更大。

來源

2014-10-08 05:59:28 Thilo

因此，我必須拿m = 100萬，例如？我是否也應該改變p，a，b？ – Bob 2014-10-08 06:02:29

取決於你正在嘗試做什麼。具有百萬桶的哈希表需要比具有一百個的哈希表多一萬倍的存儲。 – Thilo 2014-10-08 06:03:51

通用哈希誤解

回答

相關問題