27

線形プローブを使用するハッシュテーブルからエントリを削除する最良の方法は何ですか? これを行う 1 つの方法は、フラグを使用して削除された要素を示すことでしょうか? これより良い方法はありますか？

4

6 に答える 6

36

簡単なテクニックは次のとおりです。

  1. 目的の要素を見つけて削除する
  2. 次のバケットに移動
  3. バケットが空の場合は終了します
  4. バケットがいっぱいの場合は、そのバケット内の要素を削除し、通常の方法でハッシュ テーブルに再度追加します。アイテムは元の場所に追加される可能性があるため、再度追加する前にアイテムを削除する必要があります。
  5. 手順 2 を繰り返します。

この手法では、削除が少し遅くなりますが、テーブルをきれいに保つことができます。

于 2010-12-09T08:18:28.167 に答える
16

オーバーフローの処理方法と、(1) 削除されるアイテムがオーバーフロー スロットにあるかどうか、および (2) 削除されるアイテムを超えるオーバーフロー アイテムがある場合、削除されるアイテムのハッシュ キーがあるかどうかによって異なります。またはおそらく他のハッシュキー。[その double 条件を見落とすことは、削除の実装におけるバグの一般的な原因です。]

衝突がリンクされたリストにオーバーフローした場合、それは非常に簡単です。リストをポップアップするか (空になっている可能性があります)、リンクされたリストの途中または最後からメンバーを削除します。それらは楽しく、特に難しいことではありません。これをさらに効率的にするために、過度のメモリ割り当てと解放を回避するための他の最適化が存在する可能性があります。

線形プロービングの場合、Knuth は、スロットを空、削除済み、または使用中としてマークする方法を用意するのが簡単な方法であると提案しています。削除された占有スロットを削除済みとしてマークして、線形プローブによるオーバーフローがスキップされるようにしますが、挿入が必要な場合は、通過した最初の削除済みスロットを埋めることができます [The Art of Computer Programming, vol.3: Sorting and Searching] 、セクション 6.4 ハッシング、p. 533（ed.2）]。これは、削除がかなりまれであることを前提としています。

Knuth は Algorithm R6.4 [pp. 533-534] 代わりに、セルを削除ではなく空としてマークし、作成されたばかりの穴を別の穴の隣になるまで移動することで、テーブル エントリを最初のプローブ位置に近づける方法を見つけます。

Knuth は、こ​​れにより既存のまだ占有されているスロット エントリが移動され、スロットへのポインタがハッシュ テーブルの外部に保持されている場合は良い考えではないことを警告しています。[スロットにガベージコレクションまたはその他のマネージド参照がある場合は、スロットを移動しても問題ありません。これは、テーブルの外で使用されている参照であり、参照するスロットがどこにあるかは問題ではないためです。同じオブジェクトがテーブルにあります。]

于 2008-11-11T02:06:53.693 に答える
10

Python ハッシュ テーブルの実装 (非常に高速であると言えます) は、ダミー要素を使用して削除をマークします。拡大、縮小、またはテーブル (固定サイズのテーブルを使用していない場合) に合わせて、ダミーを同時にドロップできます。

コピーにアクセスできる場合は、実装に関するBeautiful Codeの記事を参照してください。

于 2008-11-11T00:00:26.367 に答える
3

私が考えることができる最善の一般的な解決策は次のとおりです。

  • 非定数イテレータ (ala C++ STL または Java) を使用できる場合は、遭遇したときにそれらを削除できるはずです。ただし、基になるコレクションが変更された場合に無効になる const イテレータまたは列挙子を使用していない限り、おそらくこの質問をすることはないでしょう。
  • あなたが言ったように、含まれているオブジェクト内で削除済みフラグをマークできます。ただし、これはメモリを解放したり、キーの衝突を減らしたりしないため、最善の解決策ではありません。また、おそらく実際にはそこに属していないクラスにプロパティを追加する必要があります。これが私と同じくらい気になる場合、または単に格納されたオブジェクトにフラグを追加できない場合 (おそらくクラスを制御していない場合)、これらのフラグを別のハッシュ テーブルに格納できます。これは、最も長期間のメモリ使用を必要とします。
  • ハッシュ テーブルをトラバースしながら、削除するアイテムのキーをベクターまたは配列リストにプッシュします。列挙子を解放した後、このセカンダリ リストをループして、ハッシュ テーブルからキーを削除します。削除するアイテムがたくさんある場合や、キーが大きい (そうであってはならない) 場合、これは最善の解決策ではない可能性があります。
  • ハッシュ テーブルに残す項目よりも多くの項目をハッシュ テーブルから削除することになる場合は、新しいハッシュ テーブルを作成し、元のハッシュ テーブルをたどって、新しいハッシュ テーブルに持っておきたいアイテム。次に、古いハッシュ テーブルへの参照を新しいものに置き換えます。これにより、二次的なリストの反復が節約されますが、おそらく新しいハッシュ テーブルの項目が元のハッシュ テーブルよりも大幅に少ない場合にのみ効率的であり、もちろん、元のハッシュ テーブルへのすべての参照を変更できる場合にのみ機能します。
  • ハッシュ テーブルがキーのコレクションへのアクセスを許可している場合、それらを反復処理して、1 回のパスでハッシュ テーブルから項目を削除できる場合があります。
  • ハッシュ テーブルまたはライブラリ内の一部のヘルパーが述語ベースのコレクション修飾子を提供する場合、削除するアイテムを識別するためにラムダ式または関数ポインターを渡すことができる Remove() 関数がある場合があります。
于 2008-11-11T00:22:46.963 に答える
1

時間が重要な場合の一般的な手法は、削除済みアイテムの 2 つ目のテーブルを用意し、時間があるときにメイン テーブルをクリーンアップすることです。検索エンジンでよく使われます。

于 2008-11-20T14:52:01.190 に答える
0

リンクされたリストのようなポインターを含むようにハッシュ テーブルを強化するのはどうですか? 挿入時にバケットがいっぱいの場合は、このバケットから新しいフィールドが格納されているバケットへのポインタを作成します。

ハッシュテーブルから何かを削除するときの解決策は、リンクリストからノードを削除する関数を作成する方法と同じです。

于 2014-09-22T22:29:23.287 に答える