効率的なハッシュマップの使用

Question

ハッシュマップを使用するためのより効率的なアプローチは何ですか?

A) 複数の小さなハッシュマップを使用する、または

B) すべてのオブジェクトを 1 つの巨大なハッシュマップに保存しますか?

(キーのハッシュ アルゴリズムがかなり効率的であり、衝突がほとんどないと仮定します)

説明:オプション B は、主キーによる分離を意味します。つまり、実際にどのハッシュマップを使用するかを決定するために追加の検索は必要ありません。(たとえば、検索キーが英数字の場合、ハッシュマップ 1 には A が格納され、ハッシュマップ 2 には B が格納されます。)

Answer 1

間違いなくBです。ハッシュ テーブルの利点は、ルックアップごとの比較の平均数がサイズに依存しないことです。

マップを N 個の小さなハッシュマップに分割した場合、各ルックアップで平均して半分を検索する必要があります。小さいハッシュマップの負荷係数が大きいマップの負荷係数と同じである場合、比較の総数は約 N/2 倍に増加します。

また、小さいハッシュマップの負荷係数が小さい場合は、メモリを無駄にしていることになります。

これらはすべて、より小さいハッシュマップ間でキーをランダムに分散することを前提としています。キーの何らかの機能に従ってそれらを配布する場合 (例:文字列プレフィックス)、作成したものは 試してみる, 、これは一部のアプリケーション (例:Web フォームのオートコンプリート。)

Answer 2

これらのマップは、論理的に異なる場所で使用されていますか？たとえば、キーが衝突しないことがわかっているからといって、ユーザー、キャッシュされたクエリ結果、ロガーなどを含む1つのマップはありません。ただし、1つのマップを複数のマップに分割することも等しくありません。

キーから値への論理マッピングごとに1つのハッシュマップを保持します。

Answer 3

@Jonの答えに加えて、個別のハッシュテーブルを維持する実用的な理由があります。

異なるマッピング用に別々のテーブルがある場合、各マッピングを個別に「クリア」できます。例えば「clear」を呼び出すか、対応するテーブルへの参照を削除します。

個別のテーブルがキャッシュされたエントリへのマッピングを保持している場合、異なる戦略を使用してそれぞれのエントリを「エージング」できます。

アプリケーションがマルチスレッドの場合、個別のテーブルを使用するとロックの競合が減少し、（一部のプロセッサアーキテクチャでは）プロセッサメモリキャッシュヒット率が増加する可能性があります。