In this article ,I would try to explain FAIL-FAST and FAIL-SAFE behaviour of iterators.
What is Iterator
Iterator is an interface defined in java.util package,with following methods declared in it :
boolean hasNext();
E next();
void remove();
Various collections in collection framework has implemented this iterator interface to provide facility to iterate over the elements of those collections.So as we can see from methods provided by Iterator interface,using hasNext method we can check if there are more elements in the collection and using next method we can actually get the next element in the collection.So these two methods are the backbone of Iterator implementation.
Lets see now what is Fail-fast and Fail-safe iterator.
1. Fail-Fast Iterators
What is the meaning of fail fast
When iterating over the elements of the collection,if there is some structural modification in the collection after the iterator is created except through remove method of collection,fail-fast iterator will fail immediately by throwing concurrentModificationException.
By structural modification,it means addition or deletion of elements from collection and not just reading or replacing of element.
Lets
take an example of ArrayList. As we will see in below examples that
concurrentModificationException will be thrown only when elements are added
(using add() method) or deleted(using remove() method).However if we are simply
replacing an element of an arrayList with another element(using set()
method),it is not considered as structural modification and no concurrentModificationException
will be thrown.
From Java Docs(java.util.ArrayList)
"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.
Note
that the fail-fast behavior of an iterator cannot be guaranteed as it is,
generally speaking, impossible to make any hard guarantees in the presence of
unsynchronized concurrent modification. Fail-fast iterators
throwConcurrentModificationException on a best-effort basis. Therefore, it
would be wrong to write a program that depended on this exception for its
correctness: the fail-fast behavior of iterators should be used only to detect
bugs."
ConcurrentModificationException in single
Threaded Environment
a) ConcurrentModificationException on adding
element in ArrayList while iterating
In the below example,we will try to
add element in an ArrayList while we are iterating over it.
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class TestFailfastIterator {
public static
void main(String[] args) throws Exception {
List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
Iterator<String> itrList = list.iterator();
while(itrList.hasNext()){
String element = itrList.next();
System.out.println(element);
if("a".equalsIgnoreCase(element)){
list.add("d"); // We are adding element while iterating.
}
}
}
}
Output :
a
Exception in thread
"main" java.util.ConcurrentModificationException
at
java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
at
java.util.AbstractList$Itr.next(AbstractList.java:343)
at
com.gb.failFastIterator.TestFailfastIterator.main(TestFailfastIterator.java:16)
Probable Solution to avoid
ConcurrentModificationException in case of a)
Assuming that in a) ,
developer wants to add another element("d") to the list on fulfilling
some condition,in our case when element in the existing list is
"a".This can be achieved as below by adding new elements in new
ArrayList and then after iterator has completed,this sublist can be added
(appended) at the end of existing list.
import
java.util.ArrayList;
import
java.util.Iterator;
public class
TestFailfastIterator {
public static void main(String[] args) throws
Exception {
List<String> list = new
ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
list.add("a");
List<String> subList = new
ArrayList<String>();
Iterator<String> itrList =
list.iterator();
while(itrList.hasNext()){
String element = itrList.next();
System.out.println(element);
if("a".equalsIgnoreCase(element)){
subList.add("d");
}
}
list.addAll(subList);
System.out.println("Added sublist to end
of original list");
for(String str : list){
System.out.println(str);
}
}
}
Output :
a
b
c
a
Added sublist to end of
original list
a
b
c
a
d
d
b) ConcurrentModificationException on
removing element using remove method of ArrayList while iterating
import
java.util.ArrayList;
import
java.util.Iterator;
import java.util.List;
public class
TestFailfastIterator {
public static void main(String[] args) throws Exception {
List<String> list = new
ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
list.add("a");
Iterator<String> itrList = list.iterator();
while(itrList.hasNext()){
String element = itrList.next();
System.out.println(element);
if("a".equalsIgnoreCase(element)){
list.remove("a");
}
}
}
}
Output :
a
Exception in thread
"main" java.util.ConcurrentModificationException
at
java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
at
java.util.AbstractList$Itr.next(AbstractList.java:343)
at
com.gb.failFastIterator.TestFailfastIterator.main(TestFailfastIterator.java:16)
Probable Solution for ConcurrentModificationException in
case of b)
import
java.util.ArrayList;
import
java.util.Iterator;
import java.util.List;
public class
TestFailfastIterator {
public static void main(String[] args) throws
Exception {
List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
list.add("a");
List<String> subList = new ArrayList<String>();
Iterator<String> itrList =
list.iterator();
while(itrList.hasNext()){
String element = itrList.next();
System.out.println(element);
if("a".equalsIgnoreCase(element)){
subList.add("a");
}
}
list.removeAll(subList);
System.out.println("Removed elements of
sublist from original list");
for(String str : list){
System.out.println(str);
}
}
}
Output :
a
b
c
a
Removed elements of
sublist from original list
b
c
Another Solution for b) and a better
solution,as it need not create another ArrayList object.No
ConcurrentModificationException is thrown on removing element while
iterating using remove method of Iterator
If we remove element
using Iterator's remove method,it will not throw
concurrentModificationexception.Basically remove() method removes the element
which is last returned by the next() method from the underlying ArrayList.
But why there is
partiality between ArrayList's remove and Iterator's remove method.Why
ArrayList's remove is throwing concurrentModificationException however
Iterator's remove is not.
The proable reason that
I can think of is that purpose of throwing concurrentModificationException is
that ,once an Iterator has been taken on ArrayList(collection),then during the
iteration it should be only Iterator itself which can do manipulation on the
ArrayList ,no outside manipulation(write operartion) is allowed concurrently(at
same time).
import
java.util.ArrayList;
import
java.util.Iterator;
import java.util.List;
public class
TestFailfastIterator {
public static void main(String[] args) throws
Exception {
List<String> list = new
ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
list.add("a");
Iterator<String> itrList = list.iterator();
while(itrList.hasNext()){
String element = itrList.next();
System.out.println(element);
if("a".equalsIgnoreCase(element)){
itrList.remove();
}
}
System.out.println("After removing
elements by remove() method of Iterator");
for(String str : list){
System.out.println(str);
}
}
}
Output :
a
b
c
a
After removing elements
by remove() method of Iterator
b
c
ConcurrentModificationException in Multi
threaded environment
Here in the below program thread 2 is adding an element to ArrayList instance when it is being iterated by thread 1.
import
java.util.ArrayList;
import
java.util.Iterator;
import java.util.List;
public class
CMExceptionMultithreaded {
private static final List<String> list =
new ArrayList<String>();
public static void main(String[] args) {
list.add("a");
list.add("b");
list.add("c");
list.add("d");
Thread t1 = new Thread(new Runnable() {
@Override
public void run()
{
Iterator<String> itrList =
list.iterator();
while(itrList.hasNext()){
String str = itrList.next();
System.out.println("Thread1:"+str);
}
}
});
t1.start();
//update list in second thread
Thread t2 = new Thread(new Runnable() {
@Override
public void run()
{
System.out.println("Thread 2");
list.add("e");
}
});
t2.start();
}
}
Output :
Thread1:a
Thread1:b
Thread1:c
Thread 2
Thread1:d
Exception in thread
"Thread-0" java.util.ConcurrentModificationException
at
java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
at
java.util.AbstractList$Itr.next(AbstractList.java:343)
at
com.gb.failFastIterator.CMExceptionMultithreaded$1.run(CMExceptionMultithreaded.java:20)
at java.lang.Thread.run(Thread.java:662)
Solution for ConcurrentModificationException
in multi threaded environment
Solution 1:
Synchronize the code
import
java.util.ArrayList;
import
java.util.Collections;
import
java.util.Iterator;
import java.util.List;
public class
CMExceptionMultithreaded {
private static List<String> list = new
ArrayList<String>();
public static void main(String[] args) {
list.add("a");
list.add("b");
list.add("c");
list.add("d");
Thread t1 = new Thread(new Runnable() {
@Override
public void run()
{
list = Collections.synchronizedList(list);
synchronized(list) {
Iterator<String> itrList = list.iterator();
while(itrList.hasNext()){
String str = itrList.next();
System.out.println("Thread1:"+str);
}
}
}
});
t1.start();
//update list in second thread
Thread t2 = new Thread(new Runnable() {
@Override
public void run()
{
list = Collections.synchronizedList(list);
synchronized(list) {
list.add("e");
Iterator<String> itrList = list.iterator();
while(itrList.hasNext()){
String str = itrList.next();
System.out.println("Thread2:"+str);
}
}
}
});
t2.start();
}
}
Output :
Thread1:a
Thread1:b
Thread1:c
Thread1:d
Thread2:a
Thread2:b
Thread2:c
Thread2:d
Thread2:e
Solution 2:
Use thread safe implementation of ArrayList
which is CopyOnWriteArrayList
We can use
CopyOnWriteArrayList which is thread safe implementation of List interface.It
achieves its thread safe nature due the reason that whenever we take Iterator
over collection,it keeps snapshot or copy of it at that time and works on that
copy instead of the original collection.
import
java.util.Iterator;
import java.util.List;
import
java.util.concurrent.CopyOnWriteArrayList;
public class
CMExceptionMultithreaded {
private static List<String> list = new
CopyOnWriteArrayList<String>();
public static void main(String[] args) {
list.add("a");
list.add("b");
list.add("c");
list.add("d");
Thread t1 = new Thread(new Runnable() {
@Override
public void run()
{
Iterator<String> itrList = list.iterator();
while(itrList.hasNext()){
String str = itrList.next();
System.out.println("Thread1:"+str);
}
}
});
t1.start();
//update list in second thread
Thread t2 = new Thread(new Runnable() {
@Override
public void run()
{
list.add("e");
Iterator<String> itrList = list.iterator();
while(itrList.hasNext()){
String str = itrList.next();
System.out.println("Thread2:"+str);
}
}
});
t2.start();
}
}
Output :
Thread1:a
Thread1:b
Thread1:c
Thread2:a
Thread1:d
Thread2:b
Thread2:c
Thread2:d
Thread2:e
As you can see from
above output that after Thread 1 iterated over list till element "c",
thread 2 started ,which means it added element "e" to the list,but
when Thread 1 resumed its iteration it did not print element "e" ,as
Thread 1 and Thread 2 are having separate copies of list.
Note :
concurrentHashMap and CopyOnWriteHashSet are thread safe implementations of
HashMap and HashSet respectively.Basicallly all the classes in
java.util.concurrent package are thread safe.
When concurrentModificationException will not
be thrown
Replacing element using set method and not
adding or deleting will not throw concurrentModificationException,as its
not structural modification and is not changing size.
As we discussed earlier
in this article,that concurrentModificationException will be thrown only when
there is structural change in the collection such that it changes(Increases or
decreases) the size of collection.Mere replacing the element with another
element or only iterating over collection will never throw exception.
Lets check with an
example.
import
java.util.ArrayList;
import
java.util.Iterator;
public class
TestFailfastIterator {
public static void main(String[] args) throws
Exception {
List<String> list = new
ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
Iterator<String> itrList =
list.iterator();
while(itrList.hasNext()){
System.out.println(itrList.next());
list.set(1, "d");
}
}
}
Output :
a
d
c
How Iterator knows that there has been structural
modification in the ArrayList
For that we need to
understand hierarchy of ArrayList,which can be seen in below diagram.ArrayList
class inherits from abstract class AbstractList.This AbstractList class
has a variable modCount,which is declared as below.If you get time ,you can
read description about it as mentioned in Java doc comments below Or else I am
going to explain briefly :)
/**
*
The number of times this list has been <i>structurally
modified</i>.
*
Structural modifications are those that change the size of the
*
list, or otherwise perturb it in such a fashion that iterations in
*
progress may yield incorrect results.
*
*
<p>This field is used by the iterator and list iterator implementation
*
returned by the {@code iterator} and {@code listIterator} methods.
* If
the value of this field changes unexpectedly, the iterator (or list
*
iterator) will throw a {@code ConcurrentModificationException} in
*
response to the {@code next}, {@code remove}, {@code previous},
*
{@code set} or {@code add} operations. This provides
*
<i>fail-fast</i> behavior, rather than non-deterministic behavior
in
*
the face of concurrent modification during iteration.
*
*
<p><b>Use of this field by subclasses is optional.</b> If a
subclass
*
wishes to provide fail-fast iterators (and list iterators), then it
*
merely has to increment this field in its {@code add(int, E)} and
*
{@code remove(int)} methods (and any other methods that it overrides
*
that result in structural modifications to the list). A single call to
*
{@code add(int, E)} or {@code remove(int)} must add no more than
*
one to this field, or the iterators (and list iterators) will throw
*
bogus {@code ConcurrentModificationExceptions}. If an implementation
*
does not wish to provide fail-fast iterators, this field may be
*
ignored.
*/
protected transient int
modCount = 0;
so ArrayList class inherits this modcount property
from AbstractList class.Now whenever there is addition or removal of elements
in the ArrayList,modcount will be increased by 1.
So say we added 4 elements to an ArrayList,in that case modCount
will be 4.You can put the debug point as can be seen below and can inspect list
after all four elements have been added.It will show you modcount 4.
Now when we
get Iterator over an ArrayList as below
list.iterator();
What
iterator() method does is ,it will instantiate Itr class which is defined as
inner class within ArrayList class and this Itr class has instance variable
expectedModCount,which is initialized as below
int
expectedModCount = modCount;
So which
means that when we got iterator over an ArrayList, expectedModCount will also
be 4.
So far so
good...
Say now
while iterating we added another element(e) to ArrayList using add method of
ArrayList,so what will happen?
modCount
will increase to 5.
expectedModCount of iteartor will still be 4.
Now when we will call next() method of Iterator
,it first calls method checkForComodification(),which is defined as below:
Now as modCount(5) != expectecdModCount(4),this will throw
concurrentModificationException.
Moral of the story is ,while we are iterating over a collection,it
should not be modified except by remove() method of Iterator,and if there
are some modifications outside of Iterator,it will get to know that and
it will throw concurrentModificationException.
Which are the collections which are
having Fail Fast iterators
Iterators of all the
collections within java.util package are fail fast.For example : ArrayList,
LinkedList, HashSet, HashMap.
2) Fail-Safe Iterators
What is the meaning of Fail Safe
Fail-safe iterators don't throw
concurrentModificationException like fail-fast Iterator, if Collection is
modified structurally after taking iterator over collection. This is because
they work on clone or copy of the original collection instead of original
collection,so any modification done after iterator has been taken will be done
on original collection,however the copy which iterator
is referring is a snapshot taken when Iterator was taken over
collection.As we can modify the collection after iterator is taken,so it is
quite possible that iterator will be working on obsolete copy of the collection
specially in multi threaded environment,which can produce some
unwanted results later when the code is running in production.Also as every mutative operation(add,set and so on) leads to creation of fresh copy of underlying array,it will not be cost efffective to use copyOnWriteArrayList when you want to perform lots of mutative operations on list.
From Java Docs
"A
thread-safe variant of ArrayList in which all mutative operations(add,set
and so on) are implemented by making a fresh copy of the underlying array.This is
ordinarily too costly, but may be more efficient than
alternatives when traversal operations vastly outnumber mutations, and is
useful when you cannot or don't want to synchronize traversals, yet need to
preclude interference among concurrent threads. 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. Element-changing operations on iterators themselves(remove,set and
add) are not supported. These methods throw
UnsupportedOperationException.All elements are permitted, including null."
Please check Solution 2 above for
concurrentModificationException in Multithreaded enviorenment for example of
Fail safe Iterator(CopyOnWriteArrayList).
Which are the collections which are
having Fail Safe iterators
Iterators
of all the collections within java.util.concurrent package are fail safe.For
example : CopyOnWriteArrayList, CopyOnWriteHashSet, ConcurrentHashMap.
Hope this article was helpful to you.
For more collections tutorials you can go through below articles.Also I post on Google+ ,so you can add me in your circle to get updates
Hope this article was helpful to you.
For more collections tutorials you can go through below articles.Also I post on Google+ ,so you can add me in your circle to get updates
