skip to content

How does a fail-fast iterator in java.util, such as ArrayList's, detect concurrent modification internally?

level: middleimportance: must knowfreq 62%

answer

  1. modCount on the collection
  2. expectedModCount on the iterator
  3. checkForComodification on each next()
  4. Iterator.remove re-syncs expectedModCount
  5. unsynchronized = best-effort only

basics

~20 s

The collection keeps a counter called modCount that goes up every time you add or remove an element. When you make an iterator, it remembers that number. On each next() it compares them; if they differ, the collection changed behind its back, so it throws.

solid answer

~40 s

Most fail-fast iterators rely on a modification counter, modCount, stored on the backing collection (e.g. AbstractList, HashMap). Every structural change (add/remove/clear) increments modCount. When you obtain an iterator, it copies the current modCount into a field called expectedModCount. On each next() and remove(), the iterator runs a check (checkForComodification() in ArrayList, the same comparison inline in HashMap) that throws ConcurrentModificationException if modCount != expectedModCount. The iterator's own remove() updates expectedModCount after modifying, so it stays consistent — that's why iterator-based removal is safe. The check is cheap and unsynchronized: it's a best-effort bug detector, so it gives no guarantee under true multi-threaded access and may miss a race. It surfaces the common single-threaded misuse at the loop's next step rather than letting iteration silently produce wrong results.

code

java · 35 lines
java
import java.util.*;

// Simplified from java.util.AbstractList.Itr: the fail-fast check and little else
abstract class SketchList<E> extends AbstractList<E> {
    private class Itr implements Iterator<E> {
        int cursor = 0;
        int lastRet = -1;
        int expectedModCount = modCount;   // snapshot at creation

        public boolean hasNext() {
            return cursor != size();       // no check, so a loop can end without one
        }

        public E next() {
            checkForComodification();      // throws if modCount changed
            E next = get(cursor);
            lastRet = cursor++;
            return next;
        }

        public void remove() {
            if (lastRet < 0) throw new IllegalStateException();
            checkForComodification();
            SketchList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;   // re-sync so we don't throw next time
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
}

go deeper

for a junior

Knows there's a hidden counter that detects changes and that the iterator's own remove() is the safe way to delete during a loop.

for a middle

Can name modCount/expectedModCount, describe checkForComodification on next(), and explain why Iterator.remove() re-syncs the counter and is therefore safe.

for a senior

Understands the check is unsynchronized/best-effort, that fail-fast is documented as non-guaranteed for concurrency, and that views check the parent's modCount.

for a principal

Reasons about the trade-off (cheap bug detection vs correctness guarantee), the memory-visibility implications of an unsynchronized counter, and steers architecture toward concurrent collections for shared mutable state.

## Goal We want to understand the exact machinery that makes a **fail-fast iterator** throw `ConcurrentModificationException` (CME). 'Fail-fast' means: the moment it detects the collection changed underneath it, it stops and throws, rather than continuing and returning wrong data. ## The key field: `modCount` Most mutable JDK collections (via base classes like `AbstractList`, and inside `HashMap`, `ArrayList`, etc.) hold an `int` field named **`modCount`** — short for *modification count*. (`ArrayDeque` has no such field; its fail-fast iterators infer interference from the array's own state.) The field's rule: > Every **structural modification** increments `modCount`. A **structural modification** adds or removes elements (`add`, `remove`, `clear`, `addAll`, etc.) or, in `AbstractList`'s words, otherwise perturbs the list so that iterations in progress may yield incorrect results. So `ArrayList.sort` and `replaceAll` bump `modCount` with the size unchanged. Replacing a value in place (`set`, or `put` on an existing `HashMap` key) does **not** bump it. ## The snapshot: `expectedModCount` When you create an iterator, its constructor copies the collection's current `modCount` into its own field, **`expectedModCount`**: ```java int expectedModCount = modCount; ``` This is the iterator's memory of 'the collection as it was when I started.' ## The check: `checkForComodification()` On every `next()` (and the iterator's own `remove()`), `ArrayList`'s iterator runs this; `HashMap` and `TreeMap` inline the same comparison: ```java final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } ``` If someone changed the collection structurally through the collection's own API (e.g. `list.remove(x)`), `modCount` advanced but `expectedModCount` did not — they differ — and the next `next()` throws. `hasNext()` runs no check: in `ArrayList` it is only `cursor != size`, so a removal that makes it false, such as one made while the loop is on the second-to-last element, ends the loop before `next()` can throw. ## Why `Iterator.remove()` is safe The iterator's own `remove()` performs the structural change *and then* re-syncs its snapshot: ```java public void remove() { // ... do the actual removal, which bumps modCount ... expectedModCount = modCount; // re-sync, so the next check passes } ``` Because it updates `expectedModCount` to match, subsequent `next()` calls don't throw. This is why the sanctioned way to remove during iteration is the iterator's own `remove()` (a `ListIterator`'s `add` re-syncs the same way). `removeIf` replaces the loop rather than running inside it: `Collection`'s default calls `Iterator.remove`, `ArrayList` overrides it with its own pass, and called inside a for-each, either one is an outside modification: if it removes something, the outer iterator's next `next()` throws, provided the loop reaches one. ## Best-effort, not a guarantee The `modCount` read in `checkForComodification()` is **not synchronized** and `modCount` is not `volatile` in the general case. Therefore: - Under true multi-threaded modification, the detection is **best-effort**: it may catch the race or miss it. The Javadoc says fail-fast behavior 'cannot be guaranteed', that it 'should be used only to detect bugs', and that it would be wrong to write a program that depended on the exception for its correctness. - This is why you must never write `try { iterate } catch (ConcurrentModificationException e) { /* assume thread safety */ }`. ## Sub-list and view gotchas Views like `subList`, `keySet`, `entrySet` check the parent's `modCount`. Structurally modifying the parent while iterating a view (or vice versa) also trips the check — another reason to treat CME as 'something structurally changed unexpectedly.' ## Contrast: weakly consistent iterators Concurrent collections (`ConcurrentHashMap`, `ConcurrentLinkedQueue`) **do not** use this modCount check. Their iterators are **weakly consistent**: they never throw CME, traverse elements as they existed at or since iterator creation, and may or may not reflect modifications made after creation. `CopyOnWriteArrayList` goes further: its iterator walks an immutable **snapshot** taken at creation, so later writes are invisible to it and it never throws.

  • Why does the JDK warn against catching ConcurrentModificationException to handle threading?
    Because the modCount check is unsynchronized and best-effort, so it can miss races. It's a debugging aid for detecting bugs, not a reliable signal of concurrent access. For real concurrency, use thread-safe/concurrent collections instead.
  • If I call list.set(i, v) during iteration, does the iterator throw?
    No. set() is not a structural modification, so it doesn't increment modCount and the check still passes. Only structural changes are detected, and that is wider than size changes: ArrayList.sort counts too.

  • Saying the check compares size() or element hashes rather than modCount vs expectedModCount.
  • Believing modCount detection is a reliable concurrency/thread-safety guarantee — it's unsynchronized and best-effort.
  • Thinking value updates (set, or put on an existing HashMap key) bump modCount — only structural changes do.
  • Not knowing why Iterator.remove() is safe (it re-syncs expectedModCount).

context