hashtable - ハッシュ テーブル: 衝突の要素数を増やす必要がありますか?

Question

現在、私のハッシュテーブルは、ハッシュテーブルに挿入されたすべての要素の数を数えています。このカウントとハッシュ テーブルの合計サイズを使用して負荷率を計算し、70% 程度に達したら再ハッシュします。

挿入された要素をすべてではなく、空のスロットを埋めるだけでカウントする必要があるのではないかと考えていました。私が使用している衝突方法は、個別の連鎖です。要素の負荷は増加し続けますが、いくつかの衝突が発生する可能性がある場合は、ハッシュ テーブルに多くの空のスロットが残ります。

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

私の疑問はまだ残っています。挿入されたすべての要素を数え続けるべきですか、それともハッシュ テーブルの空のスロットを埋める要素だけを数えるべきですか?

Answer 1

再ハッシュは衝突の可能性を減らすことを目的としているため、衝突を体系的に無視して、いつ再ハッシュするかを決定することは自滅的であるように思われます。

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

完全なハッシュ値を保持することは、ハッシュ関数を再度実行する必要がないため、再ハッシュが安価になることも意味します（もちろん、ハッシュ関数の計算コストによって異なります）。