Fail-fast Iterators fail as soon as they realized that structure of Collection has been changed since iteration has begun.
The iterators returned by ArrayList's iterator and listIterator methods are fail-fast: if 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.
Implementation of fail-fast Iterators
AbstractList class contains a field protected transient int modCount,stores 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 iterator and listIterator methods. If the value of this field changes unexpectedly, the iterator (or list iterator) will throw a ConcurrentModificationException in response to the next, remove, previous, set or add operations. This provides fail-fast behavior, rather than non-deterministic behavior in the face of concurrent modification during iteration.
Let us see one example :
import java.util.*;
public class Main {
public static void main(String[] args) {
ArrayList list = new ArrayList();
list.add("one");
Iterator i = list.iterator();
list.add("two");
while(i.hasNext())
System.out.println(i.next());
}
}
The output is :
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:782)
at java.util.ArrayList$Itr.next(ArrayList.java:754)
at Main.main(Main.java:11)
The reason for this exception is that after the creation of the iterator i the structure of the list has been changed by adding one element "two" into it.
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 throw ConcurrentModificationException 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.
Fail-Safe Iterators
The fail-fast behavior of iterator is not mandatory for all the implementations of the Collection.You can implement Collection with fail-safe iterator by just ignoring the above mentioned modCount field.
Let us discuss about one fail-safe iterator implementation:
java.util.concurrent.CopyOnWriteArrayList<E>
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.
See the above example with CopyOnWriteArrayList class
import java.util.Iterator;
import java.util.concurrent.CopyOnWriteArrayList;
public class Main {
public static void main(String[] args) {
CopyOnWriteArrayList list = new CopyOnWriteArrayList();
list.add("one");
Iterator i = list.iterator();
list.add("two");
while (i.hasNext())
System.out.println(i.next());
}
}
The output is
one
You can see that ConcurrentModificationException is not thrown by the iterator even then the list structure has changed after the iterator creation.The iterator does not reflect the addition of an element "two" to the list since the iterator was created.
The iterators returned by ArrayList's iterator and listIterator methods are fail-fast: if 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.
Implementation of fail-fast Iterators
AbstractList class contains a field protected transient int modCount,stores 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 iterator and listIterator methods. If the value of this field changes unexpectedly, the iterator (or list iterator) will throw a ConcurrentModificationException in response to the next, remove, previous, set or add operations. This provides fail-fast behavior, rather than non-deterministic behavior in the face of concurrent modification during iteration.
Let us see one example :
import java.util.*;
public class Main {
public static void main(String[] args) {
ArrayList list = new ArrayList();
list.add("one");
Iterator i = list.iterator();
list.add("two");
while(i.hasNext())
System.out.println(i.next());
}
}
The output is :
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:782)
at java.util.ArrayList$Itr.next(ArrayList.java:754)
at Main.main(Main.java:11)
The reason for this exception is that after the creation of the iterator i the structure of the list has been changed by adding one element "two" into it.
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 throw ConcurrentModificationException 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.
Fail-Safe Iterators
The fail-fast behavior of iterator is not mandatory for all the implementations of the Collection.You can implement Collection with fail-safe iterator by just ignoring the above mentioned modCount field.
Let us discuss about one fail-safe iterator implementation:
java.util.concurrent.CopyOnWriteArrayList<E>
- Type Parameters:
E
- the type of elements held in this collection
- All Implemented Interfaces:
- Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccess
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.
See the above example with CopyOnWriteArrayList class
import java.util.Iterator;
import java.util.concurrent.CopyOnWriteArrayList;
public class Main {
public static void main(String[] args) {
CopyOnWriteArrayList list = new CopyOnWriteArrayList();
list.add("one");
Iterator i = list.iterator();
list.add("two");
while (i.hasNext())
System.out.println(i.next());
}
}
The output is
one
You can see that ConcurrentModificationException is not thrown by the iterator even then the list structure has changed after the iterator creation.The iterator does not reflect the addition of an element "two" to the list since the iterator was created.
Excellent Example . Marvelleous
ReplyDelete