2

ハッシュテーブルの基本: - 主要なテストが近づいています。すべてのヘルプが高く評価されます。

基本的に、キーの均一なハッシュについて少し混乱しています。

----------------------
| X X X                    <=== Chains; X represents an item in there
----------------------
| X X X                    <=== Multiple X represents collisions
---------------------- 
| 
----------------------
| X X X
----------------------
| X
----------------------

  1. M = 5 (行数) で全長が 10 である上記のハッシュ テーブルの場合を考えてみます。

  2. キーのセットの均一なハッシュを作成する場合、それはハッシュテーブル内のチェーン内のリスト、つまり衝突によるリンクリストが同じ長さであることを意味しますか? それとも平均という意味ですか？

  3. キーの均一なハッシュ化を行う場合、このハッシュテーブルの検索関数と削除関数は O(1) (償却) であり、M はチェーンの合計数である O(n/M) の純粋な複雑さを意味しますか?

  4. 負荷係数または (N/#ofChains) はハッシュの均一性を識別しますか?

これらの質問についてお役に立てれば幸いです。私の教授はクラスで多くの概念を発表しましたが、私は基本的にそれらをここでまとめているだけで、これらの概念をまとめると混乱します.

この概念についてもっと勉強するために Web で検索していたところ、以下に示すような一連のスライドを見つけました。2 番目のスライドで、キーの均一なハッシュに関連して式が何を意味するかを説明していただければ幸いです。

また、「各スロットにマップされるキーの数が等しい」とはどういう意味ですか? 上に示されている私のハッシュテーブルは一様にハッシュされていないと言いますか?

ここに画像の説明を入力

ありがとうございました

4

1 に答える 1

4

スライドは、キーのすべての可能な値について話しています。ハッシュマップには、常にキーのサブセットしかないことを認識することが重要です。ハッシュ関数がどれほど優れていても、それらのキーをバケットにマッピングする方法が幸運である場合もあれば、そうでない場合もあります。

1) M = 5 (行数) で、全長が 10 である上記のハッシュ テーブルの場合を考えてみます。

一様ハッシュは、ハッシュ テーブルではなく、ハッシュ関数のプロパティです。したがって、ハッシュ テーブルの内容を見るだけではわかりません。ハッシュ関数自体を調べて、均一かどうかを確認する必要があります。

2) 一連のキーを一様にハッシュ化する場合、それはハッシュテーブル内のチェーン内のリスト、つまり衝突によるリンク リストが同じ長さであることを意味しますか? それとも平均という意味ですか？

平均的にという意味です。

3) キーの均一なハッシュ化を行う場合、このハッシュテーブルの検索関数と削除関数は O(1) (償却) であり、M はチェーンの合計数である O(n/M) の純粋な複雑さを意味しますか? .

ハッシュ関数の特性に加えて、複雑さは負荷要因にも依存します。バケットの数が要素の数に比例して増加する場合、O(1)平均して検索と削除が行われます (再バケットを適切に償却する限り)。

于 2012-12-12T11:14:42.263 に答える