optimization - ハッシュバケットの数

Question

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

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

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

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

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

Answer 1

良い経験則 (常に理想的であるとは限りませんが、経験則にすぎません) は、ハッシュテーブルが 80% までいっぱいになった場合に再ハッシュすることです。つまり、100 個のバケツと 80 個のアイテムが内部にある場合、以前に衝突が何度あったかに関係なく、容量を増やす時間が来ていることを意味します。

どのくらい増やしたらいいですか？まあ、完璧な値もありません。最も簡単な解決策は、増加するたびに容量を 2 倍にすることです。したがって、200、400、800 などになります。これが多すぎると思われる場合は (結局、ハッシュテーブルが非常に大きくなると 8 MB のメモリが 16 MB に跳ね上がり、16 MB がいっぱいになることはないかもしれません)、より小さな成長係数を選択してください。少なくとも 3 分の 1 が推奨されます (100 から 133 に増やします)。

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

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

Answer 2

一般に、負荷係数 (非公式に、既に述べました) に注目します。これは、正式には α =  n  /  Nとして定義されます。つまり、合計バケットに対する使用済みの比率です。ハッシュ テーブルが適切に機能する (または少なくとも数学的な用語でそのパフォーマンスを推論する) ためには、α < 1 である必要があります。

他のすべては実際に経験的なテスト次第です。α > 0.5 でハッシュ テーブルのパフォーマンスが低下することがわかった場合は、必ずその値を下回るようにしてください。この値は、衝突解決技術にも依存します。チェーンを使用したハッシュには、オープン アドレスを使用したハッシュとは別の負荷係数が必要になる場合があります。さらに別の要因は、キャッシュの局所性です。テーブルが大きくなりすぎると、メイン メモリに収まりません。配列へのアクセスはランダムであるため、キャッシュからの読み込みがボトルネックになる可能性があります。

Answer 3

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

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

閉じたハッシュテーブルでは、ハッシュ値を使用して最初のバケットを見つけ、それが占有されている場合は次の値を調べます。単純なケースでは、次の空いているバケットを探すことでこれを行うことができます。または、アイテムから 2 番目のハッシュ値を作成し、それをステップ実行することもできます (ただし、これがハッシュ テーブルのサイズを法として素数であることを確認する必要があるため、すべてのバケットにアクセスする必要があります)。バケツ）。

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

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

クローズド ハッシュテーブルの利点は、アイテムを挿入するための償却コストが常に O(1) であることです (適切なハッシュ関数を想定)。サイズ変更のコストのために、特定のアイテムを挿入するのは O(N) かもしれませんが、それが行われることはめったにありません。

Answer 4

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

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

Answer 5

Linear Hashing を使用すると、一定の負荷係数を維持することで、テーブル自体が自動的にサイズ変更を処理します。