ハッシュテーブル：公開アドレス指定と要素の削除

Question

ハッシュテーブルでの公開アドレス指定を理解しようとしていますが、私の文献では答えられない質問が1つあります。二次プロービングを使用する場合、このようなハッシュテーブル内の要素の削除に関係します。その後、取り除かれた要素はセンチネル要素に置き換えられます。次に、get（）オペレーションは、それがさらに進む必要があることを認識し、add（）メソッドは見つかった最初のセンチネルを上書きします。しかし、すでにハッシュテーブルにあるが、プロービングパスのセンチネルの背後にあるキーを持つ要素を追加するとどうなりますか？すでにテーブルにある同じキーでインスタンスの値を上書きするのではなく、add（）メソッドは、センチネルを上書きします。そして、ハッシュテーブルに同じキーを持つ複数の要素があります。メモリを消費するだけでなく、ハッシュテーブルから要素を削除すると、最初の要素が削除されるため、要素がテーブル内に見つかる（削除されない）可能性があるため、問題として認識しています。

したがって、センチネル要素を置き換える前に、挿入したい要素のキーの探索パス全体を検索する必要があるようです。私は何か見落としていますか？この問題は実際どのように扱われますか？

Answer 1

しかし、私は、ハッシュテーブルではなく、プロービングパスでセンチネルの後ろにすでに であるキーを持つ要素を追加したい場合はどうなりますか？ インスタンスの値をテーブルにすでにある同じキー で上書きする代わりに、add（）メソッドは のセンチネルを上書きします。

add()後で指摘したように、それは、空の要素を見つけるまで、プロービングパスにおけるセンチネル（複数可）の後にすべての要素をチェックする必要があります。プロービングパスで新しい要素が見つからず、その上にセンチネル要素がある場合は、最初のセンチネルスロットを使用して新しい要素を格納できます。

http://www.algolist.net/Data_structures/Hash_table/Open_addressing（HashMap.java）にハッシュテーブルの実装があります。そのput()メソッドはこれを正確に行います。 （衝突の解決は、参照されたスニペットの線形プロービングですが、アルゴリズムの観点からは重要ではないと思います）。表。これに対する解決策は、（アイテムの数およびセンチネル要素の数に基づいて）時々ハッシュテーブルを再構築する（すなわちすべてを再ハッシュする）ことである。この操作は、センチネル要素を除去する。

もう1つの方法は、要素を削除するときにプロービングパスからセンチネル（DELETED）要素を削除することです。実際には、この場合、テーブルにセンチネル要素はありません。 FREEスロットとOCCUPIEDスロットしかありません。それは高価かもしれません。

だから、1がセンチネル 要素を交換する前に、挿入したい要素の キーの全体のプロービングのパスを探索する必要があるようです。

はい、あります。空の要素が見つかるまで検索する必要があります。

この問題はどのように実際に処理されますか？

実生活のハッシュテーブルの実装についてはあまり気にしません。私はそれらの多くがオープンソースプロジェクトのインターネット上で利用可能であると思います。私はちょうどJavaのHashtableとHashMapクラスをチェックしました。どちらもオープンアドレッシングの代わりに連鎖を使用します。

Answer 2

申し訳ありませんが、Javaは公開アドレス指定のハッシュテーブルの例：java.util.IdentityHashMapを持っています。

また、GNU Trove Projectを使用することもできます。そのマップは、overview pageで説明されているように、すべて公開されているハッシュテーブルを扱っています。