关于素数幂模的“数学的本质”是它们是有限域的一个组成部分。另外两个构建块是加法运算和乘法运算。素模的特殊性质是，它们用“常规”的加法和乘法运算形成一个有限域，只是取到模。这意味着每一个乘法都映射到一个不同的整数对质数求模，每一个加法也是如此。

质模的优势在于:

它们在二次哈希中选择次乘数时给予了最大的自由，除了0之外的所有乘数最终都将访问所有元素一次 如果所有哈希值都小于模量，则根本不会发生碰撞 随机质数比两个模的幂更好地混合，并压缩所有比特的信息，而不仅仅是一个子集

然而，它们有一个很大的缺点，它们需要整数除法，这需要很多(~ 15-40)个周期，即使在现代CPU上也是如此。用大约一半的计算就可以确保散列混合得很好。两次乘法和异移运算比一个质数模更容易混合。然后，我们可以使用任何哈希表的大小，哈希约简是最快的，对于2个表大小的幂，总共给出7个操作，对于任意大小的表，大约9个操作。

我最近研究了许多最快的哈希表实现，其中大多数都不使用质数模块。

哈希表索引的分布主要依赖于所使用的哈希函数。质数模量不能修复一个坏的哈希函数，一个好的哈希函数也不能从质数模量中受益。然而，在某些情况下，它们可能是有利的。例如，它可以修复半坏的哈希函数。

插入/从哈希表中检索时要做的第一件事是计算给定键的hashCode，然后通过执行hashCode % table_length将hashCode修剪为哈希表的大小来找到正确的bucket。这里有两个“陈述”，你很可能在某处读到过

如果对table_length使用2的幂，那么查找(hashCode(key) % 2^n)就像查找(hashCode(key) & (2^n -1))一样简单快捷。但是如果你为一个给定的键计算hashCode的函数不是很好，你肯定会在几个散列桶中聚集许多键。 但是，如果table_length使用质数，即使使用稍微愚蠢的hashCode函数，计算出来的hashCode也可以映射到不同的散列桶中。

这就是证明。

如果假设你的hashCode函数的结果是以下hashCode {x, 2x, 3x, 4x, 5x, 6x…}，那么所有这些都将聚集在m个桶中，其中m = table_length/GreatestCommonFactor(table_length, x)。(验证/推导这个很简单)。现在可以执行以下操作之一来避免集群

确保你不会生成太多的hashCode，这些hashCode是另一个hashCode的倍数，比如{x, 2x, 3x, 4x, 5x, 6x…}。但如果你的hashTable应该有数百万个条目，这可能有点困难。 或者通过使GreatestCommonFactor(table_length, x)等于1使m等于table_length，即使table_length与x为coprime。如果x可以是任何数字，则确保table_length是质数。

来自- http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html

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

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

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

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

这取决于哈希函数的选择。

许多哈希函数通过将数据中的各种元素与一些因子相乘，再乘以与机器的字大小相对应的2的幂的模(这个模可以通过让计算溢出来释放)来组合数据中的各种元素。

您不希望在数据元素的乘数和哈希表的大小之间有任何公共因子，因为这样可能会发生改变数据元素不会将数据分散到整个表上的情况。如果你为表的大小选择一个质数，这样的公因数是极不可能的。

另一方面，这些因数通常由奇数质数组成，因此在哈希表中使用2的幂也应该是安全的(例如，Eclipse在生成Java hashCode()方法时使用31)。

这个问题与更合适的问题合并，为什么哈希表应该使用素数大小的数组，而不是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)。

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

我想为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.

希望能有所帮助。