Question

我需要一个哈希函数用于查找表，以便如果我的值从0到N，则需要一个哈希函数，使我得到从0到n的值，其中n<

我一直在调查不同的低成本哈希函数，但我只找到了这个：

h = z mod n  range(z) - 0 to N, range(h) - 0 to n

我的哈希函数需要在硬件中实现，因此它需要具有非常低的成本。除了那个简单的东西，有没有人能推荐任何其他公式或算法？我所说的硬件是真正的硬件实现，而不是微处理器中的指令。

谢谢。

更新解决方案 (gēngxīn jiějué fāng'àn)

感谢所有答案，我不会选择一个最喜欢的，因为它们都同样有效，取决于目标应用程序的特征。

Answer 1

规范形式为h(x) = (a*x + b) mod n，其中a和b为常数，n为哈希表的大小。您希望将n设为质数，以获得最佳分配。

请注意，这对某些类型的分布是敏感的——例如，仅执行x mod n大多依赖于低位比特的随机性；如果它们在您的集合中不是随机的，则会导致相当显着的偏斜。

Bob Jenkins has designed several very good hashing functions; here s one specifically designed to be simple to implement in hardware: http://burtleburtle.net/bob/hash/nandhash.html

对于许多不同的哈希函数、设计讨论等等，请参阅该网站的其余部分：http://burtleburtle.net/bob/hash/

Answer 2

CRC？

对此，硬件支持已经非常多了。

Answer 3

我相信这是此问题的最佳哈希（比取模更快，分布更好），前提是您的所有数字在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;

Answer 4

随机重排位，取低log2(n)位。

如果您的数据均匀分布，只需取 log2(n) 位即可。

Answer 5

如果你真正讨论硬件（而不是软件或软件实现的硬件），并且你的哈希桶数量n可以写成n = 2的m次方 - 1，最简单的可能是一个最大长度线性反馈移位寄存器（LFSR），其中CRC是一个实例。

这是使用m位移位寄存器创建数据包哈希的一种方法（如果您有更短的字符串，请确保所有数据以K位字符串一致地表示，如果您有更短的字符串，则在一端用零进行填充）：

Initialize the state of the LFSR (CRC-32 uses all 1 s; all zeros is probably bad)
Shift in the bits of your data
(Optional) Shift in an additional j zeros (j between m and 2m is probably a good choice); this adds some additional hashing to reduce direct correlation between input/output bits
Use the contents of the m-bit shift register as your hashed value.