为什么127号（总理）优于128的哈希表？
假设简单的统一散列，那么任何给定的值就像散列到散列的任何一个槽中一样。 为什么使用大小为127而不是128的表格更好？ 我真的不明白2号码的力量有什么问题。 或者它实际上如何改变。
在使用除法的时候，我们通常会避免m（table size）的某些值。 例如，m不应该是2的幂，因为如果m = 2 ^ p，那么h（k）就是k的p个最低位。
假设可能的元素只在1到10000之间，我把表格大小选为128. 127怎么能更好？ 所以128是2 ^ 6（1000000），127是0111111.这个有什么不同？ 所有数字（散列时）仍然是127的k的最低位。 我有什么问题吗？
我正在寻找一些例子，因为我真的不明白为什么这是不好的。 提前感谢！
PS：我知道： 哈希表：为什么大小应该是素数？
所有数字（散列时）仍然是127的k的最低位。
这是错误的（或者我误解了..）。 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的大小）是没有问题的。 但是，使用真实的数据和真正devise非常糟糕的散列函数，您将需要这些高位。
分割方法
“在使用除法的时候，我们通常会避免m（表格大小）的某些值，例如，m不应该是
2的幂，因为如果m =2 p，那么h(k)就是p最低阶k位“。–CLRS
为了理解为什么m = 2 p只使用k最低位，你必须首先理解模哈希函数h(k) = k % m 。
密钥可以用商q和余数r 。
k = nq + r
select商为q = m允许我们简单地将k % m写成上式中的余数：
k % m = r = k - nm, where r < m
因此， k % m等于连续减去总数n次（直到r < m ）为止：
k % m = k - m - m - ... - m, until r < m
让我们尝试哈希关键k = 91与m = 2 4 = 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 % 2 4 = 11只是91的二进制forms，只剩下p=4最低位。
重要的区别：
这特别涉及散列的划分方法 。 事实上，在CLRS中所述的乘法方法是相反的：
乘法方法的一个优点是m值不重要。我们通常select[m]是2的幂，因为我们可以很容易地在大多数计算机上实现这个函数。
尼克是正确的，一般来说，散列表大小并不重要。 然而，在使用双重散列的 开放寻址 （其中探测间隔由另一个散列函数计算）的特殊情况下，质数大小的散列表最好确保所有散列表条目可用于新的元素（如Corkscreewe提到的）
首先，这不是select素数。 对于你的例子，如果你知道你的数据集将在1到10,000的范围内，select127或128将不会有什么区别bc这是一个糟糕的deviseselect。
相反，最好在你的例子中select一个像3967这样的非常大的素数，这样每个数据都有自己唯一的键/值对。 你只是想要最小化碰撞。 为你的例子select127或128将不会有所作为bc所有127/128桶将被统一填充（这是不好的，并且会降低插入和查询运行时间O（1）到O（n）），而不是3967 （这将保持O（1）运行时间）
编辑＃4
“散列函数”的devise有些黑色艺术。 它可能会受到基于散列的数据结构中存储的数据的高度影响，所以关于明智的散列函数的讨论往往会偏离对特定input的讨论。
为什么素数是“首选的”，我们必须考虑一个“对手”的分析，那就是假设我devise了一个基于散列的一般数据结构，考虑到对手的最坏情况，它将如何执行。 由于性能是由散列冲突决定的，所以问题就变成了什么样的散列，在最坏的情况下使冲突最小化。 一个这样的条件是什么时候input总是可以被整数整除的数字，比如4。如果你使用N = 128，那么任何被4模128整除的数字仍然可以被4整除，这意味着只有桶4,8,12。总是被使用，导致25％的数据结构利用率。 素数有效地降低了发生这种情况的可能性，数字> N.
如果你有一个完美的哈希函数，它具有均匀的分布，那么它并不重要。
维基百科其实有一个很好的总结：
http://en.wikipedia.org/wiki/Hash_table
他们指出，一些散列函数被devise为只能用素数运算。 这篇文章解释了为什么两个权力是不好的：
我不能再certificate这一点，虽然我记得在一百万年前的大学考试中必须这样做，但最佳的散列大小不仅仅是素数。 你想select一个素数N ，使得N = 4*M − 1 （其中M也是一个整数）。
这使得31比29更好。当N是31时， M是8，但当N是29时，没有整数M.
正如我所说，我不再记得math来certificate这一点。 乌迪的妻子蕾切尔·曼伯（Rachel Manber）大约在二十五年前就开始了这个理论课。
这里有一个方法来理解“k％127取决于k的所有位，k％128只取决于7个最低位”。 。
例如：129％128 = 1，在二进制：1000 0001＆0111 1111 = 0000 0001，（2 ^ 7-1）的任何高位将是0，这意味着什么高位不重要。 但是这个翻译对于不等于2 ^ n的数字是无效的。
现在让我们来看看我们如何在Decimal 129％127中进行分割，首先看最高位置1，小于127，然后我们得到下一个项目2结合拳头我们得到12,12小于127，然后合并其中9表示129，127除以余数2，我们可以在math中写出：129 = 1 * 127 + 2，所以我们得到2 [所有这些被称为Long_division] ，在二元分割中是一样的，现在，我们知道k％127取决于k的所有位
我相信这只是与计算机工作在基地2的事实有关。类似的情况发生在基地10。
…
select一个足够大的非幂次数将确保散列函数真的是所有input位的函数，而不是它们的一个子集。
从什么哈希表应该使用素数大小 。
