为什么将HashTable的长度设置为素数是一个好习惯？
当我点击这段时，我正在阅读Eric Lippert 关于GetHashCode指南和规则的最新博客post：
我们在这里可能更聪明; 就像List在它满了时resize一样，bucket set也可以自己resize，以确保平均bucket长度保持低位。 此外，由于技术原因，通常最好将存储桶设置长度设为素数，而不是100.我们可以对此哈希表进行大量改进。 但是这个哈希表的简单实现的快速草图现在可以做到。 我想保持简单。
所以看起来我错过了一些东西。 为什么将它设置为素数是一个好习惯？
假设您的铲斗设置长度是2的幂 – 这使得mod计算非常快。 它还意味着桶选择仅由哈希码的前m位确定。 （其中m = 32 - n ，其中n是使用2的幂）。 所以它就像你立即丢弃哈希码的有用位。
或者像2006年的博客文章中所说：
假设你的hashCode函数产生以下hashCodes以及其他{x，2x，3x，4x，5x，6x …}，那么所有这些将集中在m个桶中，其中m = table_length / GreatestCommonFactor（ table_length，x）。 （validation/得出这个是微不足道的）。 现在，您可以执行以下操作之一以避免群集：
…
或者通过使GreatestCommonFactor（table_length，x）等于1来简单地使m等于table_length，即通过使table_length与x进行互操作。 如果x可以是任何数字，那么请确保table_length是素数。
您可以找到建议频谱两个相反端的人。 另一方面，为哈希表的大小选择素数将减少冲突的可能性，即使哈希函数不太有效地分配结果。 注意，如果（在最简单的例子中争论）确定2个大小的幂，则只有较低位影响桶，而对于素数，将使用散列结果中的大多数位。
另一方面，通过选择更好的散列函数，甚至通过应用一些位操作来重新散列散列函数的结果，并使用2散列大小的幂来加速计算，您可以获得更多。
作为现实生活中的一个例子，Java HashTable最初是通过使用素数（或接近素数）来实现的，但是从Java 1.4开始，设计被改为使用两个桶的功率并添加了第二个快速哈希函数应用于初始哈希的结果。 可以在此处找到评论此更改的有趣文章。
所以基本上：
-
即使在不太好的散列函数的情况下，素数也有助于将输入分散到不同的桶中。
-
通过对散列函数的结果进行后处理，并使用2大小的幂来加速模运算（位掩码）并补偿后处理，可以实现类似的效果。
因为这会产生更好的散列函数并减少可能的冲突次数。 选择良好的散列函数中对此进行了解释：
基本要求是该函数应提供散列值的均匀分布。 不均匀分布会增加冲突次数和解决冲突的成本。
对于应用程序中出现的表大小，分布需要是统一的。 特别是，如果使用具有s的精确加倍和减半的动态resize，则仅当s是2的幂时，散列函数才需要是均匀的。 另一方面，只有当s是素数时，一些散列算法才提供均匀的散列。