Tuesday, June 16, 2009

Funny ConcurrentModificationException while playing with Google's Multimap

(Disclaimer: Google's Multimap surely work fine and as advertised - this post describes a potentially confusing code interaction which can result in unintuitive ConcurrentModificationExceptions)

First, lets create a multimap:

Multimap multimap = HashMultimap.create();

Put somehow some values to it:

putSomeValues(multimap);

Now lets iterate its key set, and potentially filter some elements of each key's collection:
for (Key key : multimap.keySet()) {
Collection values = multimap.get(key);

...
if (something) {
Value someValue = ...;
values.remove(someValue);
}
}
(We could iterate its entries() as well, which is supposedly faster, but for now, I won't bother).

This seems safe. I iterate the keys, and don't perform any structural modification in the multimap, I might only make a collection inside it shorter.

Well, no. It can blow if "values" becomes empty, since then the multimap will remove the respective entry from the map (this is a very desirable behavior, to be sure), thus structurally modifying the map, thus ConcurrentModificationException when the iterator will try to fetch the next key.

This may be quite nasty if only rarely the "values" collection goes empty and triggers this behavior, so it's good to know.

My solution is this:

Iterator keyIterator = multimap.keySet().iterator();
while (keyIterator.hasNext()) {
Key key = keyIterator.next();
Collection values = multimap.get(key);

...
if (something) {
Value someValue = ...;
if (values.size() == 1 && values.contains(someValue)) {
keyIterator.remove();
continue; //this is not really needed
}
values.remove(someValue);
}
}
Quite simpler would be to simply change this:

for (Key key : multimap.keySet()) {

To this:

for (Key key : Lists.newArrayList(multimap.keySet())) {

If you don't mind creating a copy of the entire key set up-front.