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

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 > 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() , seesmodified == false , proceeds. - Something else mutates the map. modified flips totrue . - Iterator B - created after that mutation - checks the same shared modified flag, 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 > { private long expectedVersion; // ... public MyEntryIterator() { this.expectedVersion = version; // snapshot at creation } @Override public Entry 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 change - still invalidated on its 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. Further reading - Fail-Safe Iterator vs Fail-Fast Iterator - Baeldung - ConcurrentModificationException javadoc - the "best-effort, not a guarantee" language is worth reading verbatim - java-iterator-fail-types - GitHub Top comments (0)