誰かが私のために誕生日効果を明確にしてくれませんか？

Question

ウィキペディアに記載されているように、誕生日効果を解釈するのを手伝ってください：

誕生日攻撃は次のように機能します：

1. メッセージmを選択し、H（m）を計算します。
2. リストLを更新します。h（m）がリストLにあるかどうかを確認します。
3. （h（m）、m）がすでにlにある場合、衝突するメッセージペアが見つかりました。それ以外の場合、リストLにペア（h（m）、m）を保存し、ステップ1に戻ります。

誕生日のパラドックスから、約2^（n/2）ハッシュ評価を実行した後、マッチングエントリを見つけることが期待できることを知っています。

上記の2^（n/2）の反復は、上記のループ全体（すなわち2^（n/2）がステップ1に戻る）を意味しますか、それともlの既にLの個々のアイテムとの2^（n/2）の比較を意味しますか？

Answer 1

ループを介した2^（n/2）反復を意味します。しかし、それに注意してください L ここでは通常のリストではありませんが、ハッシュテーブルマッピング h(m) に m. 。したがって、各反復には、平均で一定の数（O（1））の比較のみが必要であり、合計でO（2^（n/2））比較があります。

Lが通常の配列またはリンクリストであった場合、各反復リスト全体を検索する必要があるため、比較の数ははるかに大きくなります。ただし、これはこのアルゴリズムを実装するための悪い方法です。