为什么哈希表的大小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仍将是k的p个最低位。是我错了吗？

我正在寻找一些例子，因为我真的不理解为什么会有问题。非常感谢你们提前的帮助！

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

- Clash

---

PS: 我知道：哈希表：为什么大小应该是质数？然后再读一遍，或者通过链接阅读此文章（https://dev59.com/7nM_5IYBdhLWcg3w-4Zg#1147232）。

- sehe

@sehe 您链接的线程做出了一个假设，即其中的元素具有关系（“如果一堆具有相同首字符的字符串都被输入，则结果在模k意义下都相同”） - Clash

“Clash” 是一个非常好的屏幕名称，在讨论哈希碰撞时使用 :) - sehe

因为真实数据几乎从不均匀分布。如果您使用128来哈希字符串，您将得到26个桶填充不均匀和其余的空桶。如果您使用127，您可能会得到更均匀地填充它们所有的桶。 - phkahler

只是更正一个笔误：128 是 2^7，而不是 2^6。 - TT_ stands with Russia

Answer 1

所有数字（哈希后）在 127 中仍将是 k 的 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，..}更频繁地出现。那么像这个answer中解释的那样，使用质数大小将会给出更好的分布。（除非x恰好是该质数大小。）

因此，如果低位的分布足够好，那么截断高位（使用大小为128）就没有任何问题。但是，对于真实数据和设计不良的哈希函数，您将需要这些高位。

- Ishtar

---

你是对的Ishtar。但这相当于说128的任何倍数% 128（高位总是128的倍数）将为0，对我来说是显而易见的。另一方面，127没有这个属性，但会有更多的127的倍数，所以这应该更糟糕，不是吗？我不明白忽略高位的问题在哪里。 - Clash

@Clash - 忽略高位的真正问题在于人们编写了糟糕的哈希函数。因此，如果您的表需要良好的分布，忽略那些额外的位就是愚蠢的。制作良好的哈希很难，所以使用质数大小只是宽容而已。 - Ishtar

@Clash：忽略高位的问题在于，对于给定的数据集，只有某些位变化是正常的。（例如，表示路径的一堆字符串变量可能在前十几个字符上达成一致。或者，年龄可能除了最低的6位以外都相同。）如果你要丢弃这些位，那么就会产生很多冲突。 - Neil G

Answer 2

除法散列方法

在使用除法散列方法时，我们通常避免某些特定的m值（表大小）。例如，m不应是2的幂，因为如果m = 2^p，则h(k)只是k的p个最低位。

--CLRS

