CODEWITHSUNDEEP
javaiteratorconcurrentmodification
AA A
AA A

Reputation: 448

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

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?

Upvotes: 2

Views: 6776

Answers (1)

rgettman
rgettman

Reputation: 178293

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

  1. 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.
  2. 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.

  1. 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.
  2. 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.

Upvotes: 5

Related Questions