data-structures - ハッシュテーブルの遅延削除

Question

私の実装では、衝突解決のために線形または2次プロービングを使用したレイジー削除を使用します。挿入の場合、怠惰に削除されたアイテムに遭遇したとき、それを挿入されるアイテムに置き換えます。この方法でそれを行うことの不利な点または不正確さは何ですか（線形または二次または二重ハッシュ衝突解決のいずれかのために）？スペースを節約しませんか？

Answer 1

オープン アドレス ハッシュテーブルの問題は、特にエントリが非常に動的である場合に、時間の経過とともにパフォーマンスが低下することです。

たとえば、単純な線形プローブ リストを考えてみましょう。ハッシュ スロット 1 で 3 つの衝突があった場合、スロット 1、2、3 が使用されます。2 が削除された場合、スロット 3 でアイテムを引き続き見つけることができるように、「以前に使用された」とマークする必要があります。特定の使用パターンでは、線形検索時間がますます増加するポイントまでハッシュテーブルが劣化し、再び有効にするための費用のかかる再ハッシュ。

クローズ アドレス ハッシュテーブルは、多くのアイテムを挿入/削除する場合、時間の経過とともにパフォーマンスがより一定になります。ただし、ポインターをいじる必要があるため、キャッシュフレンドリーではありません。

したがって、ほぼ一定のキーがある場合は、オープン アドレス指定を使用します。それ以外の場合は、クローズ アドレス ハッシュ テーブルを検討してください。

特定の問題については、カッコウハッシュなどの他の概念も調べたい場合があります。