要理解为什么m = 2^p只使用k的p个最低位，您必须先了解模散列函数h(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

让我们尝试使用 m = 24 = 16 对密钥 k = 91 进行哈希。

  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 = 11 就是用只保留 p=4 最低位的二进制形式表示的 91。

---

重要区别：

这仅适用于哈希的除法方法，事实上，对于乘法方法，正如CLRS所述，相反的情况是真实的：

“乘法方法的一个优点是m的值不关键... 我们通常选择[m]为2的幂次方，因为我们可以很容易地在大多数计算机上实现函数。”

- bcorso

Answer 3

首先，它与选择质数无关。对于您的示例，如果您知道数据集将在1到10,000的范围内，选择127或128不会有任何区别，因为这是一个糟糕的设计选择。

相反，最好选择一个非常大的质数，例如3967，以便每个数据都有自己独特的键/值对。您还希望最小化冲突。对于您的示例选择127或128不会有任何区别，因为所有127/128个桶都将均匀填充（这很糟糕，并且会将插入和查找运行时间从O(1)降至O(n)），而3967则会保持O(1)运行时间。

第四次编辑

“哈希函数”的设计有点黑魔法。它可以受到打算存储在基于哈希的数据结构中的数据的高度影响，因此对于合理的哈希函数的讨论通常可能会偏离具体输入的讨论。

至于为什么质数“更受青睐”，必须考虑“敌手”分析，也就是说，假设我设计了一个通用的基于哈希的数据结构，那么在面对最坏的输入时它会表现如何。由于性能由哈希冲突决定，所以问题变成了使用什么哈希可以在最坏的情况下最小化冲突。其中一种情况是当输入始终是某个整数的倍数时，比如4。如果您使用N = 128，则任何模128可被4整除的数字仍然可被4整除，这意味着只有4、8、12等桶总是被使用，从而导致数据结构的利用率为25%。质数有效地降低了发生这种情况的可能性，尤其是对于大于N的数字。

- Matthew

---

如果我错了，请纠正我，但是3976将在每个桶中具有多个值。 - Nick ODell

@Nick，我认为他读了1000。我知道127和128对于10000来说是不好的。我想要理解的是，为什么选择质数而不是其他任何数字更好？为什么2的幂不好？如果我选择16384（2^14），那么为什么16381更好？谢谢。 - Clash

抱歉，打错了：我是指3967。这与哈希函数的设计有关。目前，如果您假设一个简单的哈希函数，它只接受一个数字（介于1和10,000之间），并将其模除3967，这几乎可以确保我们在表中没有冲突。此外，大质数使我们的表几乎扩大了4倍，并确保碰撞的概率很低。 - Matthew

我不明白为什么127被认为是“小”的，而3967被认为是“真的很大”。最重要的是负载因子。如果您正在存储10个元素，则127完全可以胜任，并且可能会减少缓存未命中率。 - Neil G

@mattkc7，你所说的“二进制是2的幂次方”是什么意思？我认为二进制只是表示数字的另一种进位方式。而且我也不明白使用2的幂次方时哈希值会有一半被截掉的原因是什么。 - Clash

Answer 4

尼克说得对，一般来说哈希表的大小并不重要。但是，在使用“二次哈希”（其中探测间隔由另一个哈希函数计算）的“开放地址法”特殊情况下，最好使用质数大小的哈希表，以确保所有哈希表条目都可用于新元素（正如Corkscreewe所提到的）。

- Neil G

Answer 5

如果您拥有一个具有均匀分布的完美哈希函数，那么它就不重要了。

- Nick ODell

---

如果你不这样做，可能会出现递归冲突，从而使得某个项目无法保存在哈希表中。使用质数大小（或完美的哈希函数）可以避免这种情况发生。 - Corkscreewe

这实际上取决于遇到碰撞时这张桌子会发生什么。 - Nick ODell

我的哈希函数是模运算符。这不是完美的哈希，对吗？实际上，我还没有达到完美的哈希，但从我所读的内容来看，这更多地与没有插入新键有关，元素是静态的。 - Clash

@Neil，我正在尝试理解的是：使用接近2的素数或任何靠近2的幂次方的数字是否比使用2的幂次方更好？另外提一句：据我所知，std库中没有哈希。虽然有std :: map，但我认为它内部作为二叉树运行（可能是我错了）。 - Clash

我看到了你的回答。这本书在这个例子中使用模运算符作为哈希函数，而不是双重哈希。 - Clash

Answer 6

维基百科对此有很好的概述：http://en.wikipedia.org/wiki/Hash_table。他们指出，一些哈希函数只能使用质数。这篇文章解释了为什么二的幂次方不好：http://www.concentric.net/~Ttwang/tech/primehash.htm。请注意，保留HTML标签。

- user236520

Answer 7

虽然我记得在大学考试中不得不这样做，但我无法再证明它了。最优哈希大小不仅仅是质数。您需要选择一个质数N，使得N = 4*M − 1（其中M也是整数）。

这使得31比29更好。当N为31时，M为8，但当N为29时，没有整数M。

正如我所说，我不再记得证明这个问题的数学方法。大约25年前，由Udi的妻子Rachel Manber教授的理论课程中提到过。

- tchrist

Answer 8

我相信这只是因为计算机使用二进制。类似的情况也会在十进制中发生。

选择一个足够大的、非2次幂的数字，可以确保哈希函数真正成为所有输入位的函数，而不仅仅是它们的子集。

来自于为什么哈希表应该使用质数大小。

- Ste_95

Answer 9

这里有一种理解“k % 127取决于k的所有位。k % 128仅取决于最低的7位。”的方法。
k % 128等于k & (2^7-1)。例如：129 % 128 = 1，在二进制中：1000 0001 & 0111 1111 = 0000 0001，(2^7-1)的任何高位都将为0，这意味着高位是什么并不重要。但是，对于不等于2^n的数字，此转换无效。
现在让我们看看如何在十进制中进行除法129 % 127，首先看最高位1，小于127，然后我们得到下一个项目2与第一个组合得到12，12小于127，然后与9组合表示129，除以127余数为2，我们可以用数学写成：129 = 1 * 127 + 2，所以我们得到了2 [所有这些都称为Long_division]，在二进制除法中也是如此，现在，我们知道k % 127取决于k的所有位。

- paxi