Map/ArrayList：どちらが素早く要素を検索するのですか

Question

私はコレクションに格納する巨大なデータセットを持っており、そこに複製があるかどうかを調べる必要があります。

データサイズは100万を超える可能性があります。私はArrayList comapre Mapに多くの要素を格納できることを知っています。

私の質問は以下のとおりです。

1. はソートArrayListで検索するよりも高速Mapで鍵を探していますか？
2. を検索していますHashMapのキーがTreeMapより速いですか？
3. n要素を格納するために必要な領域のみについて、TreeMapとHashMapの実装の方が効率的でしょうか？

Answer 1

1）はい。 ArrayListの検索は平均してO（n）です。マップ内のキー参照のパフォーマンスは、特定の実装に依存します。実際にはO（n）または悪い場合はMapの実装を書くことができますが、標準ライブラリのすべての実装はO（n）より高速です。

2）はい。 HashMapは、単純なキー検索では平均でO（1）です。 TreeMapはO（log（n））です。

Class HashMap<K,V>

この実装は、ハッシュ関数が複数のバケットで適切に要素を分散すると仮定すると、基本的な操作（getおよびput）に一定時間のパフォーマンスを提供します。

Class TreeMap<K,V>

この実装のcontainsKeyのための保証のlog（n）時間コストを提供し、取得入れて、操作を削除します。アルゴリズムは、Cormen、Leiserson、Rivestのアルゴリズム入門のアルゴリズムの適応です。

3）どちらの場合も、スペース要件はO（n）になります。私はと思っています。TreeMapにはわずかにスペースが必要ですが、定数でしかありません。

Answer 2

1. 使用しているMapの種類によって異なります。
2. HashMapTreeMapの平均検索時間は、ツリーの深さに基づいているので、（O（）N（ログ））、（（1）O）一定時間平均ルックアップを有しますHashMapはより高速です。
3. おそらく違いはありません。両方のデータ構造は、設計によって空間の複雑さにおいてある程度の一定のオーバヘッドを必要とする（ともにO（n）空間の複雑さ）。