data-structures - ハッシュテーブルの Open Addressing ベースのリニア プローブ メソッドについて混乱していますか?

Question

文字列「temp」のハッシュ関数による配列インデックスが 155 で、位置 155 が事前に占有されていると仮定し、位置 156 が試行されます。場所 156 が利用可能であると仮定すると、このエントリは場所 155 ではなく場所 156 に保存されます。後で、場所 156 にマップされる別の文字列「another_temp」を見つけます。これも、次に利用可能な場所 157 に保存されます。

問題は、後で「another_temp」の場所を知りたい場合、ハッシュ関数が 156 を返したとしても、それが 156 ではなく 157 であることをどのように知ることができるでしょうか?

ありがとう。

Answer 1

ハッシュ コードだけでなく、キーを比較する必要があります。ハッシュテーブルでは、とにかくキーを保存する必要があります（あなたの場合は「temp」と「another_temp」）。ハッシュ値は一意ではないため、ハッシュ値を保存して比較するだけでは十分ではありません。

オープンアドレス指定にはいくつかの問題があります。1 つは、エントリを削除した後はどうすればよいかということです。通常、特別な「削除済み」マーカーを保存します。もう 1 つの問題は、衝突が発生した場合、ハッシュ コードをインクリメントする必要があるかどうかです。詳細については、ウィキペディアを参照してください。