Best way to create a hashmap of arraylist

Question

I have one million rows of data in .txt format. the format is very simple. For each row:

user1,value1
user2,value2
user3,value3
user1,value4
...

You know what I mean. For each user, it could appear many times, or appear only once (you never know). I need to find out all the values for each user. Because user may appear randomly, I used Hashmap to do it. That is: HashMap(key: String, value: ArrayList). But to add data to the arrayList, I have to constantly use HashMap get(key) to get the arrayList, add value to it, then put it back to HashMap. I feel it is not that very efficient. Anybody knows a better way to do that?

Answer 1

it would be faster if you used a LinkedList instead of an ArrayList, as the ArrayList will need to resize when it nears capacity.

you will also want to appropriately estimate the capacity of the wrapping collection (HashMap or Multimap) you are creating to avoid repetitive rehashing.

Answer 2

Use Multimap from Google Collections. It allows multiple values for the same key

http://google-collections.googlecode.com/svn/trunk/javadoc/index.html?com/google/common/collect/Multimap.html

Answer 3

The ArrayList values in your HashMap are references. You don't need to "put it back to HashMap". You're operating on the object that already exists as a value in the HashMap.

Answer 4

i think what you want is the Multimap. You can get it from apache's commons collection, or google-collections.

http://commons.apache.org/collections/

http://code.google.com/p/google-collections/

"collection similar to a Map, but which may associate multiple values with a single key. If you call put(K, V) twice, with the same key but different values, the multimap contains mappings from the key to both values."

Answer 5

You don't need to re-add the ArrayList back to your Map. If the ArrayList already exists then just add your value to it.

An improved implementation might look like:

Map<String, Collection<String>> map = new HashMap<String, Collection<String>>();

while processing each line:

String user = user field from line
String value = value field from line

Collection<String> values = map.get(user);
if (values==null) {
    values = new ArrayList<String>();
    map.put(user, values)
}
values.add(value);

Answer 6

As already mentioned, MultiMap is your best option.

Depending on your business requirements or constraints on the data file, you may want to consider doing a one-off sorting of it, to make it more optimised for loading.