An iterator enables us to iterate the objects in a collection, and the iterator can be either Fail-Safe or Fail-Fast. The Fail-Fast iterator will throw ConcurrentModificationException whenever we modify the collection during iteration. On the other hand, Fail-Safe iterator will not throw ConcurrentModificationException even when we modify the collection during iteration. In this article, let’s understand the Fail-Fast and Fail-Safe Iterators in Java.
Fail-Fast and Fail-Safe Iterators in Java
Before getting into the details, let’s take a look into Fail-Fast and Fail-Safe with an example.
ArrayList is an example of a Fail-Fast iterator, and it throws ConcurrentModificationException when the ArrayList is modified during iteration.
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class FailFastIterator
{
public static void main(String args[])
{
List al = new ArrayList();
al.add("1");
al.add("2");
al.add("3");
Iterator it = al.iterator();
while (it.hasNext())
{
String val = it.next();
if (val.equals("1"))
{
al.remove(0);
}
}
System.out.println(al);
}
}
The above code will throw ConcurrentModificationException, as we are removing an item during iteration when the value is equal to 1.
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:907)
at java.util.ArrayList$Itr.next(ArrayList.java:857)
at com.javainterviewpoint.FailFastIterator.main(FailFastIterator.java:19)
Let’s take the ArrayList equivalent Fail-Safe collection, which is CopyOnWriteArrayList, and perform the same removal operation and see what happens?
import java.util.Iterator;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
public class FailSafeInterator
{
public static void main(String[] args)
{
List cl = new CopyOnWriteArrayList();
cl.add("1");
cl.add("2");
cl.add("3");
Iterator it = cl.iterator();
while (it.hasNext())
{
String val = it.next();
if (val.equals("1"))
{
cl.remove(0);
}
}
System.out.println(cl);
}
}
Even though we are removing an element during iteration, the CopyOnWriteArrayList will not throw any ConcurrentModificationException.
Output:
[2, 3]
Why fail-fast iterator throws ConcurrentModificationException?
Now let’s understand the internals of a fail-fast iterator with ArrayList. The ArrayList or every fail-fast collection class will have flag variable modCount, which gets incremented for every modification done on the collection, be it addition or removal.
In the ArrayList class the modCount changes for all the modification methods which we call like add(), remove(), fastRemove(), clear(), trimToSize(), ensureExplicitCapacity()… etc.
The ArrayList class has an inner class Itr, which performs the iteration on the ArrayList.
As a first step, this iterator stores the modCount value to expectedModCount, to keep track of the changes.
int expectedModCount = modCount;
During iteration, the iterators expect the expectedModCount value to be the same as the modCount value. It calls the checkForComodification() method to check whether both values are the same.
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
If we have not performed any modification operations on the collection during iteration, then the modCount and expectedModCount will have the same value. Hence, no ConcurrentModificationException occurs.
But when we have made some modifications to the collection during iteration, the expectedModCount value will not be the same as the modCount, and hence it throws ConcurrentModificationException.
Then how to solve this issue?
We can call the remove() method of the iterator, in that case, we will not get any ConcurrentModificationException as it internally reassigns the value of the expectedModCount to the new modCount value.
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
Let’s change our code with the above approach and check
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class FailFastIterator
{
public static void main(String args[])
{
List al = new ArrayList();
al.add("1");
al.add("2");
al.add("3");
Iterator it = al.iterator();
while (it.hasNext())
{
String val = it.next();
if (val.equals("1"))
{
it.remove();
}
}
System.out.println(al);
}
}
Now our code works fine and produces the below output.
[2, 3]
Why does fail-safe iterator will not throw ConcurrentModificationException?
The fail-safe iterator works on the snapshot of the actual collection, and so any modification to the actual collection will not disturb the iterator.
In the case of CopyOnWriteArrayList, the iterator() method creates a new instance of COWIterator, to which the original collection is passed and a snapshot is taken and used for iteration.
public Iterator iterator() {
return new COWIterator(getArray(), 0);
}
As we can see that the COWIterator constructor creates a snapshot from the actual collection (elements array) and stores them in a snapshot array.
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
snapshot = elements;
}
In the above image, we can see that the COWIterator performs all the operations on the snapshot array and not on the real collection, and hence It will not throw any ConcurrentModificationException.
Although this type of iterator will not throw ConcurrentModificationException, it has its drawbacks.
- It requires additional memory as it is copying the original collection.
- The iterator will not reflect the current state of the collection, as the iteration is happening on the snapshot.
In the fail-fast iterator, we are allowed to remove or add an element using the iterator instance. In contrast, in the case of fail-safe iterator because of the copy mechanism, any add or remove operation using the iterator instance will throw UnsupportedOperationException.
Let’s try to remove an element from the CopyOnWriteArrayList with the iterator instance.
import java.util.Iterator;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
public class FailSafeInterator
{
public static void main(String[] args)
{
List cl = new CopyOnWriteArrayList();
cl.add("1");
cl.add("2");
cl.add("3");
Iterator it = cl.iterator();
while (it.hasNext())
{
String val = it.next();
if (val.equals("1"))
{
it.remove();
}
}
System.out.println(cl);
}
}
This will produce UnsupportedOperationException
Exception in thread "main" java.lang.UnsupportedOperationException
at java.util.concurrent.CopyOnWriteArrayList$COWIterator.remove(CopyOnWriteArrayList.java:1178)
at com.javainterviewpoint.FailSafeInterator.main(FailSafeInterator.java:22)
Fail-Fast Vs Fail-Safe Iterators
Let’s put all them into a tabular form
| Fail-Fast Iterator | Fail-Safe Iterator |
|---|---|
| Fail-Fast Iterators does not allow us to make any modification to the collection while iterating | Fail-Safe Iterators allows us to modify to the collection while iterating |
| Throws ConcurrentModificationException when the collection is modified | Does not throw ConcurrentModificationException when the collection is modified |
| Uses the original collection for the iteration | Uses the snapshot of the collection for the iteration |
| We are allowed to modify the collection using the iterator instance | We are not allowed to modify the collection using the iterator instance |
| It does not need additional memory as the iteration happens on the original collection | Requires additional memory, as it takes a snapshot of the original collection |
| Example: Iterators of ArrayList, HashMap, LinkedList, Vector | Example: Iterators of CopyOnWriteArrayList, ConcurrentHashMap, ConcurrentMap |
Happy Learning!!
Leave a Reply