0

这是问题所在：

X 是一个正整数（包括 0）集合，它具有我预先知道的 n 个不同元素。它们都小于m。我希望有一个尽可能简单的无 occ 哈希函数将它们映射到 0-n-1。

例如：

X = [31,223,121,100,123,71]，所以 n = 6，m = 223。

我想找到一个哈希函数将它们映射到 [0, 1, 2, 3, 4, 5]。

如果映射到 0-n-1 太难，那么如何将 X 映射到小范围也是一个问题。

找到这样的函数并不太难，但要简单易生成却很难。

最好保留 X 的顺序。

有什么线索吗？

4

1 回答 1

1

我最喜欢的完美哈希非常简单。

您生成的哈希函数具有以下形式：

hash = table1[h1(key)%N] + table2[h2(key)%N]

h1并且h2是随机生成的哈希函数。在您的情况下，您可以生成随机常数，然后具有h1(key)=key*C1/m和h2(key)=key*C2/m或类似简单的东西

要生成完美的哈希：

  1. 生成随机常数 C1 和 C2
  2. 想象一下二分图，其中table1槽和table2槽作为顶点，每个键在table1[h1(key)%N]和之间都有一条边table2[h2(key)%N]。运行 DFS 以查看图形是否是非循环的。如果不是，请返回步骤 1。
  3. 现在您有了一个无环图，从每个连接组件中的任何键/边开始，并设置它的插槽，table1但是table2您想给它任何hash您喜欢的东西。
  4. 从与您刚刚设置的边相邻的顶点开始遍历树。对于您遍历的每条边，已经设置了其中一个插槽。设置另一个以使散列值随心所欲地出现。

而已。所有步骤 (2)、(3) 和 (4) 都可以很容易地组合成一个 DFS 遍历。

完整的描述和分析在本文中。

于 2022-01-31T13:18:55.603 回答