2

私は C でデータ構造とアルゴリズムとソフトウェアの原則を読んで、データ構造の内部に頭を悩ませようとしていますが、2 つのことが本当に気になります。

(1) バケット内のアイテムがすべて同じハッシュを持つ場合、検索しているアイテムがバケット内のどのアイテムであるかを決定する際、ハッシュ テーブルはどのように処理しますか?

例えば

  1. キー、値を取得
  2. キーでハッシュアルゴリズムを使用して、値を入れようとするインデックスを見つけます
  3. スロットが使用されているが、バケット (単一のエントリ) がない場合は、バケットを作成し、現在のアイテムをバケットにスローしてから、現在の値をバケットにスローします。
  4. すべてのキーが同じハッシュにマップされ、バケット内のアイテムには検索するキーがないため、どの値がどのキーに属しているかがわからない「紛失および発見の問題」があります。キーによるバケット。

これは、バケットが各エントリのキーと値を保存する場合に機能しますが、ハッシュ テーブルがキーとエントリの値を保存することを確認するサイトが見つからないため、混乱しています。

(2) ハッシュテーブルは、インデックスの値がキーの正しい値であるかどうか、またはプロービングが衝突を検出して別の場所に配置したかどうかをどのように判断しますか。

例えば。

  1. キー、値を取得
  2. index(0) を見つけるためのハッシュ キー
  3. インデックスが取得されたら、スロットが見つかるまで (スロット 1 が空になるまで) 線形検索を実行する単純なプローブ アルゴリズムを使用します。
  4. ここでキーを検索し、インデックス 0 を見つけます。ハッシュは、インデックス 0 がこのキーの正しいアイテムではなく、スロット 1 にプローブされていることをどのように認識しますか?

繰り返しますが、テーブルがキーとエントリの値を保存する場合、これは私には理にかなっていますが、ハッシュがエントリの値とともにキーを保存するのか、それともハッシュ インデックスのアイテムを確実にする別の方法があるのか​​ はわかりませんまたはバケットインデックスが正しい項目であるか、誤解している場合。

質問を明確にするために: ハッシュ テーブルは値と共にキーを保存してバケットとプローブ シーケンスを明確にしますか、それともハッシュのあいまいさを避けるために何か他のものを使用しますか?

大雑把に定式化された質問で申し訳ありませんが、私はただ尋ねなければなりませんでした。

ありがとうございます。

4

1 に答える 1

2

ハッシュ テーブルはエントリを保存します。エントリはキーと値で構成されます。

バケット内のアイテムがすべて同じハッシュを持っている場合、検索しているアイテムがバケット内のどのアイテムであるかをハッシュテーブルはどのように決定しますか?

キーを渡すことでクエリが実行されるためです。

ハッシュの目的は、インデックスを見つける時間を短縮することです。それらのキーはハッシュされて、適切なバケットを見つけます。次に、アイテムが合計 N から非常に小さな n に削減されたら、線形検索を実行して、同じハッシュを持つすべてのキーから適切なアイテムを見つけることもできます。

ハッシュテーブルは、インデックスの値がキーの正しい値であるかどうか、またはプローブが衝突を見つけて別の場所に配置したかどうかをどのように判断しますか?

繰り返しますが、これはハッシュ テーブルが値だけでなくエントリを保存するためです。衝突が発生した場合、ハッシュ テーブルは、このバケットで見つかったキーがクエリされたキーではないことを確認すると、衝突が以前に発生し、キーが次のバケットにある可能性があることを認識します。この場合、バケットが LinkedList またはエントリのツリーを格納する可能性がある最初の回答の場合とは異なり、バケットは単一のエントリを格納することに注意してください。

于 2016-07-16T00:01:25.657 に答える