`ArrayList of HashMap` or `LinkedHashMap` to get i

问题:

My need to store a a huge amount of data in the key-value form. Also, I have two requirements

1. query data via the index, like from an array.
2. hence the order in the data structure must be preserved.

For Requirement 2 - I can use a LinkedHashMap.

For Requirement 1 - I have two options :

• 1.1 | To implement an ArrayList Of HashMap. [ArrayList<HashMap<String,String>>]
• 1.2 | To implement a LinkedHashMap and query the items by index using something like
  • -> new ArrayList(hashMapObject.entrySet()).get(0);

The Question is which is better among 1.1 or 1.2 ?

By better, I mean - efficient in terms of memory and space.

Let's assume the volume of data is in the order of 50 to 100 key-value pairs with average sized Strings - say every key is 10-30 characters and value is 30-50 characters.

回答1:

Try using SortedMap.

For example:

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

This way you get the fast lookup time (via key), but they also remain ordered.

You can then iterate over the data like so:

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

I used them recently to analyze 10s millions tweets where the key was a date, and the value was a counter. I wanted to maintain the ordering of the dates.

update If you can get by with just itereating over the data, then my method will suffice. Perhaps you could supply a small example? If it's absolutely required that you can reference the data by index as well, it seems like you would just want to maintain two datastructures like @Jim mentioned. I'ved had to do that before.

回答2:

Remember that collections do not contain the objects, only references to objects.

Use two collections:

1. An ArrayList to store the references for access by index
2. A HashMap to store the references for access by key

For example:

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);

If you need to cross-reference (i.e. given a value object, find its index or its key) you have some options:

1. Save the index and key in the the value object itself
2. Wrap the value in a "handle" that contains the key and index.

For example

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();
...

回答3:

I think the LinkedHashMap is the best solution, but to get the item, you can use

hashMapObject.values().toArray()[index]

However, the toArray method will be slow for large amounts of data. But that is something you'll have to test.

If speed is really an issue, you can maintain a HashMap and an ArrayList.

回答4:

I went with experimentating it myself. Turns out the method of creating an ArrayList of HashMaps is about 40 times faster with 1000 elements.

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));        
    }
}

When you increase the size to 30,000 elements - the difference is HUGE.