TreeMapかHashMapか？[重複あり］

質問

ハッシュマップとツリーマップの使い分けは？

要素をソートする必要があるときに、TreeMapを使用して反復処理できることは知っています。 しかし、それだけでしょうか？私はちょうどマップを参照したいとき、またはいくつかの最適な特定の用途の最適化はありません？

どのように解決するのですか？

ハッシュテーブルは（通常）、以下の複雑さの範囲内で検索操作（ルックアップ）を行います。 O(n)<=T(n)<=O(1) であり、平均的な場合の複雑さは O(1 + n/k) しかし、バイナリサーチツリー(BST)では、検索操作(ルックアップ)は O(n)<=T(n)<=O(log_2(n)) であり、平均的な場合の複雑さは O(log_2(n)) . それぞれの（そしてすべての）データ構造の実装は、利点、欠点、操作の時間の複雑さ、コードの複雑さを理解するために、（あなたによって）知っている必要があります。

例えば、ハッシュテーブルのエントリの数は、しばしば衝突のリストを持ついくつかの固定数（その一部は全く埋められないかもしれません）を持っています。一方、ツリーは通常、ノードあたり 2 つのポインタ (参照) を持ちますが、実装がノードあたり 2 つ以上の子ノードを許可すれば、これはもっと多くなり、これによってノードが追加されるとツリーは成長しますが、重複を許可しない場合があります。(JavaのTreeMapのデフォルトの実装は、重複を許しません)

例えば、特定のデータ構造の要素数が際限なく増加したり、データ構造の基礎となる部分の限界に近づいた場合はどうでしょうか。何らかのリバランスやクリーンアップ操作を実行する償却操作についてはどうでしょうか。

例えば、ハッシュテーブルでは、テーブルの要素数が十分に大きくなると、任意の数の衝突が発生する可能性があります。一方、木は通常、挿入（または削除）後に再バランス処理を行う必要があります。

キャッシュのようなもの（例：要素数が決まっている、サイズがわかっている）であれば、ハッシュテーブルが最適でしょうが、辞書のようなもの（例：一度登録すると何度も調べる）であれば、ツリーを使うことになるでしょうね。

ただし、これはあくまで一般的なケースです（情報が与えられていない）。どのデータ構造を使うか、正しい選択をするためには、どのような処理がどのように行われるかを理解する必要があります。

マルチマップ（範囲検索）やコレクションのソート・フラット化が必要な場合、ハッシュテーブルではだめなんだ。