什么整数哈希函数可以接受整数哈希键？

什么整数哈希函数可以接受整数哈希键？

我发现以下算法提供了非常好的统计分布。每个输入位以大约 50% 的概率影响每个输出位。不存在冲突（每个输入都会产生不同的输出）。除非 CPU 没有内置整数乘法单元，否则该算法速度很快。 C 代码，假设int是 32 位（对于 Java，替换>> with >>>并删除unsigned):

unsigned int hash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}

幻数是使用以下公式计算的特殊的多线程测试程序 https://github.com/h2database/h2database/blob/master/h2/src/test/org/h2/test/store/CalculateHashConstant.java运行多个小时，计算雪崩效应（如果单个输入位发生更改，则输出位的数量发生变化；平均应接近 16）、输出位变化的独立性（输出位不应相互依赖） ，以及如果任何输入位发生变化，每个输出位发生变化的概率。计算出的值比使用的 32 位终结器更好杂音哈希 https://code.google.com/p/smhasher/wiki/MurmurHash3，并且几乎与使用时一样好（不完全）AES http://en.wikipedia.org/wiki/Advanced_Encryption_Standard。一个小小的优点是相同的常量被使用两次（它确实使我上次测试时的速度稍微快一些，不确定是否仍然如此）。

如果替换，您可以反转该过程（从哈希中获取输入值）0x45d9f3b with 0x119de1f3 (the 乘法逆元 https://lemire.me/blog/2017/09/18/computing-the-inverse-of-odd-integers/):

unsigned int unhash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = (x >> 16) ^ x;
    return x;
}

对于 64 位数字，我建议使用以下内容，即使它可能不是最快的。这个是基于分割混合64 http://xorshift.di.unimi.it/splitmix64.c，这似乎是基于博客文章更好的位混合 http://zimbry.blogspot.it/2011/09/better-bit-mixing-improving-on.html（混合13）。

uint64_t hash(uint64_t x) {
    x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
    x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
    x = x ^ (x >> 31);
    return x;
}

在这种情况下，反转就更复杂了：

uint64_t unhash(uint64_t x) {
    x = (x ^ (x >> 31) ^ (x >> 62)) * UINT64_C(0x319642b2d24d8ec3);
    x = (x ^ (x >> 27) ^ (x >> 54)) * UINT64_C(0x96de1b173f119089);
    x = x ^ (x >> 30) ^ (x >> 60);
    return x;
}

以上所有内容均适用于 C。对于 Java，请使用long, add L为常数，替换>> with >>>并删除unsigned.

更新：您可能还想查看哈希函数探矿者 https://github.com/skeeto/hash-prospector项目，其中列出了其他（可能更好的）常量。