hash - Hashing : 削除されたスロットへの挿入

Question

私はハッシュが初めてで、ここに私の質問があります：

ハッシュ テーブルの DELETED スロットに挿入できますか?

Answer 1

はい、削除されたスロットに挿入できます。しかし...

まず、ソフト削除とハード削除があることを知っておく必要があります。ソフト削除では、フラグを反転してスロットを「削除済み」としてマークするだけです。ハード削除では、スロットを空にします。

ソフト削除が必要な理由を説明しましょう。たとえば、線形プローブでハッシュ テーブルを使用していて、ハッシュ関数が 3 つの入力値を同じスロットにマップするとします。リニア プロービングを使用すると、空のスロットが見つかるまでテーブル上を直線的に進み、これら 3 つの要素を配置します。この場合、削除に物理削除を使用すると、値を取得しようとしている間に空のスロットが存在するため、ハッシュ テーブルが壊れてしまい、1 つの値に到達できなくなります。

一方で; 完全なハッシュ関数がある場合は、ハード削除を使用しても問題ありません。完全なハッシュ関数は、すべての入力値をスロットに一意にマップします。したがって、調査スキームは必要なく、ハード削除によってテーブルが壊れることはありません。

質問に戻って、重複挿入を回避する方法も検討して把握する必要があります。