algorithm - 散列中可能的冲突

Question

Ifh是任何散列函数，用于将n键散列到大小为 的表中m，其中n<=m，涉及特定键的预期冲突数x为：

(A) Less than 1
(B) Less than n
(C) Less than m
(D) Less than n/2

我想出的是，它应该小于n但我不确定。

Answer 1

你最好阅读生日悖论。

以下是一些链接：

生日问题

理解生日悖论

并引用第二个链接：

以下是生日悖论的一些教训：

• sqrt(n) 大致是您需要有 50% 的机会与 n 个项目匹配的数字。sqrt(365) 大约是 20。这在密码学中用于生日攻击。
• 即使有 2^128 (1e38) 个 GUID，我们也只有 2^64 (1e19) 个可以在 50% 的碰撞几率之前用完。50% 真的非常高。
• 你只需要 13 个人选择字母表就有 95% 的匹配机会。在上面试试（人 = 13，项目 = 26）。
• 指数增长迅速降低了挑选独特物品的机会（也就是增加了比赛的机会）。请记住：指数是非直觉的，人类是自私的！