連鎖ハッシュテーブルをいつ再ハッシュしますか？

Question

連鎖ハッシュテーブルに挿入するとき、いつ再ハッシュしますか？ alpha = 1のときに再ハッシュする方が良いでしょうか？ （アルファ=保存された要素数/ハッシュテーブルのサイズ）

Answer 1

連鎖を使用すると、バケットに設定された数以上の項目が含まれている場合に、通常はサイズを変更する必要があります。たとえば、バケットに最大5個のアイテムを含めることができます。最初に6番目の項目をバケットに挿入するときは、テーブルのサイズを変更します。

また、理想的な数値が10または3になるように決定することもできます。リサイズ時間とリサイズパフォーマンスのバランスをどのように調整するかはあなた次第です。バケットサイズが小さいほど、平均ルックアップが速くなりますが、テーブルのサイズをもっと頻繁に変更する必要があります。バケットサイズを大きくすると、頻繁にサイズを変更する必要はなくなりますが、平均ルックアップ時間は長くなります。

バケットサイズが10の最悪の場合の検索時間は、バケットサイズが2の場合よりも5倍遅くなります。ただし、それでもリストの順次スキャンよりもずっと速くなり、5xあなたが再ハッシュしなければならない回数の削減。アプリケーションの最適なバケットサイズを試す必要があります。

大きなバケットサイズでルックアップ時間を改善するためにできることは、ルックアップ時に、参照されたばかりのアイテムをバケット内のリストの先頭に移動することです。ここでの理論は、いくつかのアイテムが他のアイテムよりも頻繁に参照されるということです。したがって、常に最新の参照アイテムをリストの先頭に移動すると、より速く見つけることができます。この最適化は、項目が一様に参照されていれば、何の効果もありません。

連鎖すると、しばしば負荷率が150％または200％の良好なパフォーマンスが得られます。時にはさらに高い。再ハッシングとは対照的に、負荷率70〜75％ですばやく劣化し始めます。