为什么将HashTable的长度设置为质数是一个好的做法？

在使用HashTable时，我们需要将元素的键通过哈希函数映射为一个整数值，并将该整数值作为索引来存储和访问元素。而HashTable的长度决定了哈希函数的取值范围，也决定了哈希表的大小。在设置HashTable的长度时，将其设置为一个质数是一个好的做法，下面将解释原因以及解决方法。

首先，如果将HashTable的长度设置为2的幂次方，可以加快模运算的计算速度。但是，这也意味着哈希桶的选择仅由哈希码的前m位决定，其中m = 32 - n，其中n是使用的2的幂次方。这就像是立即丢弃了哈希码的有用位。

其次，在2006年的一篇博客文章中提到了另一个原因。如果哈希函数的哈希码值为{x, 2x, 3x, 4x, 5x, 6x...}，则这些哈希码值将会聚集在仅有m个哈希桶中，其中m = table_length / GreatestCommonFactor(table_length, x)。为了避免聚集，可以采取以下方法之一：

- 使GreatestCommonFactor(table_length, x)等于1，即使m等于table_length。如果x可以是任意数，则确保table_length是一个质数。

将HashTable的长度设置为质数可以避免聚集和丢弃有用位的问题。通过选择质数作为HashTable的长度，可以更好地分散元素在哈希表中的分布，提高哈希表的性能。

最后，对于问题中提到的疑惑，如果将HashTable的长度设置为128，那么hash%128将等同于hash&127，这意味着只有最后7位将决定桶的选择。所以，理解是正确的。

参考链接：

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

为什么将HashTable的长度设置为质数是一个好的做法？

在选择哈希表的大小时，有人建议两个完全相反的观点。一方面，选择一个质数作为哈希表的大小，即使哈希函数在分布结果上不太有效，也可以减少碰撞的几率。需要注意的是，如果选择了2的幂作为哈希表的大小（这是最简单的例子），只有较低的位影响到哈希桶，而选择质数作为哈希表的大小，哈希结果的大多数位都会被使用。

另一方面，通过选择更好的哈希函数，甚至通过应用一些位操作来重新计算哈希函数的结果，并使用2的幂作为哈希表的大小，可以获得更多的好处，以加快计算速度。

以Java中的HashTable为例，最初使用了质数（或接近质数的大小）来实现，但从Java 1.4开始，设计被改为使用2的幂作为桶的数量，并在初始哈希的结果上应用了第二个快速哈希函数。关于这种改变的有趣文章可以在此处找到。

所以基本上：

• 质数有助于在哈希函数不太好的情况下将输入分散到不同的桶中。
• 通过后处理哈希函数的结果，并使用2的幂作为哈希表的大小来加速模运算（位掩码）和补偿后处理的效果，可以达到类似的效果。

不会失去哈希值的数量，因为哈希表的长度仍然可以是任意正整数。但将哈希表的长度设置为质数是一个好的做法的原因是，这样可以减少哈希冲突的可能性。

哈希冲突是指不同的键值对被映射到了相同的哈希桶中。如果哈希表的长度是一个合数（除了1和自身还有其他因数的数），那么某些哈希函数可能会导致不均匀的哈希分布，从而增加哈希冲突的数量。而将哈希表的长度设置为质数，可以使得哈希函数在一定范围内提供均匀分布的哈希值，从而减少哈希冲突的数量。

具体来说，在哈希表的长度s是质数的情况下，一些哈希算法可以提供均匀的哈希值。而如果使用动态调整哈希表大小的方法，比如精确地将哈希表的长度s倍增和减半，那么哈希函数只需要在s是2的幂次方时提供均匀的哈希值即可。但是，一些哈希算法只有在s是质数时才能提供均匀的哈希值。

因此，将哈希表的长度设置为质数是一个好的做法，可以提供更好的哈希函数，减少哈希冲突的数量，提高哈希表的性能。