The 80% Problem: Basic HashMap Functionality
Most developers are familiar with the basic operations of a HashMap: put, get, and remove. These are often the focus of coding challenges like LeetCode's "Design HashMap." However, the real-world complexity arises not from these core operations but from what happens when the map is mutated while another part of the program is iterating over its contents. This is the "fail-fast" scenario that often breaks production systems.
The author, while building a from-scratch, single-threaded HashMap with separate chaining and resizing on load factor, found that implementing these basic methods was the relatively easy part. The true challenge lay in making the entrySet().iterator() correctly detect concurrent modification. This includes the complex case where a modification is made by a second, entirely independent iterator operating on the same map.
The Failure of Simple Flags
The initial approach to handling concurrent modification often involves a simple boolean flag. For instance, setting a flag to true when an iterator is created and false when the map is modified. The iterator would then check this flag on each access. If the flag indicates a modification occurred, an exception is thrown.
This approach, however, is fundamentally flawed. It fails to account for the nuances of multi-threaded environments, even in a single-threaded context where multiple iterators might exist. The core issue is that a boolean flag provides a coarse-grained signal. It cannot distinguish between modifications made by the iterator itself (which are often permissible in some contexts, though not in this fail-fast design) and modifications made by external code or other iterators.
Consider a scenario: Iterator A starts. A boolean flag is set. Then, Iterator B starts. The flag remains set. If Iterator B modifies the map, Iterator A will detect it. But what if Iterator A modifies the map? The boolean flag doesn't inherently know which iterator is responsible. More critically, if Iterator A is iterating, and some other code (not another iterator, but a direct call to put or remove) mutates the map, the simple flag might not be reset or checked correctly by Iterator A in all its internal states.
The JDK's Pattern: ModCount and Iterator States
The Java Development Kit (JDK) employs a more robust strategy. Instead of a simple boolean, it uses a combination of a modification count and iterator-specific state tracking. The HashMap in the JDK maintains an internal counter (often called modCount) that is incremented every time the map's structure is altered (e.g., by put, remove). When an iterator is created, it captures the current value of this modCount.
During iteration, on each call to next() or hasNext(), the iterator compares its captured modCount with the map's current modCount. If they differ, it signifies that the map has been modified since the iterator was created or last advanced. This is the trigger for a ConcurrentModificationException.
This approach elegantly solves the problem of external modifications. Even if the modification is not made by another iterator, as long as the map's internal modCount is updated, the existing iterator will detect the change.
Implementing the Fail-Fast Iterator
To implement this pattern in a custom HashMap, the following steps are crucial:
- Map-Level Modification Counter: Introduce an integer field in the HashMap class, say
modCount, initialized to 0. Increment this counter in all methods that modify the map's structure:put,remove, and potentially methods involved in resizing. - Iterator Creation: When an iterator is requested (e.g., via
entrySet().iterator()), create an iterator object. This iterator object should store a copy of the map's currentmodCountat the time of its creation. Let's call thisexpectedModCount. - Iterator Operations (
next(),hasNext()): Before performing any operation that advances the iterator (like returning the next element or checking if there are more elements), the iterator must first check ifexpectedModCountis equal to the map's currentmodCount. - Exception Handling: If
expectedModCount != map.modCount, throw aConcurrentModificationExceptionimmediately. This ensures the "fail-fast" behavior.
The author's journey involved several iterations. An initial attempt might have been too simplistic, perhaps only checking the flag on next() but not hasNext(), or failing to account for the case where the iterator itself might be the source of modification (though in a strict fail-fast iterator, even self-modification might be disallowed or handled differently). The JDK's approach, using modCount, is a proven pattern that handles external modifications reliably.
Why This Matters Beyond LeetCode
While LeetCode problems focus on core logic, production code demands robustness. Concurrent modification is a common pitfall, especially as applications grow and more components interact. Understanding how standard libraries like the JDK handle such issues provides a blueprint for building more reliable custom data structures or for effectively using existing ones.
A custom HashMap might be built for performance tuning, specific memory layouts, or integration with other custom components. In such cases, ensuring its behavior aligns with or intentionally diverges from standard library patterns is critical. The fail-fast iterator is a key aspect of this robustness. It prevents subtle, hard-to-debug errors that only manifest under specific, often intermittent, load conditions.
The surprise here is not that concurrent modification is a problem, but how elegantly the modCount pattern addresses it by providing a simple, yet powerful, checksum for the map's state. It's a classic example of how a small, carefully managed counter can enforce complex invariants across multiple operations and threads (or in this case, simulated concurrency within a single thread via iterators).
The Unanswered Question: Iterator Removal
What remains an open challenge in many custom iterator implementations is how to handle the remove() operation on the iterator itself. Standard library iterators often have a remove() method that removes the *last returned element*. Implementing this safely within a fail-fast iterator requires careful synchronization and state management to ensure that the modCount is updated correctly, and that subsequent calls to next() or hasNext() still function correctly, potentially even allowing the iterator to continue if the removed element was not the one it was about to return.