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

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

博士tl;

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

插入/从哈希表中检索时要做的第一件事是计算给定键的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

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

质模的优势在于:

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

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

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

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

Primes are used because you have good chances of obtaining a unique value for a typical hash-function which uses polynomials modulo P. Say, you use such hash-function for strings of length <= N, and you have a collision. That means that 2 different polynomials produce the same value modulo P. The difference of those polynomials is again a polynomial of the same degree N (or less). It has no more than N roots (this is here the nature of math shows itself, since this claim is only true for a polynomial over a field => prime number). So if N is much less than P, you are likely not to have a collision. After that, experiment can probably show that 37 is big enough to avoid collisions for a hash-table of strings which have length 5-10, and is small enough to use for calculations.

我想说，这个链接的第一个答案是我找到的关于这个问题的最清晰的答案。

考虑键K ={0,1，…，100}和一个哈希表，其中桶数为m = 12。因为3是12的因数，所以是3倍数的键将被散列到是3倍数的存储桶中:

键{0,12、24、36…}将被散列到bucket 0。 键{3,15日,27日,39岁,…}将被散列到桶3。 键{42 6日,18日,30日,…}将被散列到桶6。 键{9日,21日,33岁,45岁,…}将被散列到桶9。

如果K是均匀分布的(即K中的每个键出现的可能性都是相等的)，那么m的选择就不是那么关键了。但是，如果K不是均匀分布的呢?想象最有可能出现的键是3的倍数。在这种情况下，所有不是3倍数的桶都很可能是空的(这在哈希表性能方面非常糟糕)。

这种情况比看起来更常见。例如，想象一下，您正在根据对象在内存中的存储位置来跟踪它们。如果您的计算机的字大小是4个字节，那么您将哈希键是4的倍数。不用说，选择m是4的倍数将是一个糟糕的选择:你将有3m/4个桶完全空了，所有的键都在剩下的m/4个桶中碰撞。

一般来说:

K中每一个与桶数m有公因数的键都将被哈希为这个因数的倍数。

因此，为了尽量减少碰撞，减少m和k的元素之间的公因数的数量是很重要的，这是如何实现的呢?通过选择m是一个因数很少的数，一个质数。

来自马里奥的回答。