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

EN

Knuth的乘法：

hash(i)=i*2654435761 mod 2^32

通常，您应该选择一个与您的散列大小顺序一致的乘数(在本例中为2^32)，并且该乘数没有公因子。通过这种方式，哈希函数统一地覆盖了所有的哈希空间。

编辑:这个散列函数最大的缺点是它保留了整除性，所以如果你的整数都可以被2或4整除(这并不少见)，它们的散列也会被整除。这是哈希表中的一个问题--您最终可能只使用了1/2或1/4的存储桶。

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

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

幻数是使用运行了许多小时的special multi-threaded test program计算的，它计算雪崩效应(如果单个输入位改变，则改变的输出位的数量；平均应该接近16 )，输出位改变的独立性(输出位不应该相互依赖)，以及如果任何输入位改变，每个输出位改变的概率。计算出的值比MurmurHash使用的32位终结器要好，几乎和使用AES时一样好(不完全一样)。一个小小的优点是相同的常量被使用了两次(我上次测试时确实让它稍微快了一点，不确定它是否仍然是这样的)。

如果您将0x45d9f3b替换为0x119de1f3 (multiplicative inverse)，则可以反转此过程(从散列中获取输入值)：

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

对于64位数字，我建议使用下面的方法，即使它可能不是最快的。这篇文章基于splitmix64，似乎是基于博客文章Better Bit Mixing (Mix13)。

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;
}

对于Java，使用long，将L添加到常量中，将>>替换为>>>并删除unsigned。在这种情况下，反转更加复杂：

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;
}

更新:您可能还想看看Hash Function Prospector项目，其中列出了其他(可能更好的)常量。

这取决于您的数据是如何分布的。对于一个简单的计数器，最简单的函数

f(i) = i

将是好的(我怀疑是最优的，但我不能证明它)。