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

Question

ハッシュマップを使用すると効率的なアプローチは何ですか？

A）は、複数のより小さなハッシュマップ、または

Bを使用して）1つの巨大なハッシュマップ内のすべてのオブジェクトを格納？

（キーのハッシュアルゴリズムは、いくつかの衝突の結果、かなり効率的であると仮定する）

明確化：オプションBは、主キーによって分離を意味 - 追加の検索が実際のハッシュマップを使用するかを決定する必要がない、すなわち。たとえば、検索キーが英数字の場合、ハッシュマップ1にはA、ハッシュマップ2にはBなどが格納されます。

Answer 1

もちろんB.ハッシュテーブルの利点は、ルックアップごとの平均比較回数が独立していることですサイズの。

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

小さいハッシュマップの負荷係数が小さいと、メモリが浪費されます。

小さなハッシュマップの間でランダムにキーを配布することを前提としています。キーの一部の機能（文字列接頭辞など）に基づいてそれらを配布する場合、作成した内容はtrieで、一部のアプリケーションでは有効です（Webフォームの自動補完など）。

Answer 2

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

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

Answer 3

@ Jonの答えには、別々のハッシュテーブルを維持したいという実用的な理由があります。

マッピングごとに異なるテーブルがある場合は、それぞれのマッピングを個別に「クリア」することができます。例えば'clear'を呼び出すか、または対応するテーブルへの参照を取り除くことによって実行されます。

キャッシュされたエントリへのマッピングが別のテーブルに保持されている場合は、それぞれのエントリを異なるものにするためにさまざまな方法を使用できます。

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