ハッシュテーブル：衝突時に要素数を増やすべきですか？

Question

現在、私のハッシュテーブルは、ハッシュテーブルに挿入されたすべての要素の数をカウントしています。総ハッシュテーブルサイズでこのカウントを使用して、負荷係数を計算し、70％のように達すると再ハッシュします。

挿入された要素がすべてのスロットではなく、空のスロットを埋めるだけでカウントする必要があると思っていました。私が使用している衝突方法は、別々のチェーンです。係数の負荷は増加し続けますが、ハッシュテーブルにたくさんの空のスロットが残っている場合、いくつかの衝突がある場合。

あなたはおそらく、私がそれほど多くの衝突を持っているなら、おそらく私は最高のハッシュ方法を使用していないと考えているでしょう。しかし、それはポイントではありません。私はそこにknowハッシュアルゴリズムの1つを使用しています。サンプルデータで3つをテストし、衝突が少ないものを選択しました。

私の質問はまだ残っています。挿入されたすべての要素をカウントし続ける必要がありますか、それともハッシュテーブルの空のスロットを埋めるものだけですか？

Answer 1

再ハッシュは、衝突の可能性を減らすことを目的としているため、衝突を体系的に無視して、いつ再ハッシュするかを決定することを意図しています。

各エントリにオリジナルのフルハッシュ値を保持している場合（もちろん、衝突はハッシュモジュロによって現在のサイズによって決定されます）、モジュロ操作による衝突のみをカウントした場合に最適です。異なるアイテムの同一の完全なハッシュ値が原因であるため、役立つことは何もできません（「再ハッシュ」しない限り、別のハッシュ関数に切り替えることも意味しますが、それがここでは意味がないようには見えません;-)。

完全なハッシュ値を維持することは、ハッシュ関数を再度実行する必要がないため、安価な再ハッシングも意味します（もちろん、ハッシュ機能がどれだけコストがかかるかによって、どの程度関連性がありますか）。