hashmap - ハッシュマップとプロービング-AVAILABLEとnull？

Question

AVAILABLE線形プロービングには、アイテムが削除されたときに置き換えられるという特別な値があります。

そして、キーを挿入するときに、空のセル（これは単にセルがnull？）またはを含むセルを探します。AVAILABLE私が理解していないのは、空のセルnullが特別な値を持つのではなく、AVAILABLE単にセルnull？

使用することに対する利点は何AVAILABLEですか？

Answer 1

クローズドハッシュ（オープンアドレッシング）では、値は次のように検索されます。

1. キーハッシュを計算し、そこから「完璧な」バケットを決定します。
2. バケットが占有されていて、検索したものと等しいキーがある場合は、値を返します。
3. バケットが占有されていない場合は、ルックアップを中止して失敗します。
4. 次のバケットに移動し（線形プロービングではバケットインデックスをインクリメントするだけです）、ステップ2に進みます。

ここで、バケット5で検索を開始し、バケット8でのみキーを見つけたとします。消去手順でバケット6が未使用としてマークされている場合、手順3のためにバケット8に到達することはありません。したがって、次のような特別な値が必要です。バケットを「占有済み」としてマークしますが、まだ挿入可能です。これはおそらく、あなたの情報源がAVAILABLE、そしてnullまったく空いていると言っているものです。

編集：ところで、線形プロービングを使用すると、この特別な値なしで（かなり）効率的に逃げることができますAVAILABLEが、それは消去をかなり複雑にします。