出于性能原因，是否总是需要将哈希表的桶数设置为素数？

Question

https://www.quora.com/Why-should-the-size-of-a-hash-table-be-a-prime-number?share=1

我看到有人提到哈希表的桶数最好是素数。

总是这样吗？当哈希值已经均匀分布时，就不需要使用素数了吗？

https://github.com/rui314/chibicc/blob/main/hashmap.c

例如，上面的哈希表代码没有使用素数作为桶的数量。

https://github.com/rui314/chibicc/blob/main/hashmap.c#L37

但哈希值是使用fnv_hash.

https://github.com/rui314/chibicc/blob/main/hashmap.c#L17

那么，为什么使用不一定是素数的存储桶大小是有意义的呢？

Answer 1

答案是“通常您不需要大小为素数的表，但由于一些实现原因您可能想要这样做。”

从根本上来说，当哈希码尽可能接近均匀地随机分布时，哈希表的工作效果最好。这可以防止项目聚集在表中的任何一个位置。在某种程度上，只要您有足够好的哈希函数来实现这一点，表的大小并不重要。

那么为什么人们说要选择尺寸为素数的桌子呢？造成这种情况的主要原因有两个，它们是由于并非所有哈希表中都出现的特定情况造成的。

有时您会看到素数大小的表，原因之一是构建哈希函数的特定方法。您可以通过选择 h(x) = (ax + b) mod p 形式的函数来构建合理的哈希函数，其中 a 是 {1, 2, ..., p-1} 中的数字，b 是 {1, 2, ..., p-1} 中的数字{0, 1, 2, ..., p-1}，假设 p 是素数。如果 p 不是素数，则这种形式的哈希函数不会均匀地分散项目。因此，如果您使用像这样的哈希函数，那么选择大小为素数的表是有意义的。

您看到有关素数大小表的建议的第二个原因是您是否使用开放寻址策略（例如二次探测或双重哈希）。这些散列策略通过将项目散列到某个初始位置 k 来工作。如果该槽已满，我们查看槽 (k + r) mod T，其中 T 是表大小，r 是某个偏移量。如果该槽已满，我们然后检查 (k + 2r) mod T，然后检查 (k + 3r) mod T，依此类推。如果表大小是素数并且 r 不为零，则这具有很好的、理想的属性这些索引将循环遍历表中的所有不同位置，而不会重复，从而确保项目在表中很好地分布。对于非素数表大小，此策略可能会在少量插槽中循环卡住，这会降低位置的灵活性，并可能导致插入在表填满之前失败。

因此，假设您没有使用双重哈希或二次探测，并且假设您有足够强大的哈希函数，请随意调整表的大小。