マップとリストの検索

Question

効率に関して質問があります。

は、私は単純なオブジェクトFoo

public class Foo { 
    Integer id; 
    List<String> data; 
    ... 
} 

のリストを持っている今、私がfooクラス

List<Foo> fooList = new ArrayList<Foo>(); 

のリストを持って、私は何千ものレコードのコレクションを持っていると私がする必要があると言うと言いますそれらをこのリストに追加しますが、リストにすでに追加されているIDを見つけたら、重複したIDを持つ新しいfooを追加するのではなく、foo.dataリストを追加する必要があります。

私がこの

Map<Integer, Foo> uniqueFoos = new HashMap<Integer, Foo>(); 

のように遭遇し、私は、レコードの私の何千ものを反復処理するように私は、単にかどうかを確認するために地図上のチェックを行い、それぞれのユニークなfoo.idためのマップを作成するのが賢明だろうfoo.idはすでに

if(uniqueFoos.containes(record.id)) 
    uniqueFoos.getFoo().add(record.data) 

else 
    uniqueFoos.add(record.id, record) 

が存在すると私はマップにすべてのレコードを追加したら、私はその後、マップを反復して、リスト

for(Foos f: uniqueFoos) 
    fooList.add(fooInMap.get(f)) 

にFOOSのそれぞれを追加します

また、Mapのアイデアを一括して取り除くべきですか？ fooListを繰り返し処理し、既にrecord.idに一致するfoo.idが含まれているかどうかを検索する方が効率的でしょうか。またはArrayList.contains(...)メソッドを使用することもできますか？私はそれがマップ方法と比べてこのようにすることははるかに非効率的であるように感じる。

更新：一部の人がセットの使用についても言及しています。だから、Setは他のリストにあるオプションをすべて調べる方法でしょうか？

注：私がここに書いたコードは、単に疑似コードです。

Answer 1

ハッシュマップは間違いなく良い選択です。 ListはO（n）であるのに対し、O（1）ではルックアップを行います。

個々の要素を検索して変更する必要がある場合は、しばしばHashMapを使用します。

Answer 2

コードをプロファイリングすることなく確実に言うのは難しいです。しかし、ハッシュマップのランダムアクセスには一定の時間がかかります（ほとんどの場合、衝突がなければ）、配列の反復は常に線形です。

Answer 3

「何千ものレコード」がある場合は、間違いなくMapを使用する必要があります。

例uniqueFoos.getFoo().add(record.data)はコンパイルされません。
uniqueFoos.get(record.id).add(record.data)である必要があります。マップ内の二重のルックアップを防ぐために

、あなたのコードは次のようになります。

Foo foo = uniqueFoos.get(record.id); 
if (foo == null) // not found 
    uniqueFoos.add(record.id, record); 
else 
    foo.add(record.data);