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

Question

请帮助解释维基百科中描述的生日效果:

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

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 是普通数组或链表，则比较次数会大得多，因为每次迭代都需要搜索整个列表。但这将是实现该算法的一个糟糕方法。