【转】Fail-Safe|【转】Fail-Safe,Fail-Fast Iterators in Java and ConcurrentModificationException
原文链接：Fail-Safe,Fail-Fast Iterators in Java and ConcurrentModificationException
In this article ,I would try to explain FAIL-FAST and FAIL-SAFE behavior of iterators.
Let us first try to understand what is Iterator?
Iterator is an interface defined in java.util package,with following methods declared in it :
boolean hasNext();
E next();
void remove();
For details on above methods,please refer java docs link java.util.Iterator
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 list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
Iterator 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 list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
list.add("a");
List subList = new ArrayList();
Iterator 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 list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
list.add("a");
Iterator 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 list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
list.add("a");
List subList = new ArrayList();
Iterator 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 list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
list.add("a");
Iterator 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 list = new ArrayList();
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 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 list = new ArrayList();
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 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 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.So if tw
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Iterator;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
public class CMExceptionMultithreaded {
private static List list = new CopyOnWriteArrayList();
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 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 itrList = list.iterator();
while (itrList.hasNext()) {
String str = itrList.next();
System.out.println("Thread2:" + str);
}}
});
t2.start();
}
}
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 list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
Iterator 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 structurally modified.
* 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.
*
* 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
* fail-fast behavior, rather than non-deterministic behavior in
* the face of concurrent modification during iteration.
*
* Use of this field by subclasses is optional. 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;
Paste_Image.png 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.
Paste_Image.png 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.
Paste_Image.png 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.
Paste_Image.png expectedModCount of iteartor will still be 4.
Paste_Image.png Now when we will call next() method of Iterator ,it first calls method checkForComodification(),which is defined as below:
Paste_Image.png 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 my below articles.Also I post on Google+ ,so you can add me in your circle to get updates
ArrayListFeatures every Java developer must know
Various ways to Iterate over commonly Used collections vizArrayList,HashSet,HashMap
ArrayList Write Operations explored
【【转】Fail-Safe|【转】Fail-Safe,Fail-Fast Iterators in Java and ConcurrentModificationException】ArrayList Read Operations explored
