Java コレクションの実装を選択するための経験則は?

StackOverflow https://stackoverflow.com/questions/48442

  •  09-06-2019
  •  | 
  •  

質問

List、Map、Set などの Java コレクション インターフェイスのさまざまな実装の中から選択するための適切な経験則を持っている人はいますか?

たとえば、一般的に、Vector、ArrayList、Hashtable、または HashMap を使用する方がよい理由、またはどのような場合に使用するのでしょうか?

役に立ちましたか？

解決

私は常に、次のようなユースケースに応じて、ケースバイケースでこれらの決定を行ってきました。

  • 注文を残す必要がありますか?
  • null キー/値を使用することになりますか?ダップス？
  • 複数のスレッドからアクセスされるか
  • キーと値のペアが必要ですか?
  • ランダムアクセスが必要ですか?

そして、私は便利な第 5 版を取り出しました Java の概要 約 20 個のオプションを比較します。第 5 章には、何が適切かを理解するのに役立つ小さな表が含まれています。

わかりました。単純な ArrayList または HashSet でうまくいくことが最初からわかっていれば、すべてを調べることはしないかもしれません。;) しかし、私の意図した使用法に少し複雑な点があるとすれば、私がこの本に書いてあることは間違いありません。ところで、Vector は「古い帽子」であるはずだと思っていましたが、私は何年も使っていませんでした。

他のヒント

Sergiy Kovalchuk のこのチートシートが本当に好きです ブログの記事:

Java Map/Collection Cheat Sheet

さらに詳しくは、Alexander Zagniotov のフローチャートがありましたが、残念ながらオフラインです。

上記の回答から、List、Set、Map の違いは理解できたと思います。なぜそれらの実装クラスの中から選択するかは別の話です。例えば：

リスト:

  1. 配列リスト 取得は速いですが、挿入は遅いです。これは、読み取りは多いが挿入/削除はあまり行わない実装に適しています。データを 1 つの連続したメモリ ブロックに保持するため、拡張する必要があるたびに配列全体をコピーします。
  2. リンクリスト 取得は遅いですが、挿入は速いです。挿入/削除は頻繁に行うが、読み取りはあまり行わない実装に適しています。配列全体を 1 つの連続したメモリ ブロックに保持するわけではありません。

セット：

  1. ハッシュセット 反復の順序は保証されないため、セットの中で最も高速です。オーバーヘッドが高く、ArrayList よりも遅いため、ハッシュ速度が重要になる大量のデータ以外は使用しないでください。
  2. ツリーセット データの順序が維持されるため、HashSet よりも遅くなります。

地図： HashMap と TreeMap のパフォーマンスと動作は Set 実装と同様です。

Vector と Hashtable は使用しないでください。これらは、新しいコレクション階層のリリース前に同期された実装であるため、速度が遅くなります。同期が必要な場合は、Collections.synchronizedCollection() を使用します。

理論的には便利なものがあります ビッグオー トレードオフですが、実際にはこれらはほとんど問題になりません。

実際のベンチマークでは、 ArrayList パフォーマンスを上回る LinkedList 大きなリストがあり、「フロントの近くにたくさんの挿入」などの操作があります。学者は、実際のアルゴリズムには漸近曲線を圧倒する一定の要因があるという事実を無視します。たとえば、リンク リストではノードごとに追加のオブジェクト割り当てが必要になるため、ノードの作成が遅くなり、メモリ アクセス特性が大幅に悪化します。

私のルールは次のとおりです。

  1. 常に ArrayList、HashSet、HashMap から始めます (つまり、LinkedList や TreeMap ではありません)。
  2. 型宣言は常にインターフェイスである必要があります (つまり、List、Set、Map) なので、プロファイラーやコード レビューでそうでないことが証明された場合は、何も壊すことなく実装を変更できます。

最初の質問について…

リスト、マップ、セットは異なる目的を果たします。Java Collections Framework については、次の URL で読むことをお勧めします。 http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html.

もう少し具体的に言うと、

  • 配列のようなデータ構造が必要で、要素を反復処理する必要がある場合は、List を使用します。
  • 辞書のようなものが必要な場合は Map を使用してください
  • 何かがセットに属するかどうかを決定するだけでよい場合は、セットを使用します。

２番目の質問についてですが…

Vector と ArrayList の主な違いは、前者は同期され、後者は同期されないことです。同期について詳しくは、以下をご覧ください。 実際の Java 同時実行性.

Hashtable (T は大文字ではないことに注意してください) と HashMap の違いは同様で、前者は同期されますが、後者は同期されません。

