随机整数的完美哈希函数

Question

问题来了：

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 的顺序。

有什么线索吗？

Answer 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 遍历。

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

Answer 2

由于条目数较少，可以使用暴力破解。我发现了这个（Java：long是64位签名，int是32位签名）：

private static int hashReduce(long x, long seed, int n) {
    long x1 = ((long) x + seed);
    int x2 = (int) ((x1 >>> 32) ^ x1);
    int x3 = ((x2 >>> 16) ^ x2) * 0x45d9f3b;
    return (int) (((x3 & 0xffffffffL) * n) >>> 32);
}

public static void main(String... args) throws InterruptedException {
    long[] data = new long[] { 31, 223, 121, 100, 123, 71 };
    for (int j = 0; j < 6; j++) {
        System.out.println(data[j] + " -> " + hashReduce(data[j], -2126115507L, 6));
    } 
}

x: 31 -> 0
x: 223 -> 1
x: 121 -> 2
x: 100 -> 3
x: 123 -> 4
x: 71 -> 5

要找到种子值，需要迭代，例如如下：

for (int seed = Integer.MIN_VALUE; seed < Integer.MAX_VALUE; seed++) {
    testWithSeed(seed);
}

其中 testWithSeed 是用户定义的，并验证数据是否按预期映射。