Gaurav Tyagi

Posted on Aug 30

I Built My Own Fail-Fast HashMap — Here's Why a Boolean Flag Wasn't Enough

#java #datastructures #computerscience

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

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(), sees modified == false, proceeds.
Something else mutates the map. modified flips to true.
Iterator B — created after that mutation — checks the same shared modified flag, sees true, 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
    }
}

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 call

I 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;
}

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
    }
}

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.

DEV Community