algorithm - 为什么哈希表的大小 127(素数)比 128 好？

Question

假设简单的统一哈希，即任何给定的值都等同地散列到哈希的任何槽中。为什么使用大小为 127 而不是 128 的表更好？我真的不明白2个数的幂有什么问题。或者它实际上是如何产生任何影响的。

When using the division method, we usually avoid certain values of m (table size). 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.

假设可能的元素仅在 1 到 10000 之间，我选择的表格大小为 128。127 怎么可能更好？所以 128 是 2^6 (1000000) 而 127 是 0111111。这有什么区别呢？对于 127，所有数字(经过哈希处理后)仍将是 k 的 p 个最低位。我是不是弄错了什么？

我正在寻找一些例子，因为我真的不明白为什么这么糟糕。非常感谢!

PS:我知道: Hash table: why size should be prime?

Answer 1

All numbers (when hashed) are still going to be the p lowest-order bits of k for 127 too.

那是错误的(或者我误解了..)。 k % 127 取决于 k 的所有位。 k % 128 仅取决于最低 7 位。

---

编辑:

如果您有 1 到 10,000 之间的完美分布。 10,000 % 127 和 10,000 % 128 都将把它变成一个非常小的分布。所有桶将包含 10,000/128 = 78(或 79)项。

如果您有一个介于 1 和 10,000 之间的有偏分布，因为 {x, 2x, 3x, ..} 出现的频率更高。然后一个基本尺寸将提供更好的分布，如本 answer 中所解释的那样。 . (除非 x 恰好是素数大小。)

因此，如果低位的分布足够好，那么切断高位(使用大小为 128)是没有问题的。但是，对于真实数据和设计糟糕的散列函数，您将需要那些高位。