hash - 计算两个元素散列时没有冲突的概率 h(x)=(x^2+1)mod3

Question

如何计算插入 2 个元素后没有碰撞的概率。答案是 4/9，但我看不出它是 4/9

Answer 1

我不太确定这是一个合适的 SO 问题，但这是我对答案的看法。这绝不是一个合法的数学证明，但它确实有效。

对于您的函数 h(x) = (x^2+1)mod3，让我们放一些样本值。

h(1) = (1+1)mod3 = 2mod3 = 2
h(2) = (4+1)mod3 = 5mod3 = 2
h(3) = (9+1)mod3 = 10mod3 = 1

h(4) = 17mod3 = 2
h(5) = 26mod3 = 2
h(6) = 37mod3 = 1

由于函数的性质（平方和加 1），这种模式将继续存在。

因此，我们有 (2/3) 的机会将函数的输入评估为 2，并且有 (1/3) 的机会评估为 1。

如果我们插入两个元素，我们发生碰撞的概率是两个输入评估为 2 的概率加上两个输入评估为 1 的概率。这是：

(2/3) (2/3) + (1/3) (1/3) = 4/9 + 1/9 = 5/9

因此，任何两个输入不会发生冲突的概率是 1 - (5/9)

或 4/9。

Answer 2

关于为什么该模式成立的一些背景知识，请考虑所有等效类 mod 3，即 { 0, 1, 2 }。

如果x mod 3 = 0那么x^2 mod 3 = (x mod 3)(x mod 3) mod 3 = (0 * 0) mod 3 = 0通过分配等价，那么x^2 + 1 mod 3 = 1

如果x mod 3 = 1那么x^2 mod 3 = (x mod 3)(x mod 3) mod 3 = (1 * 1) mod 3 = 1，那么x^2 + 1 mod 3 = 2

如果x mod 3 = 2那么x^2 mod 3 = (x mod 3)(x mod 3) mod 3 = (2 * 2) mod 3 = 1，那么x^2 + 1 mod 3 = 2

它仍然不是 100% 正式的，而且它是一个用尽的笨拙示例，但它让您了解为什么这种模式适用于自然数并集 { 0 }。我也希望我更熟悉堆栈上的数学格式。假设是时候打元？:)