Atom Feed SITE FEED   ADD TO GOOGLE READER

Coding in the small with Google Collections: Multimap

Part 9 in a Series by Robert Konigsberg, Guest blogger...

Multimap is like a Map, but lets you store multiple values for every key. It turns out this is frequently useful. Consider how often you have had to create, for instance, a Map<K, List<V>>.

Before:

  Map<Salesperson, List<Sale>> map = new Hashmap<SalesPerson, List<Sale>>();

public void makeSale(Salesperson salesPerson, Sale sale) {
List<Sale> sales = map.get(salesPerson);
if (sales == null) {
sales = new ArrayList<Sale>();
map.put(salesPerson, sales);
}
sales.add(sale);
}

After:

  Multimap<Salesperson, Sale> multimap 
= new ArrayListMultimap<Salesperson,Sale>();

public void makeSale(Salesperson salesPerson, Sale sale) {
multimap.put(salesperson, sale);
}


This is just one facet of Multimaps. Consider finding the largest value across all keys:

Before:

  public Sale getBiggestSale() {
Sale biggestSale = null;
for (List<Sale> sales : map.values()) {
Sale biggestSaleForSalesman
= Collections.max(sales, SALE_COST_COMPARATOR);
if (biggestSale == null
|| biggestSaleForSalesman.getCharge() > biggestSale().getCharge()) {
biggestSale = biggestSaleForSalesman;
}
}
return biggestSale;
}

After:

  public Sale getBiggestSale() {
return Collections.max(multimap.values(), SALE_COST_COMPARATOR);
}


The Google Collections Library comes with a large variety of Multimap implementations that you can choose from to meet your specific performance characteristics. Do you want to prevent duplicate key/value pairs? Use HashMultimap. Do you want to iterate over the maps in insertion-order? Use LinkedHashMultimap. Do you want the keys and values ordered by their natural ordering? Use TreeMultimap.
Don't forget to read the Javadoc for Multimaps, which provides access to all the supplied implementations, and much more.

Part 10
The "before" version would not compile. It should say "sales.add(sale);"
Thank you for posting this; your snippets are just great.

I'd like to notice though that this site, myjavatools.com
has been around for years, with the same "functional java" stuff... :)
Thanks James! Fixed.
I'm guessing getBiggestSale() should return a Sale, and not a boolean?

Great examples, by the way.
Is it possible to have a Map within a Multimap? Why stop at just List and Set?
Asgeir - fixed.

Anonymous - Maps don't really work because they don't have an add() method. But you could create a Multimap<Pair<K1,K2>,V> for similar behaviour.
I've just measured times for Google's and Apache's Multimaps in adding, deleting and retrieving and it turns out that Apache's MultiMap, despite other disadvantages, like no generics support and less variety of Multimap implementations, are 2 to 7 times faster than the ones of Google. Has anyone compared those two? Is there a benchmark or something for more accurate measurements?
We're working on an API to do microbenchmarking of the collections. As for current performance deltas - please post your test and results to the dev list, which might inspire the necessary optimizations.
Wow, I happened to remember that your set collections series had Multimap. I was surprised to see that I was the author!

I was also surprised, and sorry, to see that there were straight-up errors. Sorry about that.