Concurrent Modification Exception

Question

I'm currently working on a multi-threaded application, and I occasionally receive a concurrently modification exception (approximately once or twice an hour on average, but occurring at seemingly random intervals).

The faulty class is essentially a wrapper for a map -- which extends LinkedHashMap (with accessOrder set to true). The class has a few methods:

synchronized set(SomeKey key, SomeValue val)

The set method adds a key/value pair to the internal map, and is protected by the synchronized keyword.

synchronized get(SomeKey key)

The get method returns the value based on the input key.

rebuild()

The internal map is rebuilt once in a while (~every 2 minutes, intervals do not match up with the exceptions). The rebuild method essentially rebuilds the values based on their keys. Since rebuild() is fairly expensive, I did not put a synchronized keyword on the method. Instead, I am doing:

public void rebuild(){
  /* initialization stuff */
  List<SomeKey> keysCopy = new ArrayList<SomeKey>();
  synchronized (this) {
    keysCopy.addAll(internalMap.keySet());
  }
  /* 
    do stuff with keysCopy, update a temporary map
   */    
  synchronized (this) {
    internalMap.putAll(tempMap);
  }
}

The exception occurs at

keysCopy.addAll(internalMap.keySet());

Inside the synchronized block.

Suggestions are greatly appreciated. Feel free to point me to specific pages/chapters in Effective Java and/or Concurrency in Practice.

Update 1:

Sanitized stacktrace:

java.util.ConcurrentModificationException
        at java.util.LinkedHashMap$LinkedHashIterator.nextEntry(LinkedHashMap.java:365)
        at java.util.LinkedHashMap$KeyIterator.next(LinkedHashMap.java:376)
        at java.util.AbstractCollection.toArray(AbstractCollection.java:126)
        at java.util.ArrayList.addAll(ArrayList.java:473)
        at a.b.c.etc.SomeWrapper.rebuild(SomeWraper.java:109)
        at a.b.c.etc.SomeCaller.updateCache(SomeCaller.java:421)
        ...

Update 2:

Thanks everyone for the answers so far. I think the problem lies within the LinkedHashMap and its accessOrder attribute, although I am not entirely certain atm (investigating).

If accessOrder on a LinkedHashMap is set to true, and I access its keySet then proceed to add the keySet to a linkedList via addAll, do either of these actions mutate the order (i.e. count towards an "access")?

Answer 1

If you constructed LinkedHashMap with accessOrder = true then LinkedHashMap.get() actually mutates the LinkedHashMap since it stores the most recently accessed entry at the front of the linked list of entries. Perhaps something is calling get() while the array list is making its copy with the Iterator.