「アルゴリズム入門」を読んでいます。ユニバーサルハッシュがハッシュ関数のコレクションから新しいものを選択して次のマッピングを行うかどうか疑問に思っていました. たとえば、空のテーブルと一連の操作 [挿入、挿入、検索、削除、挿入、...] が与えられた場合、最初に、アルゴリズムはコレクションから関数を選択し、最初の操作である挿入を実行します。次に、アルゴリズムは新しいハッシュ関数を選択して 2 番目の操作を行うか、挿入するか、アルゴリズムの最初に選択した関数を使用しますか? 前もって感謝します！
質問する
477 次
1 に答える
2
いいえ、挿入された要素ごとにハッシュ関数が個別に選択されるわけではありません。そうであれば、誰かが「要素fooはハッシュ テーブルに存在しますか」と尋ねた場合に、どのハッシュ関数を使用するかを知る方法が必要になりますか? これは、可能な入力とハッシュ関数の間でランダム化された 1 対 1 のマッピングを維持できない可能性があるため、必然的に決定論的アルゴリズムで行われます。つまり、攻撃者はこのアルゴリズムの知識を利用して、最終的に衝突を引き起こす入力を選択し、ユニバーサル ハッシュの利点を事実上台無しにする可能性があります。
したがって、ハッシュ関数は、ハッシュテーブルを初期化するときにユニバーサルファミリから選択され、再ハッシュが発生するたびに変更することができますが (必須ではありません)、単一の要素を追加または挿入した後は変更できません。
于 2013-08-13T09:48:19.733 に答える