ハッシュマップを使用するためのより効率的なアプローチは何ですか?
A) 複数の小さなハッシュマップを使用する、または
B) すべてのオブジェクトを 1 つの巨大なハッシュマップに格納しますか?
(キーのハッシュ アルゴリズムがかなり効率的であり、衝突がほとんどないと仮定します)
明確化: オプション B は、主キーによる分離を意味します。つまり、使用する実際のハッシュマップを決定するために追加のルックアップは必要ありません。(たとえば、ルックアップ キーが英数字の場合、ハッシュマップ 1 は A を格納し、ハッシュマップ 2 は B を格納するなどです。)
間違いなく B. ハッシュ テーブルの利点は、ルックアップごとの平均比較回数がサイズに依存しないことです。
マップを N 個の小さなハッシュマップに分割すると、ルックアップごとに平均してそれらの半分を検索する必要があります。小さいハッシュマップの負荷係数が大きいマップの負荷係数と同じである場合、比較の合計数は約 N/2 倍になります。
また、ハッシュマップが小さいほど負荷係数が小さい場合は、メモリを浪費しています。
小さなハッシュマップ間でキーをランダムに配布すると仮定しています。キーの何らかの機能 (文字列プレフィックスなど) に従ってそれらを配布すると、作成したものはtrieになり、一部のアプリケーション (Web フォームのオートコンプリートなど) にとって効率的です。
これらのマップは、論理的に異なる場所で使用されていますか? たとえば、キーが衝突しないことがたまたまわかっているという理由だけで、ユーザー、キャッシュされたクエリ結果、ロガーなどを含む 1 つのマップはありません。ただし、1 つのマップを複数のマップに分割することはありません。
キーから値への論理マッピングごとに 1 つのハッシュマップを保持します。
@Jonの答えに加えて、個別のハッシュテーブルを維持したいという実際的な理由が考えられます。
異なるマッピング用に別々のテーブルがある場合は、各マッピングを個別に「クリア」できます。たとえば、「clear」を呼び出すか、対応するテーブルへの参照を削除します。
個別のテーブルがキャッシュされたエントリへのマッピングを保持している場合は、さまざまな戦略を使用して、それぞれのエントリを「エージング」できます。
アプリケーションがマルチスレッドの場合、個別のテーブルを使用すると、ロックの競合が減り、（一部のプロセッサアーキテクチャでは）プロセッサメモリキャッシュのヒット率が上がる可能性があります。