Why does removing a non-existent element from a map during iteration only crash sometimes?

Question

Note: this is not a duplicate of the many questions asking how to remove an item from a map during iteration.

I encountered some surprising edge cases when using a hash map iterator to remove an item from a map.

The following code crashes with with the a ConcurrentModificationException.

Map<Integer, Integer> m = new HashMap<>();
m.put(1, 1);
m.put(2, 2);
m.put(3, 3);

for (Iterator<Map.Entry<Integer, Integer>> iterator = m.entrySet().iterator(); iterator.hasNext(); ) {
    Map.Entry<Integer, Integer> e = iterator.next();
    if (e.getKey() == 2) {
        iterator.remove();
    }
    m.remove(2); // This causes the crash
}

Unsurprisingly, the following code does not:

Map<Integer, Integer> m = new HashMap<>();
m.put(1, 1);
m.put(2, 2);
m.put(3, 3);

for (Iterator<Map.Entry<Integer, Integer>> iterator = m.entrySet().iterator(); iterator.hasNext(); ) {
    Map.Entry<Integer, Integer> e = iterator.next();
    if (e.getKey() == 2) {
        iterator.remove();
    }
    m.remove(4); // No crash here
}

However, the following code also does not crash:

Map<Integer, Integer> m = new HashMap<>();
m.put(2, 2);
m.put(3, 3);

for (Iterator<Map.Entry<Integer, Integer>> iterator = m.entrySet().iterator(); iterator.hasNext(); ) {
    Map.Entry<Integer, Integer> e = iterator.next();
    if (e.getKey() == 2) {
        iterator.remove();
    }
    m.remove(2); // Also no crash?
}

The only difference between the first and third examples are the removal of the <1, 1> entry. Why does calling Map.remove only crash sometimes? Is this specified in the standard anywhere?

A properly thrown Exception is *not* a crash. And this question is a duplicate of http://stackoverflow.com/questions/5113016/getting-a-concurrentmodificationexception-thrown-when-removing-an-element-from-a?rq=1 (see the 2nd answer). Also, read the [Javadocs on ConcurrentModificationException](https://docs.oracle.com/javase/8/docs/api/java/util/ConcurrentModificationException.html). Relevant: *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.* — KevinO, Apr 19 '16 at 00:17
Try calling `iterator.next()` before the line that crashes. That might give you a clue — smac89, Apr 19 '16 at 00:19
This is not a duplicate. I'm not modifying the collection, since the `Map.remove` call does _not_ change the contents of the collection in any of the examples. — AA A, Apr 19 '16 at 00:20
@AAA you are modifying the map the line that does `m.remove(2); // This causes the crash` modifies the map. Since the iterator is still in a valid state, you get the exception — smac89, Apr 19 '16 at 00:21
What do you mean by "since the Map.remove call does not change the contents of the collection in any of the examples"? Your first example removes element with key 2 which exist in map. I would say it is changing map. — Pshemo, Apr 19 '16 at 00:22
But the map does not contain the value 2 at the point that `m.remove(2)` is called, which is my point. — AA A, Apr 19 '16 at 00:22
Notice what I said in my last comment "The iterator is still in a valid state". It doesn't throw the exception if the element is found or not, but rather if the iterator is still in use — smac89, Apr 19 '16 at 00:23
You call `m.remove(2)` on every iteration of the loop, so `2` exists in the map on the first iteration. — Radiodef, Apr 19 '16 at 00:23
@Pshemo, if that was the issue, then why does the third example NOT raise an exception? — AA A, Apr 19 '16 at 00:24

rgettman · Accepted Answer · 2016-04-19T00:27:16.510

The first example throws a ConcurrentModificationException because you are calling the remove method during iteration of the map. The sequence of events is this.

Call next() to retrieve the entry (1, 1). The key is not 2, so don't call iterator.remove(). Remove the entry with key 2 from the map directly with the call to m.remove(2). This changes an internal modification count that the Iterator expects to be constant.
Call next() to retrieve the next entry. The modification count in the map no longer matches the expected modification count that was noted by the Iterator when it was created, so a ConcurrentModificationException is thrown.

The last example doesn't throw it because remove(2); has no effect any more.

Call next() to retrieve the entry (2, 2). The key is 2, so call iterator.remove(), removing the entry. This has the effect of modifying the iterator's expected modification count to match the map's modification count. Calling m.remove(2) has no effect, because the key 2 no longer exists in the map.
Call next() to retrieve the entry (3, 3). The modification count in the map matches the expected modification count that was noted by the Iterator, so no ConcurrentModificationException is thrown. The key is not 2, so iterator.remove() is not called. Calling m.remove(2) has no effect, because the key 2 does not exist in the map.

Note that the sequence of events above is valid for the current way that a Java HashMap iterates over its entries. The keys happen to be retrieved in order. In general, with any range of valid integer keys, the keys are not guaranteed to be retrieved in order.

Why does removing a non-existent element from a map during iteration only crash sometimes?

1 Answers1