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

希望能有所帮助。

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

希望能有所帮助。

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

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.

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

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