どちらの実装を優先するかという経験則はなく、実際にはニーズによって異なります。

ソートされていない場合、10 回中 9 回以上、最適な選択は次のようになります。ArrayList、HashMap、HashSet。

Vector と Hashtable は同期されるため、少し遅くなる可能性があります。同期された実装が必要になることはほとんどありません。その場合、そのインターフェイスは、同期を有効にするには十分な機能を備えていません。Map の場合、ConcurrentMap はインターフェースを便利にするために追加の操作を追加します。ConcurrentHashMap は ConcurrentMap の優れた実装です。

LinkedList が良いアイデアになることはほとんどありません。挿入と削除を頻繁に行っている場合でも、位置を示すためにインデックスを使用している場合は、正しいノードを見つけるためにリストを反復処理する必要があります。ほとんどの場合、ArrayList の方が高速です。

Map と Set の場合、ハッシュ バリアントはツリー/ソートより高速になります。ハッシュ アルゴリズムのパフォーマンスは O(1) になる傾向がありますが、ツリーのパフォーマンスは O(log n) になります。

リストでは項目の重複が許可されますが、セットではインスタンスが 1 つだけ許可されます。

ルックアップを実行する必要がある場合は常にマップを使用します。

特定の実装については、順序を保持するマップとセットのバリエーションがありますが、主に速度が重要になります。私は、適度に小さいリストには ArrayList を使用し、適度に小さいセットには HashSet を使用する傾向がありますが、実装は多数あります (自分で作成したものを含む)。HashMap はマップでは非常に一般的です。「適度に小さい」以上の場合は、メモリについて心配し始める必要があるため、アルゴリズム的にはより具体的になります。

このページ もっている たくさん LinkedList とサンプル コードをテストするアニメーション画像と厳密な数値に興味がある場合は、ArrayList を参照してください。

編集： 次のリンクが、これらのものが実際にはツールボックス内のアイテムにすぎず、自分のニーズが何であるかを考えればよいことを示していることを願っています。Commons-Collections バージョンを参照してください。 地図, リスト そして セット.

他の回答で示唆されているように、ユースケースに応じて正しいコレクションを使用するにはさまざまなシナリオがあります。いくつかポイントを挙げてみますと、

配列リスト：

  • ほとんどの場合、「一連のもの」を保存または反復処理するだけで済み、後でそれらを反復処理する必要があります。インデックスベースであるため反復処理が高速になります。
  • ArrayList を作成するたびに、固定量のメモリが割り当てられ、それを超えると配列全体がコピーされます。

リンクリスト:

  • 二重リンクリストを使用しているため、ノードを追加または削除するだけなので、挿入と削除の操作が高速になります。
  • 取得はノードを反復処理する必要があるため時間がかかります。

ハッシュセット:

  • 項目に関してその他の「はい」または「いいえ」の決定を行う。例:「アイテムは英語の言葉ですか」、「データベースのアイテムですか？」 、「このカテゴリのアイテムはありますか？」等

  • 「すでに処理したアイテム」を覚えておく。Web クロールを実行するとき。

ハッシュマップ:

  • 「与えられた X に対して、Y は何ですか?」と言う必要がある場合に使用されます。これは、メモリ内キャッシュやインデックス、つまりキーと値のペアの実装に役立つことがよくあります。次に例を示します。特定のユーザー ID について、キャッシュされた名前/ユーザー オブジェクトは何ですか?
  • ルックアップを実行するには、常に HashMap を使用してください。

Vector と Hashtable は同期されるため、少し遅くなります。同期が必要な場合は、Collections.synchronizedCollection() を使用します。チェック これ ソートされたコレクションの場合。これが役に立てば幸いです。

Bruce Eckel の Thinking in Java が非常に役立つことがわかりました。彼はさまざまなコレクションをとても上手に比較しています。私は以前、彼が公開した継承階層を示す図をキューブの壁にクイックリファレンスとして保管していました。スレッドの安全性を念頭に置くことをお勧めします。通常、パフォーマンスはスレッドセーフではないことを意味します。

まあ、それは必要なものによって異なります。一般的なガイドラインは次のとおりです。

リスト データが挿入順に保持され、各要素がインデックスを取得したコレクションです。

セット 重複のない要素のバッグです (同じ要素を再挿入しても追加されません)。データには順序という概念がありません。

地図 データ要素にアクセスして書き込みを行うには、そのキー (考えられる任意のオブジェクト) を使用します。

enter image description here帰属: https://stackoverflow.com/a/21974362/2811258

Java コレクションの詳細については、 この記事をチェックしてください.

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top