MultiMap vs MultiValue Map

Question

At one place i have to use a map with many values mapped to a single key, so i was wondering whether there is any significant performance distinction between using HashMap of key, list and MultiMap of key , values in java.

score 7 · Accepted Answer · answered Apr 29 '11 at 09:56

7

You can try it but I doubt there is much difference as it does much the same thing.

IMHO The advantage is simpler/clearer code which is usually more important than performance.

answered Apr 29 '11 at 09:56

Peter Lawrey

525,659
79
751
1,130

score 2 · Answer 2 · edited Sep 02 '14 at 19:58

2

I'd recommend to use google collections if you want to use a more convenient implementation of a Multimap. In case you don't want to introduce a new dependency, HashMap<Key, Collection<Value>> should do the trick which is pretty much what apache.collections HashMultiMap does.

edited Sep 02 '14 at 19:58

Brad Mace

27,194
17
102
148

answered Apr 29 '11 at 10:07

Sebastian Zarnekow

6,609
20
23

1

Yes. Google collection is named "Guava". There are some different value collections: HashMultiMap, ArrayListMultiMap... – 卢声远 Shengyuan Lu Apr 29 '11 at 10:10

卢声远 Shengyuan Lu · Answer 3 · 2011-04-29T10:20:46.323

0

Hash provides O(1) which is fast and does nothing with the size of elements.

Regarding to Multimap, you could put values in dependent collection (List, Set). Different collection implementations provides different performance.

EDIT: As I commented on Sebastian's answer. You could use Guava which provides different value collection implemantions: HashMultiMap (HashMap<KEY, HashSet<VALUE>>), ArrayListMultiMap (HashMap<KEY, ArrayList<VALUE>>)...

edited Apr 29 '11 at 10:20

answered Apr 29 '11 at 09:59

卢声远 Shengyuan Lu

31,208
22
85
130

Hashmap/HashTable/Hash* does not provide O(1), in the worst case, where had collisions with all the input keys, it is O(N). – Pih Apr 29 '11 at 10:06
1

@Pih: hmm...big O doesn't indicate worst case. – 卢声远 Shengyuan Lu Apr 29 '11 at 10:07
1

Ok, I considered the O() notation as the Big O notation, that it is usually used for the worst case. Anyway, Hashtables provides *amortized* O(1) access. – Pih Apr 29 '11 at 10:15

score 0 · Answer 4 · answered Apr 29 '11 at 10:09

If it is a Map Key-> Values, use a Map implementation.

As you will have some Values with the same Keys, use the http://guava-libraries.googlecode.com/svn/tags/release09/javadoc/com/google/common/collect/HashMultiset.html from the Google Collection (now guava library, http://code.google.com/p/guava-libraries/ ) for your task.

MultiMap vs MultiValue Map

4 Answers4

Linked