2

我试图了解通用散列是如何工作的。它被定义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 范围内的数字，并且可能会有很多碰撞。

所以我的问题是：我正确理解并应用了通用哈希？

4

2 回答 2

1

但可能每次我都会得到 0 到 99 范围内的数字，并且可能会有很多碰撞。

正确的。但是您的哈希表只有 100 个桶，因此如果您尝试插入超过几十个键，您将无法避免冲突。

您可以期望的最好的结果是将冲突均匀地分布在整个一百个存储桶中，您的哈希函数应该能够大致做到这一点。这样，在桌子填满之前，您不会遇到很多冲突，并且每个冲突都不会涉及太多各方。

如果要存储更多的键，则需要使表更大。

于 2014-10-08T05:59:28.180 回答
1

假设您要散列的数字具有均匀分布，则您的函数偏向于桶 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-08T06:22:41.080 回答