随机整数的完美哈希函数

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