ConcurrentModificationException when using stream with Maps key set

Question

I want to remove all items from someMap which keys are not present in someList. Take a look into my code:

someMap.keySet().stream().filter(v -> !someList.contains(v)).forEach(someMap::remove);

I receive java.util.ConcurrentModificationException. Why? Stream is not parallel. What is the most elegant way to do this?

Solution 1

@Eran already explained how to solve this problem better. I will explain why ConcurrentModificationException occurs.

The ConcurrentModificationException occurs because you are modifying the stream source. Your Map is likely to be HashMap or TreeMap or other non-concurrent map. Let's assume it's a HashMap. Every stream is backed by Spliterator. If spliterator has no IMMUTABLE and CONCURRENT characteristics, then, as documentation says:

After binding a Spliterator should, on a best-effort basis, throw ConcurrentModificationException if structural interference is detected. Spliterators that do this are called fail-fast.

So the HashMap.keySet().spliterator() is not IMMUTABLE (because this Set can be modified) and not CONCURRENT (concurrent updates are unsafe for HashMap). So it just detects the concurrent changes and throws a ConcurrentModificationException as spliterator documentation prescribes.

Also it worth citing the HashMap documentation:

The iterators returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

While it says about iterators only, I believe it's the same for spliterators.

Solution 2

You don't need the Stream API for that. Use retainAll on the keySet. Any changes on the Set returned by keySet() are reflected in the original Map.

someMap.keySet().retainAll(someList);

Solution 3

Your stream call is (logically) doing the same as:

for (K k : someMap.keySet()) {
    if (!someList.contains(k)) {
        someMap.remove(k);
    }
}

If you run this, you will find it throws ConcurrentModificationException, because it is modifying the map at the same time as you're iterating over it. If you have a look at the docs, you'll notice the following:

Note that this exception does not always indicate that an object has been concurrently modified by a different thread. If a single thread issues a sequence of method invocations that violates the contract of an object, the object may throw this exception. For example, if a thread modifies a collection directly while it is iterating over the collection with a fail-fast iterator, the iterator will throw this exception.

This is what you are doing, the map implementation you're using evidently has fail-fast iterators, therefore this exception is being thrown.

One possible alternative is to remove the items using the iterator directly:

for (Iterator<K> ks = someMap.keySet().iterator(); ks.hasNext(); ) {
    K next = ks.next();
    if (!someList.contains(k)) {
        ks.remove();
    }
}

Solution 4

Later answer, but you could insert a collector into your pipeline so that forEach is operating on a Set which holds a copy of the keys:

someMap.keySet()
    .stream()
    .filter(v -> !someList.contains(v))
    .collect(Collectors.toSet())
    .forEach(someMap::remove);

View more solutions