hashtable - オープンアドレス法を使用してハッシュテーブルの負荷率でカウントされる削除されたエントリです

Question

私が使用しているオープンアドレッシング配列の実装でハッシュテーブルの負荷率を計算するとき：

numberOfKeysInArray/sizeOfArray

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

私の考えでは、エントリを見つけるためのプローブの平均数を見積もる場合、削除されたエントリは負荷率にカウントされますが、新しいキーを挿入する場合はカウントされません。

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

Answer 1

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

負荷率で削除されたエントリをカウントすることにも実際的な問題があります。ほとんどの実装には最大負荷率があります。実際に許可されている最大値を超えると、バッキングアレイのサイズが大きくなります。削除されたエントリがより高い負荷率にカウントされる場合、これにより、ほとんど空であるがデブリコンテンツテーブルが多い場合に、不要なアレイサイズが増加する可能性があります。