有人可以澄清我的生日效果吗？

Question

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

生日攻击作品如下：

1. 选择任何消息M并计算H（M）。
2. 更新列表L.检查H（M）是否在列表中。
3. 如果（H（M），M）已经在L中，则发现了一对碰撞消息对。否则将对（h（m），m）保存在列表L中，然后返回步骤1。

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

上述平均2^（n/2）通过上述整个环（即2^（n/2）返回步骤1）的迭代，还是表示2^（n/2）比较与L中的单个项目？

Answer 1

它意味着通过循环进行2^（n/2）迭代。但是请注意 L 这里不会是普通列表，而是哈希表映射 h(m) 到 m. 。因此，每次迭代只需要平均比较的恒定数（O（1）），并且总共需要O（2^（n/2））比较。

如果L是普通数组或链接列表，那么比较数将大得多，因为您需要搜索每次迭代的整个列表。但是，这将是实施该算法的不好方法。