问极低成本散列函数

EN

它的规范形式是h(x) = (a*x + b) mod n，其中a和b是常量，n是哈希表的大小。您希望使n成为素数，以获得最优(Ish)分布。

请注意，这对某些类型的分布非常敏感--例如，仅仅执行x mod n主要依赖于低阶位的随机性；如果它们在您的集合中不是随机的，您将得到相当大的偏差。

Bob设计了几个非常好的散列函数；这里有一个专门设计成易于在硬件中实现的函数：http://burtleburtle.net/bob/hash/nandhash.html

有关许多不同的散列函数、设计讨论等，请参阅站点的其余部分：http://burtleburtle.net/bob/hash/

CRC？

这方面已经有很多硬件支持。

我相信这是解决这个问题的最好的散列(比模更快，分布更好)，考虑到0.N中的所有数字都有相同的概率：

h = z * n / N;

这里所有的值都是整数，所以你有一个整数除法。这样，0. n之间的每个值都映射到n中相同数目的值。

例如，当n=3和N=7 (值3和7不在范围内)时，散列如下：

z * n / N = hash
----------------
0 * 3 / 7 = 0
1 * 3 / 7 = 0
2 * 3 / 7 = 0
3 * 3 / 7 = 1
4 * 3 / 7 = 1
5 * 3 / 7 = 2
6 * 3 / 7 = 2

因此，每个哈希值的使用频率相等，仅为1。请注意，n*(N-1)不会溢出。

如果N是2的幂，你可以用移位代替除法。例如，如果N=256：

h = (z * n) >> 8;