arrays - 为什么将 HashTable 的长度设置为质数是一个好习惯？

Question

我正在浏览 Eric Lippert 的最新博文 Guidelines and rules for GetHashCode当我点击这个段落时:

We could be even more clever here; just as a List resizes itself when it gets full, the bucket set could resize itself as well, to ensure that the average bucket length stays low. Also, for technical reasons it is often a good idea to make the bucket set length a prime number, rather than 100. There are plenty of improvements we could make to this hash table. But this quick sketch of a naive implementation of a hash table will do for now. I want to keep it simple.

看来我错过了什么。为什么将其设置为素数是一个好习惯？

Answer 1

您可以找到提出光谱两端的人。一方面，为哈希表的大小选择质数将减少冲突的机会，即使哈希函数在分配结果时不是太有效。请注意，如果(在争论的最简单的例子中)决定了 2 的幂大小，则只有较低的位会影响桶，而对于质数，将使用散列结果中的大部分位。

另一方面，您可以通过选择更好的散列函数获得更多 yield ，或者甚至通过应用一些位操作重新散列散列函数的结果，并使用 2 的散列大小的幂来加速计算。

举个现实生活中的例子，Java HashTable 最初是使用质数(或几乎质数大小)实现的，但从 Java 1.4 开始，设计改为使用两个桶的幂并添加了第二个快速哈希函数应用于初始散列的结果。可以找到一篇评论更改的有趣文章 here .

所以基本上:

• 素数有助于将输入分散到不同的桶中，即使在哈希函数不太理想的情况下也是如此。

• 通过对哈希函数的结果进行后处理，并使用 2 的幂大小来加速模运算(位掩码)并补偿后处理，可以实现类似的效果。