ハッシュテーブルの線形プロービングデータ構造

Question

線形プロービングを使用すると、1.1の負荷係数のしきい値をハッシュテーブルに選択できないのはなぜですか？ これはすべての番号で機能するはずですか？

Answer 1

なぜ私はこれを忘れたのか分かりませんが、izaak_pyzaakが私に思い出させることに感謝します。

リニアプロービングを使用している場合は、ではないと仮定して、を作成します。

Arunmuが指摘するように、負荷しきい値が1より大きい場合、チェーンされていないハッシュテーブルはオーバーフローします。これは、少なくともハッシュテーブルを破壊し、プログラムがクラッシュする可能性があります。

ほとんどの場合、ハッシュテーブルは、0.75を超える負荷がパフォーマンスヒットし、テーブルの衝突の量が指数関数的に増加するため、最大負荷係数が0.75に設定されて実装されます。原則として、ほとんどのテーブルは、衝突を減らすために、レコードの意図された量より2〜3倍大きくなければなりません。

負荷係数が1の場合、サイズ変更時にハッシュテーブルが完全に埋められることを意味します。サイズを変更する前に、テーブルのハッシュ/検索の速度が低下します。前述のように、の非連鎖ハッシュテーブルの負荷係数1.1が大きな問題になります。

Answer 2

私は、一部の問題を理解することはできません（またはまったく。）しかし...

あなたは1.1の要素を持つことができないからです。 1つまたは0（または2、3、4 ... n）の要素があります。繰り返しますが、5.5要素を持つこともできません。あなたは5または6を持つことができますが、間にはありません。 1つの要素の後にしきい値を増やす場合は、単にしきい値を1にします。