There is no such thing as a fail-safe Iterator in Java

Occasionally I see mention of a “fail-safe” Iterator in Java. What does this mean?

The context here is what happens when a collection is modified while it’s being iterated, or “concurrent modification” for short. Each collection defines its own policy for handling concurrent modification. Note that the issue is when the collection is modified directly, from “outside” the iterator. Modifying the collection via the iterator is generally permitted, with some specific exceptions.

The term “fail-safe” is not used anywhere in the Java SE specification. Instead, the specification describes four different policies for concurrent modification: fail-fast, weakly consistent, snapshot, and undefined.

1. fail-fast

Most of the non-concurrent collections in java.util have fail-fast iterators. See the ArrayList specification for example:

The iterators returned by this class’s iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

2. weakly consistent

Most of the concurrent collections in java.util.concurrent, such as ConcurrentHashMap, are weakly consistent. The definition from the java.util.concurrent package specification is:

Most concurrent Collection implementations (including most Queues) also differ from the usual java.util conventions in that their Iterators and Spliterators provide weakly consistent rather than fast-fail traversal:

• they may proceed concurrently with other operations
• they will never throw ConcurrentModificationException
• they are guaranteed to traverse elements as they existed upon construction exactly once, and may (but are not guaranteed to) reflect any modifications subsequent to construction.

3. snapshot

A third policy is snapshot semantics. The main example of this is CopyOnWriteArrayList:

All mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array.

The “snapshot” style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException. The iterator will not reflect additions, removals, or changes to the list since the iterator was created.

4. undefined

The fourth policy, if it can be called a policy, is that nothing is specified at all. The results of modifying a collection during iteration are undefined and may result in inconsistencies. The examples here are the legacy collections Vector and Hashtable and their methods that return Enumeration, including Vector.elements, Hashtable.elements, and Hashtable.keys.

If you iterate an Enumeration from the Vector.elements method, it’s not difficult to get odd behaviors such as elements being skipped, elements appearing twice in the iteration, or getting an exception unexpectedly.

As an aside, when the Collections Framework was introduced in JDK 1.2, Vector and Hashtable were retrofitted to implement the new interfaces. For example, if you have a Vector, you can get an Enumeration using the Vector.elements method, or you can get an Iterator using the Vector.iterator method. The Iterator has a fail-fast policy, while the Enumeration does not. Hashtable also provides both an Enumeration and an Iterator, and only the latter has the fail-fast policy. What’s interesting is that Hashtable‘s Iterator and Enumeration are implemented by the same class which has a flag that determines whether it should behave as an Iterator or Enumeration.

∞

After all this, where does “fail-safe” come into the picture? Answer: it doesn’t. The words “fail-safe” are never used in the Java SE specifications that describe the concurrent modification policy of a collection. As such, there is no reliable, consistent definition of “fail-safe” for an Iterator. One can attempt to apply the general concept of “fail-safety” to an Iterator, but this is open to varying, misleading, and even contradictory interpretations.

Don’t use “fail-safe” to describe a Java Iterator. Instead, use one of the documented policies listed above.