java - `ArrayList of HashMap` または `LinkedHashMap` でアイテムをインデックスで取得する

Question

キーと値の形式で大量のデータを保存する必要があります。また、2つの要件があります

配列からのように、インデックスを介してデータをクエリします。
したがって、データ構造の順序を維持する必要があります。

要件 2 については、LinkedHashMapを使用できます。

要件 1 については、次の 2 つのオプションがあります。

1.1 | HashMap の ArrayListを実装します。[ ArrayList<HashMap<String,String>>]
1.2 | LinkedHashMapを実装し、次のようなものを使用してインデックスでアイテムをクエリするには
- ->new ArrayList(hashMapObject.entrySet()).get(0);

1.1問題は、またはの中でどちらが優れているか1.2です。

つまり、メモリとスペースの点で効率的です。

データの量が、平均サイズの文字列を持つ 50 から 100 のキーと値のペアのオーダーであると仮定しましょう。すべてのキーが 10 から 30 文字で、値が 30 から 50 文字であるとします。

score 3 · Accepted Answer

コレクションにはオブジェクトは含まれず、オブジェクトへの参照のみが含まれることに注意してください。

2 つのコレクションを使用します。

ArrayListインデックスによるアクセスのための参照を格納する
HashMapキーによるアクセスの参照を格納するためのA

例えば：

List<MyValue> list = new ArrayList<MyValue>(100000);
Map<MyKey,MyValue> map = new HashMap<MyKey,MyValue>(100000);

while(moreItems) {
    // read input
    MyKey key = ...
    MyValue value = ...
    list.add(value);
    map.put(key,value);
}

// lookup by index
MyValue v1 = list.get(11241);
// lookup by key
MyValue v2 = map.get(someKey);

相互参照が必要な場合 (つまり、値オブジェクトを指定して、そのインデックスまたはキーを検索する) には、いくつかのオプションがあります。

値オブジェクト自体にインデックスとキーを保存します
キーとインデックスを含む「ハンドル」で値をラップします。

例えば

class Wrapper {
    MyKey   key;
    MyValue value;
    int     index;
    // constructor, getters and setters
}

int index=0;
while(moreItems) {
    // read input
    MyKey key = ...
    MyValue value = ...
    Wrapper w = new Wrapper(key,value,index++);
    list.add(w);
    map.put(key,w);
}
...
Wrapper w = list.get(23410);
MyKey k = w.getKey();
MyValue v = w.getValue();
int i = w.getIndex();
...

score 3 · Accepted Answer

SortedMap を使用してみてください。

例えば：

SortedMap<Key, Value> map = new TreeMap<Key, Value>();

このようにして、（キーを介して）高速なルックアップ時間を取得しますが、順序も維持されます。

その後、次のようにデータを反復処理できます。

for(Key k : map.keySet()) { 
    process(map.get(k)); 
}

私は最近、それらを使用して、キーが日付で値がカウンターである 1,000 万件のツイートを分析しました。日付の順序を維持したかったのです。

更新データを繰り返し処理するだけで済む場合は、私の方法で十分です。おそらく、小さな例を提供できますか？インデックスでもデータを参照できることが絶対に必要な場合は、@Jim が言及したように 2 つのデータ構造を維持したいだけのようです。私は前にそれをしなければなりませんでした。

score 2 · Accepted Answer

私はそれを自分で実験して行きました。HashMaps の ArrayListを作成する方法は、1000 要素で約40 倍高速であることが判明しました。

public class HashMapVsArrayOfHashMap {

    public static void main(String[] args){
        ArrayList<HashMap<String, String>> listOfMaps=new ArrayList<HashMap<String,String>>();
        for( int i=0;i<1000;i++){
            final int finalI=i;
        listOfMaps.add(new HashMap<String, String>(){{put("asdfasdfasdfasdfadsf"+finalI,"asdfsdafasdfsadfasdf"+finalI);}});
        }
        LinkedHashMap<String, String> map=new LinkedHashMap<String, String>();
        for(int i=0;i<1000;i++)
            map.put("asdfasdfasdfasdfadsf"+i,"asdfsdafasdfsadfasdf"+i);     
        int position=700;
        testArrayList("Method1:ArrayListOfHashMaps",position,listOfMaps);
        testHashMap("Method2:LinkedHashMap",position,map);
    }

    private static void testArrayList(String string, int position,
            ArrayList<HashMap<String, String>> listOfMaps) {
        long start, end;
        start=System.nanoTime();
        listOfMaps.get(position).get("asdfasdfasdfasdfadsf"+position);
        end=System.nanoTime();
        System.out.println(string+"|Difference = "+(end-start));        
    }
    private static void testHashMap(String string, int position,
            LinkedHashMap<String, String> map) {
        long start, end;
        start=System.nanoTime();

        String s= new ArrayList<String>(map.keySet()).get(position);

        end=System.nanoTime();
        System.out.println(string+"|Difference = "+(end-start));        
    }
}

ここに画像の説明を入力