Fail-fast iterator

It is generally not permissible for one thread to modify a collection while another thread is iterating over it. There are iterator implementations which throw ConcurrentModificationException in such scenario. This type of iterators are fail-fast iterators. All general purpose collection iterator implementations provided by JRE are fail-fast.

Please note the following for ConcurrentModificationException, as per Oracle documentation:

Note that this exception does not always indicate that an object has been concurrently modified by a different thread. If a single thread issues a sequence of method invocations that violates the contract of an object, the object may throw this exception. For example, if a thread modifies a collection directly while it is iterating over the collection with a fail-fast iterator, the iterator will throw this exception.

Note that fail-fast behavior cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast operations throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness. ConcurrentModificationException should be used only to detect bugs.

Fail-fast iterators throw ConcurrentModificationException if there is a structure modification of the collection. Structural modification means adding, removing or updating element of collection while a thread is iterating over it.

The fail-fast iterators are typically implemented using a volatile counter associated with collection object.

• When the collection is updated, the counter is incremented.
• When an Iterator is created, the current value of the counter is embedded in the Iterator object.
• When an Iterator operation is performed, the method compares the two counter values and throws a ConcurrentModificationException if these values do not match.

Note: If you remove element from collection using remove() method of iterator, ConcurrentModificationException will not be thrown. However, in case of using remove() method of collection class, ConcurrentModificationException will be thrown. For example, if you use remove() method of ArrayList, JRE will throw exception.

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

public class FailFastExample {
	public static void main(String[] args) {
		List<Integer> list = new ArrayList();
		list.add(1);
		list.add(2);
		list.add(3);
		Iterator itr = list.iterator();
		
		while(itr.hasNext()) {
			itr.next();
			System.out.println(list);
			list.add(1);
		}
		
	}
}

Output

[1, 2, 3]Exception in thread "main" 
java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at com.testdb.FailFastExample.main(FailFastExample.java:16)

Fail-safe iterator

There is no such term as fail-safe iterator. We have used the term fail-safe to compare with fail-fast iterator. These iterators loop over a copy of the actual collection. So if the actual collection is modified while looping over collection, fail-safe iterators will never throw exception. As per Java specification :

1. they may proceed concurrently with other operations
2. they will never throw ConcurrentModificationException
3. 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.

Since fail-safe iterators loop over a copy of actual collection (like CopyOnWriteArrayList), this is an overhead in terms of time and memory.

Java specification uses term weakly consistent. For example, iterator of ConcurrentHashMap is weakly consistent.

When we use CopyOnWriteArrayList in our previous example of fail-fast iterator, we don’t get ConcurrentModificationException.

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

public class FailSafeExample {
	public static void main(String[] args) {
		CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<Integer>();
		list.add(1);
		list.add(2);
		list.add(3);
		Iterator itr = list.iterator();
		
		while(itr.hasNext()) {
			itr.next();
			System.out.println(list);
			list.add(1);
		}
		
	}
}

Output

[1, 2, 3]
[1, 2, 3, 1]
[1, 2, 3, 1, 1]