ConcurrentModification exception using addAll over Set in Java

Question

I have been completely puzzled by an issue I just came over in my Java application.

When I attempt to run the code given below, Java raises a ConcurrentModificationException on the line that says "if ( this.vertexStore.get ( v ).addAll ( output ) )".

I find this very strange considering this a completely single-threaded application, and that I am not actually modifying anything that I am looping over as far as I can tell?

In fact, the only place I can see the error occurring is inside the addAll method, but that shouldn't happen either as I'm using HashMap and LinkedList from the Java class library...

private Queue<Vertex> worklist = new LinkedList<Vertex> ( );
protected Map<Vertex, Set<T>> vertexStore = new HashMap<Vertex, Set<T>> ( );

// . . .

while ( this.worklist.size ( ) > 0 ) {
        Vertex vertex = this.worklist.remove ( );

        Set<T> output = this.processVertice ( vertex, this.vertexStore.get ( vertex ) );

        this.vertexStore.put ( vertex, output );

        for ( Vertex v : vertex.edgesTo ( ) ) {
            // Conveniently, addAll returns true if the set changed
            if ( this.vertexStore.get ( v ).addAll ( output ) )
                this.worklist.add ( v );
        }
    }

EDIT: Error trace:

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.HashMap$HashIterator.nextEntry(HashMap.java:793)
    at java.util.HashMap$KeyIterator.next(HashMap.java:828)
    at java.util.AbstractCollection.addAll(AbstractCollection.java:305)
    at DataFlowAnalyser.process(DataFlowAnalyser.java:41) (the if line)

Any good ideas are very welcome!

PS: Full source here (sorry for lack of comments, code not completed)

Cheers, Jon

Answer 1

You're calling addAll and passing a reference to the Set itself. If you debug through the code you'll see that this.vertexStore.get(v) returns the same object as is referenced by the output var.

Normally this wouldn't be a problem for a HashSet because addAll won't actually modify the state of a HashSet if you're just adding all the same elements. In this case however, you're modifying the instances of HamiltonPath after they've been added to the set which in turn changes their hash code and makes the HashSet think that the object being added is different than the one it already has.

Here's some code that illustrates the problem better than my prose:

List<String> list1 = Arrays.asList("foo");
List<String> list2 = Arrays.asList("bar");
Set<List<String>> set = new HashSet<List<String>>();
set.add(list1);
set.add(list2);
list1.add("baz"); 
list2.add("qux");
set.addAll(set); // throws ConcurrentModificationException

Answer 2

your code breaks because you are modifying a collection while you are iterating on it and java doesn't like it. If you want to do that use a ConcurrentHashMap that uses a different type of iterator than a standard map.