hash - 有人可以为我澄清生日效应吗？

Question

请帮助解释 Wikipedia 中描述的生日效果：

生日攻击的工作原理如下：

1. 选择任何消息 m 并计算 h(m)。
2. 更新列表 L。检查 h(m) 是否在列表 L 中。
3. 如果 (h(m),m) 已经在 L 中，则发现有冲突消息对。否则将 (h(m),m) 对保存在列表 L 中并返回步骤 1。

从生日悖论我们知道，在执行大约 2^(n/2) 次哈希评估之后，我们可以期望找到匹配的条目。

以上是否意味着通过上述整个循环进行 2^(n/2) 次迭代（即 2^(n/2) 返回到步骤 1），或者是否意味着与 L 中已经存在的单个项目进行 2^(n/2) 次比较?

Answer 1

这意味着通过循环进行 2^(n/2) 次迭代。但请注意，L这里不是普通列表，而是映射h(m)到m. 因此，每次迭代平均只需要一个常数 (O(1)) 次比较，总共会有 O(2^(n/2)) 次比较。

如果 L 是一个普通数组或链表，那么比较次数会大得多，因为每次迭代都需要搜索整个列表。不过，这将是实现此算法的一种不好的方法。