オープンアドレス指定を使用してハッシュテーブルの負荷係数でカウントされた削除されたエントリ

Question

ハッシュテーブルの負荷係数を計算する場合、オープンアドレスアレイの実装を使用して私が使用しています。

numberOfKeysInArray/sizeOfArray

ただし、削除されたエントリをそのようにマークする必要があるため（空のスペースと区別するために）、キーの数にこれらを含めることは理にかなっていることがわかりました。

私の考えでは、エントリを見つけるためにプローブの平均数を推定する限り、削除されたエントリは負荷係数にカウントする必要がありますが、新しいキーを挿入する限りはそうすべきではありません。

適切な計算はどれですか：削除されたキーを含むかどうか。

Answer 1

いいえ、定義上、負荷係数は、要素数とバケットアレイサイズの比率です。例を参照してください ウィキペディア また この講義.

また、負荷係数の延期されたエントリをカウントすることには実際的な問題があります。ほとんどの実装には、最大負荷係数があります。実際に許容される最大値を上回ると、バッキングアレイサイズが増加します。削除されたエントリがより高い負荷係数にカウントされた場合、これにより、ほぼ空いているが、デブリの内容テーブルがほとんど空いていない不必要な配列サイズが増加する可能性があります。