math - 与通用哈希有关的困惑

Question

我正在阅读这个与通用散列相关的视频讲座。它显示了散列 IP 地址的示例。每个 IP 地址由 4 个 32 位整数 (x1,x2,x3,x4) 组成，其中任何 xi 的最大值为 255。

教程说哈希表的大小应该大于 255 或任何 xis。为什么会这样？

Answer 1

（对于那些还没有看过视频的人，这会在 20:45 左右出现）。

以这种方式定义的函数类是以下形式的函数

h _a (x ₁ , x ₂ , x ₃ , x ₄ ) = a ₁ x ₁ + a ₂ x ₂ + a ₃ x ₃ + a ₄ x ₄ (mod n)

其中 n 是桶的数量，每个 x _i在 0 到 n - 1 的范围内，每个 a _i在 0 到 n - 1 的范围内，并且 n 是素数。

你的问题是为什么所有的 x _i都必须小于 n。原因与证明这个哈希函数家族是通用的有关。正如 Tim 在视频中解释的那样，证明哈希函数是通用的方法之一是考虑两个不同的输入（称为 x 和 y）。这意味着它们必须在某些组件上有所不同，并且我们的想法是在不失一般性的情况下假设它们在第四个组件上有所不同。也就是说，x ₄ ≠ y ₄。通过一些数学计算，在该假设下，您可以证明发生碰撞的概率等于该陈述为真的概率：

a ₄ (x ₄ - y ₄ ) = a ₁ (x ₁ - y ₁ ) + a ₂ (x ₂ - y ₂ ) + a ₃ (x ₃ - y ₃ ) (mod n)

在这里，由于我们随机选择了散列函数，所有的 a _i都是随机的。关键的见解是，如果您将 a ₁、 a ₂和 a ₃视为固定值，则该等式的右侧只是某个固定数字 k。然后，您对以下概率感兴趣

a ₄ (x ₄ - y ₄ ) = k (mod n)

因为我们假设 n > x ₄， n > y ₄， x ₄ ≠ y ₄，并且 n 是素数。这告诉我们两个非常重要的事实：

1. x ₄ - y ₄ ≠ 0 mod n。这是我们需要 n 大于 x _i的主要原因。我们马上就会知道为什么。

2. x ₄ - y ₄与 n 互质。这是为什么？好吧，我们知道 n 是一个素数。由于 n > x ₄和 n > y ₄，我们知道 x ₄ - y ₄必须严格介于 n-1 和 -(n-1) 之间。因为我们假设 n 是素数，所以在该范围内有 n 的非平凡除数，所以 x ₄ - y ₄和 n 互质。

要了解为什么这些事实很重要，让我们考虑 k 的两种情况。首先，k = 0 是可能的。在这种情况下，在什么情况下 a ₄ (x ₄ - y ₄ ) = k (mod n)？由于 x ₄ - y ₄ ≠ 0，我们知道只有当 a ₄ = 0 时才会发生这种情况。由于 a ₄在 0 到 n-1 （含）范围内具有均匀随机值，因此我们在此范围内发生碰撞的概率情况是 1/n。

接下来，假设 k ≠ 0。在这种情况下，必须发生什么才能使₄ (x ₄ - y ₄ ) = k (mod n) 为真？好吧，我们知道 x ₄ - y ₄ ≠ 0，所以它必须有一个乘法逆模 n，因为 x ₄ - y ₄与 n 互质。事实上，它只有一个乘法逆元。唯一可能的选择₄会导致这一点是正确的选择，其中₄是 x ₄ - y ₄模 n 乘以 k 的乘法倒数。在 0 到 n-1 范围内只有一个数字可以选择，所以选择它的概率是 1/n。

请注意，如果 x ₄ - y ₄等于零模 n，则上述推理将不起作用。在第一种情况下，每次选择₄都会导致碰撞，因此碰撞概率为 1。在第二种情况下，没有选择₄会导致碰撞，因此碰撞概率将为 0。这些条件将无效证据。

希望这可以帮助！