ハッシュバケットの数

Question

ハッシュテーブル（またはハッシュテーブル上に構築された他のデータ構造）がいっぱいになっていることに気付いた場合、どの時点でより多くのバケットを持つ新しいテーブルを構築する必要があります。そして、これまでの表にn個のアイテムがある場合、新しいバケットで使用するバケットの数をどのように把握しますか？

つまり、100個のバケットがあるとします。 50個のアイテムがある場合、再編成する必要がありますか？ 500？ 5000？または、その上で最もいっぱいのバケットとキーを探す必要がありますか？次に、そのポイントに達したら、新しいハッシュテーブルをどのくらい作成しますか？

これに関連して、入るアイテムのおおよその数が事前にわかっている場合、バケットの数を計算して平均パフォーマンスを良好にする方法はありますか？

実際の答えは、特定の例で速度とサイズの重要性など、他の多くの考慮事項に依存することはわかっていますが、一般的なギルドラインを探しています。

また、プロファイリングでこれがボトルネックであることが示されない限り、この種のことを最適化すべきではないことも知っています。ハッシュテーブルを大量に使用するプロジェクトについて考えているだけで、これにどのようにアプローチするのか疑問に思いました。

Answer 1

おおまかな目安（常に理想的であるとは限りません）は、ハッシュテーブルが80％まで満たされた場合に再ハッシュすることです。つまり、100個のバケットと80個のアイテムが内部にある場合、以前の衝突の回数に関係なく、キャパシティを増やす時間が取れます。

どのくらい増やす必要がありますか？まあ、完璧な価値もありません。最も簡単な解決策は、増加するたびに容量を2倍にすることです。したがって、200、400、800などになります。これが多すぎると思う場合（ハッシュテーブルが非常に大きくなると8 MBのメモリから16 MBにジャンプするので、16 MBがいっぱいになることはありません）、より小さい成長因子を選択してください。少なくとも1/3を推奨します（100から133に増やします）。妥協案として毎回50％成長させてください。

これらはすべて、衝突の処理方法にも依存することに注意してください。それらを処理する簡単な方法（私の個人的なお気に入り）は、衝突が発生したときにアイテムをリンクリストに保存することです。 3つのアイテムが同じキーに配置されている場合、それを見つけるための比較は最大3つしかありません。リンクリストは検索には非常に効果がないため、容量を早く増やすことをお勧めします。ハッシュテーブルを高速に保つために60％の容量が使用される場合。 OTOH、あなたはもっと洗練された何かをすることができ、衝突の数に関する統計を保持します。衝突がほとんどない限り（非常に優れたハッシュ関数がある場合）、その容量の99％が使用中である場合でも、再ハッシュする必要はまったくありません。また、洗練された方法で衝突を処理する場合（たとえば、各ノードが再びソートされたテーブルであり、これらの中でバイナリ検索を実行できます）、テーブルが200％にロードされている場合、ルックアップは十分に高速になる可能性があります（したがって、2倍のアイテムがあります）容量として）。その場合、ソートされた最大のテーブルの大きさを保持し、8エントリよりも大きくなったときに、これが遅すぎると思うので、再ハッシュします。

再ハッシュは非常に遅いため、できる限り頻繁に回避する必要があります。したがって、再ハッシュが必要な場合は、容量を小さくしすぎないようにしてください。そうしないと、アイテムを追加するときにすぐに再ハッシュする必要があります。そのため、再ハッシュする必要がある場合、現在のテーブルにあるアイテムの数よりも容量を大幅に大きくします。それ以外の容量はすべて小さすぎます。

Answer 2

一般に、<！>＃945; <！> nbsp; = <！> nbsp; n として正式に定義されている負荷係数（非公式には、既に述べている）を探します。 <！> nbsp; / <！> nbsp; N 、つまりバケットの合計に対する使用済みの比率。ハッシュテーブルが適切に機能するためには（または少なくとも数学的な観点からそのパフォーマンスについて推論するため）、<！>＃945; <！> nbsp; <！> lt; <！> nbsp; 1。

他のすべては実際に経験的なテスト次第です。ハッシュテーブルが<！>＃945; <！> nbsp; <！> gt; <！> nbsp; 0.5から始まるとうまくいかないことがわかったら、必ずその値を下回ってください。この値は、衝突解決の手法にも依存します。連鎖によるハッシュには、オープンアドレス指定によるハッシュ以外の負荷要因が必要になる場合があります。さらに別の要因は、キャッシュの局所性です。テーブルが大きくなりすぎると、メインメモリに収まりません。配列へのアクセスはランダムであるため、キャッシュからのロードがボトルネックになる可能性があります。

Answer 3

ハッシュテーブルには通常、オープンとクローズの2種類があります。

開いているハッシュテーブルでは、ハッシュに基づいて適切なバケットを見つけ、そのバケットからぶら下がっているアイテムのリストを作成します。

閉じたハッシュテーブルでは、ハッシュ値を使用して初期バケットを見つけ、それが占有されている場合は、次の値をプローブします。単純なケースでは、次の空きバケットを探すことでこれを行うことができます。または、アイテムから2番目のハッシュ値を作成し、それをステップ実行できます（ただし、これは、バケット）。

通常、開いているハッシュテーブルはサイズ変更されません。初期サイズを、問題に対して合理的であると感じるサイズに設定します。他の人が指摘したように、開いているハッシュテーブルのサイズを変更できますが、このデータ構造のパフォーマンスについての推論は今では非常に難しくなります。特定のバケットの長さがLのときにサイズを変更すると、ハッシュテーブル全体でL個のアイテムだけでサイズを変更する可能性がありますが、非常に非効率的です。

負荷係数（ハッシュテーブル内のアイテム数/バケット数）が事前定義された値に達すると、閉じたハッシュテーブルのサイズが変更されます。私は80％を使用する傾向がありますが、正確な値はあまり重要ではありません。

閉じたハッシュテーブルの利点は、アイテムを挿入する償却コストが常にO（1）であることです（適切なハッシュ関数を想定）。特定のアイテムの挿入は、サイズ変更のコストのためにO（N）になる場合がありますが、それは非常にまれです。

Answer 4

構築しているハッシュテーブルのタイプに依存します。バケットのリンクリストではなく、固定配列ベースのハッシュテーブルを使用している場合、テーブルがいっぱいになったとき、または最大プローブカウントに達したときに（速度を重視するかどうかに応じて）配列のサイズを変更する必要がありますメモリ）。リンクリストを使用している場合、メモリはそれほど問題にならず、空のスペースを調べる必要がないため、サイズ変更はそれほど大きな問題ではありません。

ハッシュテーブルを使用するキーは、バケットの数ではなく、ハッシュアルゴリズムです。理想的には、各バケットに最大で1つのアイテムが常に必要なので、ハッシュテーブルのアイテム数=バケット数のときにサイズ変更するのが理想的です。データが均等に分散されていない場合は、サイズ変更戦略よりもハッシュアルゴリズムの方が優れています。

Answer 5

線形ハッシュを使用する場合、テーブル自体が一定の負荷係数を維持することにより、サイズ変更を自動的に処理します。