什么整数散列函数适合接受整数散列键？
Knuth的乘法方法：
hash(i)=i*2654435761 mod 2^32
通常，您应该选择一个乘以您的散列大小（在示例中为2^32）的乘数，并且没有与之相关的公因子。这样，哈希函数统一覆盖了所有哈希空间。
编辑：这个哈希函数的最大缺点是它保留了可分性，所以如果你的整数都可以被2或4整除（这并不罕见），它们的哈希也是如此。这是哈希表中的一个问题 - 您最终只能使用1/2或1/4的桶。
自从我找到这个帖子以来，我一直在使用splitmix64（指向Thomas Mueller的answer）。然而，我最近偶然发现了Pelle Evensen的rrxmrrxmsx_0，它比原始的MurmurHash3终结者及其继承者（splitmix64和其他混音）产生了更好的统计分布。这是C中的代码片段：
#include <stdint.h>
static inline uint64_t ror64(uint64_t v, int r) {
return (v >> r) | (v << (64 - r));
}
uint64_t rrxmrrxmsx_0(uint64_t v) {
v ^= ror64(v, 25) ^ ror64(v, 50);
v *= 0xA24BAED4963EE407UL;
v ^= ror64(v, 24) ^ ror64(v, 49);
v *= 0x9FB21C651E98DF25UL;
return v ^ v >> 28;
}
Pelle还提供了在in-depth analysis最后一步中使用的64位混音器的MurmurHash3以及更新的变体。
快速和良好的散列函数可以通过组合几个具有较低质量的快速排列来组成，例如
产生具有优良品质的散列函数，如用PCG证明随机数生成。
这实际上也是rrxmrrxmsx_0和murmur hash正在使用，有意或无意地使用的配方。
我个人发现了
uint64_t rol(const uint64_t& n,int i){
return (n<<i)|(n>>(64-i);
}
uint64_t hash(const uint64_t& n){
uint64_t c = random_uneven_64_bit_integer_constant";
return c*rol(c*n,32);
}
要足够好。
或者你可以使用像GHash这样的伽罗瓦域乘法，它们在现代CPU上变得相当快，并且在一步中具有优越的品质。
我发现以下算法提供了非常好的统计分布。每个输入位以大约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（混合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;
}
对于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
会很好（我怀疑是最佳的，但我无法证明）。
This page列出了一些简单的散列函数，这些散列函数通常都很合适，但是任何简单的散列都有病态的情况，它不能正常工作。
#define hash32(x) ((x)*2654435761)
#define H_BITS 24 // Hashtable size
#define H_SHIFT (32-H_BITS)
unsigned hashtab[1<<H_BITS]
....
unsigned slot = hash32(x) >> H_SHIFT
有一些关于Eternally Confuzzled的哈希算法的概述。我推荐Bob Jenkins的一次性哈希值，它可以快速达到雪崩，因此可用于高效的哈希表查找。
我不认为我们可以在不事先知道您的数据的情况下说哈希函数是“好”的！并且不知道你将如何处理它。
对于未知数据大小，有比哈希表更好的数据结构（我假设你在这里为哈希表进行哈希）。当我知道我有一个“有限”数量的元素需要存储在有限的内存中时，我会亲自使用哈希表。在开始考虑我的哈希函数之前，我会尝试对我的数据进行快速统计分析，看看它是如何分布的。
对于随机哈希值，一些工程师说黄金比率素数（2654435761）是一个糟糕的选择，我的测试结果，我发现它不是真的;相反，2654435761分配哈希值非常好。
#define MCR_HashTableSize 2^10
unsigned int
Hash_UInt_GRPrimeNumber(unsigned int key)
{
key = key*2654435761 & (MCR_HashTableSize - 1)
return key;
}
哈希表大小必须是2的幂。
我编写了一个测试程序来评估整数的许多哈希函数，结果表明GRPrimeNumber是一个不错的选择。
我试过了：
根据我的测试结果，我发现黄金比例素数始终具有较少的空桶或零空桶以及最短的碰撞链长度。
一些整数的散列函数声称是好的，但测试结果表明，当total_data_entry / total_bucket_number = 3时，最长的链长大于10（最大碰撞数> 10），并且许多桶未映射（空桶） ），与黄色比率素数散列的零空桶和最长链长3的结果相比，这是非常糟糕的。
顺便说一下，根据我的测试结果，我发现一个版本的shift-xor哈希函数非常好（由mikera共享）。
unsigned int Hash_UInt_M3(unsigned int key)
{
key ^= (key << 13);
key ^= (key >> 17);
key ^= (key << 5);
return key;
}