问题
我们有一组符号序列，它们应该被Map到预定义数量的桶索引。
先决条件
符号序列的长度受到限制（64个字符/字节），使用的哈希算法是Bob Jenkins hash的 Delphi 实现，用于32位哈希值。
为了进一步将这些散列值分布在一定数量的桶上，我们使用以下公式：
num_buckets
(We不希望{0，1}出现在结果集中）
问题
一位同事有一些疑问，我们需要为num_buckets选择一个素数，以便在将符号序列Map到bucket_number时实现最优1分布。
团队中的大多数人认为这更多的是一个未经证实的假设，尽管我们的团队伙伴只是声称这是数学上的内在（没有更深入的解释）。
我可以想象，我们使用的某些符号序列模式（这只是实际允许的一个非常有限的子集）可能更喜欢某些 * hashvalue s*，但通常我不认为这对大量符号序列来说真的很重要。
散列算法应该已经将 * hashvalue s* 最优地分配了，我怀疑一个素数的模除数是否真的会产生显著的差异（也无法从经验上衡量），特别是因为据我所知，Bob Jenkins的散列演算也不涉及任何素数。
[TL;DR]
对于这种情况，质数的模除数是否重要？
1)最优简单地意味着每个桶的序列数的稳定平均值，其不随序列总数而改变（太多
1条答案
按热度按时间dgjrabp21#
你的同事完全错了。
如果散列工作良好，则所有散列值的可能性应该相等，其关系从输入数据来看并不明显。
当你对某个值进行哈希模运算时，你就把同样可能的哈希输入Map到了数量减少的输出桶中。结果现在并不是均匀分布的，以至于输出可以由不同数量的输入产生。只要桶的数量相对于哈希值的范围很小，这个差异是很小的。它的数量级为桶数/散列值数。由于桶数通常小于10^6而散列值数大于10^19，这确实是非常小的。2但是如果桶的数目除以散列值的范围，就没有差异了。
素数并不参与其中，除非当桶的数目除以哈希函数的值域时，你得到了最佳的分布。由于哈希函数的值域通常是2的幂，所以桶的素数不太可能为你做任何事情。