What is the difference between fail-fast and fail-safe iterator?

In Java, iterators are used to traverse elements of a collection. When a collection is modified structurally while an iterator is in use, different types of iterators behave differently. This difference is categorized into two main types: fail-fast and fail-safe iterators.

Fail-Fast Iterators

Fail-fast iterators immediately throw a ConcurrentModificationException if a collection is structurally modified (i.e., elements are added, removed, or the underlying array is resized) at any time after the iterator is created, except through the iterator's own remove() or add() methods (if supported). They are designed to detect concurrent modifications and prevent unpredictable behavior by failing quickly.

This mechanism is typically implemented by maintaining a modCount variable in the collection. Each structural modification increments modCount. The iterator keeps its own expected modCount value. During each iteration operation (next(), hasNext()), the iterator compares its expected modCount with the collection's current modCount. If they don't match, a ConcurrentModificationException is thrown.

Characteristics include: generally not thread-safe, suitable for single-threaded environments or when external synchronization is used, and they provide immediate feedback on concurrency issues.

Common examples are iterators for ArrayList, HashMap, HashSet, and other collections in the java.util package.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class FailFastExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String element = iterator.next();
            System.out.println(element);
            // This will cause ConcurrentModificationException
            if (element.equals("B")) {
                list.add("D"); // Structural modification
            }
        }
    }
}

Fail-Safe Iterators

Fail-safe iterators do not throw a ConcurrentModificationException even if the collection is structurally modified while iteration is in progress. They operate on a snapshot or a copy of the collection at the time the iterator was created.

Because they work on a copy, any modifications to the original collection after the iterator's creation are not reflected in the elements returned by the iterator. This makes them inherently thread-safe with respect to concurrent modifications during iteration.

Characteristics include: generally thread-safe, suitable for concurrent environments, do not reflect real-time changes to the collection, and might consume more memory due to the copy.

Examples include iterators provided by concurrent collections like CopyOnWriteArrayList, CopyOnWriteArraySet, ConcurrentHashMap (its iterators reflect modifications made prior to iterator creation, but not necessarily subsequent ones in a consistent manner, still generally considered fail-safe in that they won't throw CME).

import java.util.Iterator;
import java.util.concurrent.CopyOnWriteArrayList;

public class FailSafeExample {
    public static void main(String[] args) {
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
        list.add("X");
        list.add("Y");
        list.add("Z");

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String element = iterator.next();
            System.out.println(element);
            // This modification will not affect the current iterator
            // and will not throw ConcurrentModificationException
            if (element.equals("Y")) {
                list.add("W"); // Structural modification
            }
        }
        System.out.println("Modified list after iteration: " + list);
        // Output will show X, Y, Z from iterator, then list: [X, Y, Z, W]
    }
}

Key Differences Summary

Choosing between fail-fast and fail-safe iterators depends on the specific requirements of your application. Fail-fast iterators are good for detecting bugs early in single-threaded contexts or where strict consistency is required with external synchronization. Fail-safe iterators are preferred in concurrent environments where you need to iterate over a collection without worrying about concurrent modifications, even if it means iterating over a slightly stale view of the data.