If you’ve done LeetCode’s Design HashMap, you’ve implemented put, get, and remove. What that exercise usually skips is the part that actually breaks in production: what happens when someone mutates the map while another piece of code is iterating over it.
I ran into this directly while building MyHashMap, a from-scratch single-threaded HashMap (separate chaining, resize on load factor). Getting put/get/remove right was the easy 80%. Getting entrySet().iterator() to correctly detect concurrent mutation — including the case where a second, completely separate iterator is the one that should notice — took three wrong turns before landing on the pattern the JDK actually uses.
The problem, concretely
Iterator<Entry<K,V>> it = map.entrySet().iterator();
it.next();
map.put(someNewKey, someValue); // structural change, mid-iteration
it.next(); // ??? — undefined behavior if we don't guard against this
Enter fullscreen mode Exit fullscreen mode
Without a guard, next() might return a stale entry, skip entries entirely, or throw an unrelated exception depending on internal bucket-array state. Java’s real collections handle this with ConcurrentModificationException (CME) — but the interesting part isn’t the exception, it’s the mechanism that detects when to throw it.
First idea: a boolean “dirty” flag
Obvious first attempt: a boolean modified field on the map, flipped to true on any put/remove, checked by the iterator. This works for exactly one iterator. It falls apart the moment two iterators are alive at once:
- Iterator A calls
next(), seesmodified == false, proceeds. - Something else mutates the map.
modifiedflips totrue. - Iterator B — created after that mutation — checks the same shared
modifiedflag, seestrue, and incorrectly throws, even though nothing has changed since B was created.
A single shared boolean can’t represent “changed since this specific iterator was created” for more than one iterator at a time. Resetting it on read doesn’t help either — now the other iterator stops seeing the change it legitimately needed to see.
Second idea: a timestamp
Next instinct: give the map a lastModified timestamp instead, and have each iterator capture the current time on creation. Compare timestamps instead of a shared flag — now each iterator has its own baseline.
This closes the multi-iterator gap, but introduces a different bug: resolution. Two mutations in a tight loop, or a mutation immediately followed by iterator creation, can land in the same millisecond (System.currentTimeMillis()) — or even the same tick of System.nanoTime() on some platforms. If a real modification and an iterator’s baseline capture ever produce the same timestamp value, the comparison can’t tell who happened first. Worse, currentTimeMillis() isn’t even guaranteed monotonic — it can jump backward on a clock adjustment.
The deeper issue: this isn’t a timing problem. It’s a “did anything change since I looked” problem, and wall-clock time is the wrong tool for a question that has nothing to do with elapsed time.
What actually works: a monotonic counter (modCount)
Every mutation increments a plain long counter. Every iterator, at creation, snapshots the counter’s current value. Every next() call compares its snapshot against the live value:
final class MyEntryIterator implements Iterator<Entry<K, V>> {
private long expectedVersion;
// ...
public MyEntryIterator() {
this.expectedVersion = version; // snapshot at creation
}
@Override
public Entry<K, V> next() {
if (expectedVersion != version) {
throw new ConcurrentModificationException();
}
// ... advance and return
}
}
Enter fullscreen mode Exit fullscreen mode
No shared mutable flag, no clock. Each iterator carries its own independent baseline (expectedVersion), so the multi-iterator case that broke the boolean flag now works automatically — iterator B’s snapshot is whatever the counter was when B was created, completely independent of A’s. And since it’s a plain increment, not a physical measurement, there’s zero resolution/collision risk: every mutation gets a value strictly different from every other, no matter how fast they happen. This is exactly the pattern java.util.HashMap, ArrayList, and friends use internally — go read AbstractList‘s modCount field and the ConcurrentModificationException javadoc directly; it’s short.
The subtlety that actually caught me: no “free” first call
Here’s the case that exposed a real bug in my own test suite, not just the implementation. Two iterators, A and B, created back to back — before either has called next() even once:
sequenceDiagram
participant Map
participant IteratorA
participant IteratorB
Note over Map: version = 3 (after 3 puts)
IteratorA->>Map: create (snapshot version=3)
IteratorB->>Map: create (snapshot version=3)
IteratorA->>Map: next()
IteratorA->>Map: remove() → version = 4
IteratorB->>Map: next()
Map-->>IteratorB: ConcurrentModificationException
Note over IteratorB: B never called next() before A's<br/>change — still invalidated on its<br/>very first callI originally wrote a test that let iterator B succeed on its first next() call before asserting a second call would throw. That’s wrong: B’s snapshot predates A’s remove(), so B is already stale the instant A mutates — there’s no “one free call” grace period. The check only cares whether a modification happened since the snapshot was taken, not whether the iterator has navigated yet. Fixing that test (not the implementation) was the actual bug.
The self-invalidation trap
One more sharp edge: an iterator’s own remove() legitimately bumps the shared counter — so if the iterator doesn’t resync its own expectedVersion immediately afterward, it trips its own check on the very next call:
@Override
public void remove() {
if (!nextCalled) {
throw new IllegalStateException();
}
MyEntry entryToDelete = currentEntry;
this.next();
MyHashMap.this.remove(entryToDelete.getKey());
this.expectedVersion = version; // resync — or self-CME on the next call
this.nextCalled = false;
}
Enter fullscreen mode Exit fullscreen mode
One more nuance most write-ups skip: not every write is “structural”
The counter shouldn’t bump on every put() — only on ones that actually change the map’s shape. Overwriting the value of an already-present key isn’t structural (same key, same position, same size) and doesn’t need to invalidate a live iterator; inserting a genuinely new key is, and does:
if (entry == null) {
entries[bucket] = new MyEntry(key, value);
++count;
++version; // new key: structural
} else {
// walk the chain...
if (matchFound) {
entry.setValue(value); // existing key, value-only: NOT structural, no bump
}
}
Enter fullscreen mode Exit fullscreen mode
This matches java.util.HashMap‘s real behavior, and it’s the kind of detail that only shows up once you’ve actually built the thing rather than read about it.
Takeaway
Fail-fast iteration looks like a one-line trick (modCount) until you actually have to defend it against a second iterator, a same-millisecond race, or your own iterator’s legal mutation. Building it from scratch — and writing tests that actually exercise the multi-iterator case — surfaced three separate designs before landing on the one that’s actually in the JDK, plus a bug in the test for the final design, not the code.
Further reading
- Fail-Safe Iterator vs Fail-Fast Iterator — Baeldung
-
ConcurrentModificationExceptionjavadoc — the “best-effort, not a guarantee” language is worth reading verbatim - java-iterator-fail-types — GitHub