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

Question

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

A birthday attack works as follows:

1. Pick any message m and compute h(m).
2. Update list L. Check if h(m) is in the list L.
3. if (h(m),m) is already in L, a colliding message pair has been found. else save the pair (h(m),m) in the list L and go back to step 1.

From the birthday paradox we know that we can expect to find a matching entry, after performing about 2^(n/2) hash evaluations.

以上是否意味着通过上述整个循环进行 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 是一个普通数组或链表，那么比较的次数会大得多，因为每次迭代都需要搜索整个列表。不过，这将是实现该算法的一种糟糕方式。