这个问题与更合适的问题合并，为什么哈希表应该使用素数大小的数组，而不是2的幂。 对于哈希函数本身，这里有很多很好的答案，但对于相关的问题，为什么一些安全关键的哈希表，如glibc，使用质数大小的数组，目前还没有。

通常两张表的幂要快得多。这里有昂贵的h % n => h和位掩码，其中位掩码可以通过大小为n的clz(“计数前导零”)计算。模函数需要做整数除法，这比逻辑和要慢50倍。有一些技巧可以避免取模，比如使用Lemire的https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/，但通常快速哈希表使用2的幂，而安全哈希表使用质数。

为什么如此?

Security in this case is defined by attacks on the collision resolution strategy, which is with most hash tables just linear search in a linked list of collisions. Or with the faster open-addressing tables linear search in the table directly. So with power of 2 tables and some internal knowledge of the table, e.g. the size or the order of the list of keys provided by some JSON interface, you get the number of right bits used. The number of ones on the bitmask. This is typically lower than 10 bits. And for 5-10 bits it's trivial to brute force collisions even with the strongest and slowest hash functions. You don't get the full security of your 32bit or 64 bit hash functions anymore. And the point is to use fast small hash functions, not monsters such as murmur or even siphash.

因此，如果你为哈希表提供一个外部接口，比如DNS解析器、编程语言……你想要关心那些喜欢使用DOS服务的人。对这些人来说，用简单得多的方法关闭你的公共服务通常更容易，但这种情况确实发生了。所以人们确实关心。

因此，防止这种碰撞攻击的最佳选择是

1)使用质数表，因为

所有32位或64位都与查找桶相关，而不仅仅是几个。 哈希表的大小调整函数比double更自然。最好的生长函数是斐波那契数列，质数更接近于它，而不是翻倍。

2)使用更好的措施对抗实际攻击，加上2个尺寸的快速功率。

计算碰撞次数，并在检测到攻击时中止或休眠，即概率<1%的碰撞次数。比如100个32位哈希表。这就是djb的dns解析器所做的。 当检测到碰撞攻击时，将碰撞链表转换为O(log n)搜索而不是O(n)的树。这就是例如java所做的。

有一个广为流传的神话，更安全的哈希函数有助于防止这种攻击，这是错误的，正如我解释的那样。只有低比特是不安全的。这只适用于质数大小的表，但这将使用两个最慢方法的组合，慢哈希+慢质数模。

哈希表的哈希函数主要需要小(内联)和快速。安全性只能来自于防止冲突中的线性搜索。并且不要使用非常糟糕的哈希函数，比如对某些值不敏感的哈希函数(比如使用乘法时的\0)。

使用随机种子也是一个不错的选择，人们首先使用随机种子，但是有了足够的表信息，即使是随机种子也没有多大帮助，而动态语言通常使通过其他方法获取种子变得很简单，因为它存储在已知的内存位置中。

假设表的大小(或模数)是T = (B*C)。如果你输入的散列是(N*A*B) N可以是任何整数，那么你的输出就不会很好地分布。因为每次n变成C、2C、3C等，你的输出就会开始重复。也就是说，你的输出只会分布在C位。注意这里的C是(T / HCF(表大小，哈希))。

这个问题可以通过制造hcf1来消除。质数是很好的选择。

另一个有趣的现象是当T = 2^N时。这些将给出与所有输入哈希的低N位完全相同的输出。由于每个数都可以表示为2的幂，当我们对任意数取T的模时，我们将减去所有2的幂形式的数，即>= N，因此总能得到特定模式的数，取决于输入。这也是一个糟糕的选择。

类似地，T作为10^N也是不好的，因为类似的原因(模式是十进制数而不是二进制数)。

因此，质数往往会给出更好的分布结果，因此是表大小的好选择。

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

解释得很清楚，还有图片。

编辑:作为一个总结，使用质数是因为当数值乘以所选质数并将它们全部相加时，获得唯一值的可能性最大。例如，给定一个字符串，将每个字母的值与质数相乘，然后将它们全部相加，就会得到它的哈希值。

一个更好的问题是，为什么是数字31?

博士tl;

Index [hash(input)%2]将导致所有可能哈希值的一半和一段值发生冲突。Index [hash(input)%prime]导致所有可能哈希值中的<2的碰撞。将除数固定为表的大小还可以确保数字不能大于表。

我想为Steve Jessop的回答补充一些东西(我不能评论，因为我没有足够的声誉)。但我找到了一些有用的材料。他的回答很有帮助，但他犯了一个错误:桶的大小不应该是2的幂。我引用Thomas Cormen, Charles Leisersen等人写的《算法导论》263页

When using the division method, we usually avoid certain values of m. For example, m should not be a power of 2, since if m = 2^p, then h(k) is just the p lowest-order bits of k. Unless we know that all low-order p-bit patterns are equally likely, we are better off designing the hash function to depend on all the bits of the key. As Exercise 11.3-3 asks you to show, choosing m = 2^p-1 when k is a character string interpreted in radix 2^p may be a poor choice, because permuting the characters of k does not change its hash value.

希望能有所帮助。

我读过一个流行的wordpress网站，上面有一些流行的答案。根据我的理解，我想分享一个简单的观察。

你可以在这篇文章中找到所有的细节，但假设以下是正确的:

使用质数给我们提供了一个唯一值的“最佳机会”

一个通用的hashmap实现需要有两个东西是唯一的。

键的唯一哈希码 用于存储实际值的唯一索引

我们如何得到唯一索引?通过使内部容器的初始大小也是质数。基本上，质数的存在是因为它具有产生唯一数字的独特特性，我们最终用它来标识对象并在内部容器中查找索引。

例子:

Key = " Key "

Value = " Value " uniqueId = "k" * 31 ^ 2 + "e" * 31 ^ 1 ' + “y”

映射到唯一id

现在我们想要一个独特的位置来存放我们的价值，所以我们

uniqueId % internalContainerSize == uniqueLocationForValue，假设internalContainerSize也是质数。

我知道这是简化的，但我希望你能理解我的大意。