为什么散列表的大小127(素数)优于128？

Question

假设简单的统一散列,即任何给定值同样地散列到散列的任何槽中.为什么使用大小为127而不是128的表更好？我真的不明白2号码的力量有什么问题.或者它实际上如何产生任何差异.

使用除法时,我们通常会避免使用某些m值(表大小).例如,m不应该是2的幂,因为如果m = 2 ^ p,则h(k)只是k的p个最低位.

假设可能的元素只在1和10000之间,我选择表格大小为128. 127如何才能更好？所以128是2 ^ 6(1000000),127是0111111.这有什么区别？所有数字(当经过哈希处理时)仍然是127的p的最低位数.我弄错了吗？

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

PS:我知道: 哈希表:为什么大小应该是素数？

Answer 1

所有数字(当经过哈希处理时)仍然是127的p的最低位数.

那是错的(或者我被误解了......).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,..}会更频繁地出现.然后,如本答案中所解释的那样,素数大小将给出更好,更好的分布.(除非x正好是最大尺寸.)

因此,如果较低位的分布足够好,则切断高位(使用128的大小)是没有问题的.但是,对于真实数据和真正设计糟糕的哈希函数,您将需要那些高位.

Answer 2

分工方法

"当使用除法时,我们通常会避免使用m的某些值(表大小).例如,m不应该是幂的幂2,因为如果m = ,那么它只是最低位的."2ph(k)pk

--CLRS

要理解为什么只使用最低位,必须先了解模数散列函数.m = 2ppkh(k) = k % m

密钥可以用商q和余数来表示r.

k = nq + r

选择商可以q = m让我们k % m简单地写成上面等式中的余数:

k % m = r = k - nm,  where r < m

因此,k % m相当于连续减去m总n次数(直到r < m):

k % m = k - m - m - ... - m,  until r < m

让我们试着散列键k = 91用.m = 24 = 16

  91 = 0101 1011
- 16 = 0001 0000
----------------
  75 = 0100 1011
- 16 = 0001 0000
----------------
  59 = 0011 1011
- 16 = 0001 0000
----------------
  43 = 0010 1011
- 16 = 0001 0000
----------------
  27 = 0001 1011
- 16 = 0001 0000
----------------
  11 = 0000 1011

因此,仅仅是二进制形式仅与最低位剩余.91 % 24 = 1191p=4

重要区别:

这特别涉及散列的划分方法.事实上,与CLRS中所述的乘法方法相反:

"乘法方法的一个优点是m的值并不重要......我们通常选择[m]为2的幂,因为我们可以在大多数计算机上轻松实现该功能."