ダイナミックパーフェクトハッシュとユニバーサルハッシュ関数 - 説明してください。

Question

私はハッシュテーブル、ハッシュ関数などについて読んでいます。特定のバケット内に複数の値を格納するためにデータ構造として第2のハッシュテーブルを使用する方法については、ウィキペディアで「動的完全ハッシュ」を読む方法に興味を持っていました。

ただし、私が失われるのは、その2番目のハッシュテーブルのハッシュを実行するためにどのように汎用ハッシュ関数が選択されるかということです。バケツに格納されている値からこの汎用ハッシュ関数がどのように決定されるのか誰も説明できますか？私はウィキペディアの「普遍的なハッシュ関数」のページにある推論とロジックを漠然としていますが、直感的に理解しています。特に、これらの機能はどのように衝突を保証しないのですか？それとも、もしそれらが処分され、衝突が検出された場合に新しいものが生成されれば、それは現実的な時間内に行えることをどのようにして知ることができるでしょうか？

レディバードブック説明どうぞ？

Answer 1

完璧なハッシュとは、最悪の場合でも読み取りアクセスに一定の時間がかかることを意味します。

キーを挿入するには、最悪の場合の保証はありません。時間的な境界は平均でのみ真です（または償却されるかもしれません）。

2番目のレベルのハッシュテーブルは、キーの数（k ）に非常に大きく選択されているため、衝突が十分に起こりにくくなります。これは問題ではありません。第1レベルのハッシュはキーを均等に分配するので、平均的な第2レベルのハッシュテーブルは依然として小さくなるからである。

第2レベルテーブルのハッシュ関数は、パラメータ化されたハッシュ関数のセットからランダムに選択されます。

Answer 2

MIT講義はどうですか？ :)
MIT’s Introduction to Algorithms, Lectures 7 and 8: Hashing