我已经在 SO 和网络上阅读了几个关于选择一个好的哈希表长度的答案，并且它应该是减少冲突并在哈希表中均匀分布密钥的首要条件。
虽然有很多答案，但我找不到令人满意的证明，我不明白我找到的解释。
因此，如果我们有一个键k和一个长度为的哈希表，n并且我们确实k % n = i要在哈希表中找到一个存储桶的索引i，我们说它n应该是一个素数，以便最大限度地减少冲突的数量并更好地在整个存储桶中分配键。哈希表。
但为什么？这是我试图证明这一点的尝试。它会很长而且有点迂腐，但请耐心等待，并尝试读到最后。
我将首先做出以下假设：
对于一k组键中的每个键K，我们可以有一个k是偶数或奇数的。键是一个整数，可以是偶数 ( k = 2x) 或奇数 ( k = 2x + 1)。
对于n我们可以选择的每个，n也可以是偶数 ( n = 2y) 或奇数 ( n = 2y + 1)。
如果我们将一个偶数加到另一个偶数上，我们会得到一个偶数 ( 2x + 2y = 2(x + y))。同样，如果我们将一个奇数添加到另一个奇数，我们仍然会得到一个偶数 ( (2x + 1) + (2y + 1) = 2x + 1 + 2y + 1 = 2x + 2y + 2 = 2(x + y + 1))。
如果我们将奇数添加到偶数（与将偶数添加到奇数相同），我们总是得到一个奇数（(2x + 1) + 2y = 2x + 1 + 2y = 2(x + y) + 1）。
首先，让我们尝试考虑使用不是素数n的 an ，所以也许我们会发现这些数字不足以用作哈希表的长度（假设键共享一些模式，例如就像全是偶数或全是奇数）。
让我们假设它n是偶数，即n = 2y。在这种情况下，我们有两种情况：我们的键k可以K是偶数（1.1.）或奇数（1.2.）。
1.1。n = 2y是偶数，键是偶数k = 2x
对于k = 2x和n = 2y，我们有：k % n = 2x % 2y = i。
在这种情况下，我们可以说如果键k和哈希表长度n都是偶数，那么i也将永远是偶数。为什么？因为如果我们通过整数除法取商k // n = 2x // 2y = q，我们会得到一个商q，这样：
k = 2x = (n * q) + i = (2y * q) + i = 2yq + i
因为2yq( 2y * q) 是偶数，为了满足2x = 2yq + i余数i总是偶数，因为2x是偶数 ( even + even = even)。如果i是奇数，我们会得到一个奇数 ( even + odd = odd)，但又2x是偶数。
如果我们选择偶数，这会导致以下问题n：如果我们的所有ks 都是偶数，那么它们将始终以偶数索引结束，这会增加冲突和聚类的数量，因为只有n / 2哈希长度的一半表（仅偶数索引）将被占用。
因此，n如果我们的所有ks 或我们的大多数ks 将是偶数，则使用偶数不是一个好主意。
1.2. n = 2y是偶数，键是奇数k = 2x + 1
对于k = 2x + 1和n = 2y，我们有：k % n = (2x + 1) % 2y = i。同样，在这种情况下，如果我们所有的ks（或它们中的大多数）都是奇数，我们最终会遇到这种情况：
k = 2x + 1 = (n * q) + i = (2y * q) + i = 2yq + i
因为2yq是偶数，为了得到一个奇数k = 2x + 1，i总是会是奇数 ( even + odd = odd)。
n同样，即使我们的所有或大部分s 都是奇数，选择偶数作为哈希表长度也是一个坏主意k，因为我们最终只会占用奇数索引（存储桶）。
因此，让我们尝试使用n不是偶数的，即奇数n = 2y + 1。
让我们假设这n是奇怪的，即n = 2y + 1。我们仍然有偶数 ( 2.1. ) 和奇数 ( 2.2. ) 键 ( kof K)。
2.1。n = 2y + 1是奇数，键是偶数k = 2x
在这里，我们有：
k = 2x = (n * q) + i = ((2y + 1) * q) + i = (2yq + q) + i = 2yq + q + i
我们知道那2yq是偶数，所以为了得到k = 2x它是偶数，我们q + i也需要是偶数。什么时候可以q + i平？仅在这两种情况下：
q -> even, i -> even,even + even = even
q -> odd, i -> odd,odd + odd = even
如果其中一个qori是偶数，而另一个是奇数，我们将得到一个奇数q + i，因此得到一个奇数2yq + (q + i)，但我们有k = 2x一个偶数，所以要么两者都是偶数q，i要么它们都是奇数。
在这种情况下，我们可以看到，对于一个奇数n = 2y + 1，i可以是偶数或奇数，这很好，因为这意味着现在我们将使用哈希表的偶数和奇数桶索引，而不仅仅是偶数或奇数。
顺便说一句，事实证明所有素数p : p > 2都是奇数，所以至少现在我们可以说选择素数可能是一个好主意，因为大于 2 的素数总是奇数。
2.2. n = 2y + 1是奇数，键是奇数k = 2x + 1
同样在这里：
k = 2x + 1 = (n * q) + i = ((2y + 1) * q) + i = 2yq + q + i = 2yq + (q + i)
为了得到奇数k = 2x + 1，我们需要(q + i)奇数（2yq是偶数），这仅在以下两种情况下发生：
q -> even, i -> odd,even + odd = odd
q -> odd, i -> even,odd + even = odd
同样，我们证明奇数是更好的选择，n因为这样我们就有机会同时i占用偶数和奇数桶的索引。
现在，我被困在这里了。这个证明和素数之间是否有联系，我如何继续这个证明来得出结论，素数p比具有类似推理的通用奇数更好的选择？
编辑：
所以我试着进一步推理一下。这就是我想出的：
3.使用一个通用的奇数n共享一个公因数fk
我们可以说，对于在( ) 和( )f之间共享的任何因子，我们最终都会得到一个也共享该公共因子 的因子。为什么？kk = f * x = fxnn = f * y = fyi = k % nf
同样，如果我们尝试计算k：
k = fx = (n * q) + i = (fy * q) + i = fyq + i
然后：
k = fx = fyq + i
仅当且仅当i也共享f作为其因素之一时才能满足，例如i = f * g = fg：
k = fx = fyq + fg = f(yq + g)
导致yq + g = x.
这意味着如果两者k和n共享一个公因数，那么模的结果i也将具有该公因数，因此i将始终是该公因数的倍数，例如对于k和K = {12, 15, 33, 96, 165, 336}（n = 9奇数，不是素数）：
k | k % n
---------------------------
12 | 12 % 9 = 3
15 | 15 % 9 = 6
33 | 33 % 9 = 6
96 | 96 % 9 = 6
165 | 165 % 9 = 3
336 | 336 % 9 = 3
两者k并且n总是共享一个共同的因素（3在这种情况下）。这也导致i = k % n成为 的倍数，3因此，在这种情况下，所使用的哈希表的桶索引也只会是 common factor 的倍数3。
因此，虽然 的奇数n肯定比偶数好（如2.1.和2.2中所解释的），但当两者共享一个公因数时k，我们仍然可能在数字中有不想要的模式。nf
所以，如果我们做n一个素数 ( n = p)，我们肯定会避免它与(假设)n共享那个公因数，因为素数只能有两个因数：1 和它自己。所以...fkf != pp
4. 使用素数n
如果n是素数 ( n = p)，我们最终得到：
k = fx = (q * p) + i = qp + i
然后：
k = fx = qp + i
意味着q整数除法得到的商k // n可以共享f或不共享公因数，即：
q = fz
或者：
q = z
在第一种情况下 ( q = fz) 我们有：
k = fx = (q * p) + i = (fz * p) + i = fzp + i
所以i最终也分享了共同因素f，例如i = fg：
k = fx = (q * p) + i = (fz * p) + i = fzp + i = fzp + fg = f(zp + g)
这样zp + g = x。
在第二种情况下（q = z），我们有：
k = fx = (q * p) + i = (z * p) + i = zp + i = zp + i
即在第二种情况下，i不会有f它的因素之一，因为它的因素也zp没有f。
因此，当使用素数 forn时，好处是结果 fori = k % n可以共享一个公因数f，也可以完全不共享它，k例如 fork和：K = {56, 64, 72, 80, 88, 96}n = p = 17
k | k % n
---------------------------
56 | 56 % 17 = 5
64 | 64 % 17 = 13
72 | 72 % 17 = 4 ---> Common factor f = 4 of k and i
80 | 80 % 17 = 12 ---> Common factor f = 4 of k and i
88 | 88 % 17 = 3
96 | 96 % 17 = 11
在这种情况下，所有ks 共享一个公因数f = 4，但只有i = 72 % 17 = 4和i = 80 % 17 = 12都拥有k并i共享该公因数f：
72 % 17 = 4 -> (18 * 4) % 17 = (4 * 1)
80 % 17 = 12 -> (20 * 4) % 17 = (4 * 3)
此外，如果我们采用前面的例子，for kofK = {12, 15, 33, 96, 165, 336}并且我们使用素数17forn而不是9，我们得到：
k | k % n
---------------------------
12 | 12 % 17 = 12
15 | 15 % 17 = 15
33 | 33 % 17 = 16
96 | 96 % 17 = 11
165 | 165 % 17 = 12
336 | 336 % 17 = 13
即使在这里，我们也看到f = 3这种情况下的共同因素是两者之间共享的，k并且n仅在以下 3 种情况下：
12 % 17 = 12 -> (4 * 3) % 17 = (4 * 3)
15 % 17 = 15 -> (5 * 3) % 17 = (5 * 3)
165 % 17 = 12 -> (55 * 3) % 17 = (4 * 3)
这样，使用素数，发生冲突的概率降低了，我们可以更好地在哈希表中分布数据。
现在，如果 evenk是素数，或者至少是素数的倍数，会发生什么？k我认为在这种情况下，沿着哈希表的分布会更好，因为n如果它们都是素数或者是素数的倍数，则不会有任何公因数k，前提是k它不是素数n。
这就是我的结论为什么素数更适合哈希表的长度。
希望收到您对我理解该主题的方式的反馈和想法。
谢谢你。