Wednesday, September 13, 2023

Difference between fail-safe vs fail-fast Iterator in Java? Example

The difference between fail-safe and fail-fast Iterator is becoming favorite core java interview questions day by day, the reason it touches concurrency a bit, and the interviewee can go deep on it to ask how fail-safe or fail-fast behavior is implementedIn this article, we will see what are fail-safe and fail-fast iterators in java and the differences between fail-fast and fail-safe iterators. The concept of the fail-safe iterator is relatively new in Java and was first introduced with Concurrent Collections in Java 5 like ConcurrentHashMap and CopyOnWriteArrayList.

 

Difference between fail-fast Iterator vs fail-safe Iterator in Java

Without wasting any more of your time, here is some important points to know about both fail-safe and fail-fast iterators in Java.


1. fail-fast Iterators in Java

As the name suggests fail-fast Iterators fail as soon as they realized that structure of the Collection has been changed since iteration has begun. Structural changes mean adding, removing or updating any element from the collection while one thread is Iterating over that collection. 

The fail-fast behavior is implemented by keeping a modification count and if the iteration thread realizes the change in modification count it throws ConcurrentModificationException.



Java doc says this is not a guaranteed behavior instead its done of "best effort basis", So application programming can not  rely on this behavior. 

Also since multiple threads are involved while updating and checking modification count and this check is done without synchronization, there is a chance that the Iteration thread still sees a stale value and might not be able to detect any change done by parallel threads.

Iterators returned by most of the JDK1.4 collection are fail-fast including Vector, ArrayList, HashSet, etc. to read more about Iterator see my post What is Iterator in Java.

2. fail-safe Iterator in java

Contrary to fail-fast Iterator, the fail-safe iterator doesn't throw any Exception if Collection is modified structurally while one thread is Iterating over it because they work on a clone of Collection instead of the original collection and that’s why they are called a fail-safe iterator. 

Iterator of CopyOnWriteArrayList is an example of a fail-safe Iterator also iterator written by ConcurrentHashMap keySet is also a fail-safe iterator and never throw ConcurrentModificationException in Java.

If you like to see the difference in tabular format, here is a nice table highlighting difference between fail-safe and fail-fast Iterator in Java:

Difference between fail-safe vs fail-fast Iterator in Java? Example


Difference between fail-safe vs fail-fast iterator in javaThat’s all on the difference between fail-safe vs fail-fast Iterator in Java, As I said due to there confusing or not to easy differentiation they are quickly becoming popular java collection questions asked on various level of java interview. Let me know if you are aware of any other difference between fail-fast and fail-safe iterator.


Other Core Java Interview questions you may like

Thanks for reading this article so far. If you have been ask this core Java question on interviews, then please let us know, if you have any thing to add or any doubt feel free to ask I will try my best to answer your queries. 

20 comments:

  1. Structural changes means adding or removing. Updating any element from collection is not structural change.

    Please check as I found on net at many places this definition.

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. 1) Please give example code of ConcurrentModificationException
    2) How it happens?
    3) How we can avoid the ConcurrentModificationException in the code?

    ReplyDelete
  4. CopyOnWrite concept is useful only when thread need copy of collection for read purpose.

    ReplyDelete
  5. Hey mate, what is difference between fail-fast and weekly consistent iterator? does fail-safe and weekly consistent iterator refers to same thing? As you pointed out that iterators of many concurrent collections e.g. ConcurrentHashMap and CopyOnWriteArrayList are fail-safe, which I have read somewhere that they are also weekly consistent with original collection.

    ReplyDelete
  6. Hi

    very nice article. But i would suggest you to correct the statement : "Structural changes means adding, removing or updating any element from collection while one thread is Iterating over that collection".

    Structural change does not include updating element. So, for example, while iterating over HashMap, if we update 'value' object for a key using put() operation, then this is not a structural change and ConcurrentModificationException is not thrown. The reason being that modCount variable is not incremented when we update 'value' object for an existing key.

    Here is Java HashMap put() implementation :

    public V More ...put(K key, V value) {
    387 if (key == null)
    388 return putForNullKey(value);
    389 int hash = hash(key.hashCode());
    390 int i = indexFor(hash, table.length);
    391 for (Entry e = table[i]; e != null; e = e.next) {
    392 Object k;
    393 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    394 V oldValue = e.value;
    395 e.value = value;
    396 e.recordAccess(this);
    397 return oldValue;
    398 }
    399 }
    400
    401 modCount++;
    402 addEntry(hash, key, value, i);
    403 return null;
    404 }

    So, modCount is incremented only when a new key-value pair is added, and not for updating an existing entry.

    Best regards, Achint Mittal

    ReplyDelete
  7. public class FailFastTest {
    public static void main(String[] args) {

    ArrayList nameList = new ArrayList();
    nameList.add("praveen");
    nameList.add("ravi");
    nameList.add("javarevisited");
    nameList.add("chinni");

    Iterator itr = nameList.iterator();
    while (itr.hasNext()) {
    String string = (String) itr.next();
    int temp = string.indexOf(string);
    if ("javarevisited".equals(string)) {
    nameList.remove(temp);
    }
    System.out.println(string);
    }
    }
    }
    Console:
    praveen
    ravi
    john
    javarevisited
    Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
    at java.util.ArrayList$Itr.next(Unknown Source)
    at com.failfast.component.FailFastTest.main(FailFastTest.java:24)

    ReplyDelete
  8. @Javin nice article one very important thing that is missing Ithat I want to highlight is that..

    you look at the code for a Collection implementation, lets pick ArrayList; we have a modCount variable declared in AbstractList:

    protected transient int modCount = 0;

    And then in each and every modifying method (for example remove) for the ArrayList we have

    public E remove(int index) {
    rangeCheck(index);

    modCount++;
    //....

    So the modCount is only ever incremented; it is never decremented.

    In the Iterator we then have:

    final void checkForComodification() {
    if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
    }

    Where expectedModCount is a snapshot of the modCount taken at Iterator creation.

    So if there is any modification to the underlying List while the same instance of an Iterator is in use then a ConcurrentModificationException will be thrown.

    I suppose there is a corner case where if you carried out enough modifications then the int would overflow and return to it's original value again - this would be a rather large number or modifications however; 232 to be precise.

    ReplyDelete
  9. Your code for Concurrent modification exception is not showing it

    ReplyDelete
  10. Very nice , when we use fail fast and fail safe iterator ,?

    ReplyDelete
  11. Nice blog, very helpful

    ReplyDelete
  12. CopyOnWriteArrayList is fail-safe, it means it create new copy of list when there is any changes in list. In that case how data is consistent between multiple threads if thread is operating on a separate copy of List.
    Please explain

    ReplyDelete
  13. Can someone explain why the following code is not throwing ConcurrentModificationException ?

    ArrayList al = new ArrayList();
    al.add("AA");
    al.add("AB");
    al.add("AC");
    Iterator it = al.iterator();
    while(it.hasNext()){
    String s = it.next();
    if(s.equals("AB")){
    al.remove(1);
    }
    }

    I am getting the ConcurrentModificationException if I remove the "if" condition.

    ReplyDelete
  14. Hello @james, you are getting ConcurrentModificationException because you are calling ArrayList's remove method i.e. al.remove(1) inside the if block.

    While iterating you should always use Iterator's remove method to remove element e.g. it.remove(), this will remove current element, not the first one.

    See my post how to avoid ConcurrentModificationException in Java for more details.

    ReplyDelete
  15. Hi Javin, thanks for your reply. But the question was I am getting ConcurrentModificationException only when I remove the "if" condition from the above code. It's running fine otherwise, why ?(I was trying some sample code and I came across it)

    ReplyDelete
  16. Hello james, because there would not be any string which is equal to "AB" in your ArrayList, so it won't be going inside if block, you can check that by putting a System.out.println("removing element") in the if block.

    As soon as al.remove(1); is executed while iterating it will throw ConcurrentModificationException in Java.

    ReplyDelete
  17. @Javin, Hi regarding your reply to james doubt. actually there is an element with value "AB" and the cursor is entering the if block, the modCount is changing to 4 after removing element, but still it is not throwing ConcurrentModificationException exception . Please kindly explain it. moreover, it throws java.lang.IllegalStateException if i try to remove by using it.remove().

    Thanks in advance

    ReplyDelete
  18. seems like there is a bug with consistency of ConcurrentModificationException... as if i write code like this,
    if(s.equals("AC")){ al.remove("AC"); }
    then while loop iterates 4 times...& at 4th time it throws Concurrent exception...
    Ideally it should iterate 3 times only.
    So i think dynamic state change of arraylist size is affecting consistency of Iterator itself & so exception messages are inconsistent...

    ReplyDelete
  19. @Shashi Kumar That IllegalStateException is because of you not reading the element using iterator.next() before trying iterator.remove().
    So if you have your code like

    it.next();
    while(it.hasNext()){
    System.out.println("Done");
    it.remove();
    }
    You will get the output as
    Done
    Done

    which clearly shows that the first loop or rather the first it.remove() was successful as we had already done it.next() which before the loop which had landed the iterator to reference the first object.
    After the removal, there is no other it.next() and the iterator remains at the same position and so if you try to delete an element when there isn't any, in the second iteration, you get IllegalStateException thrown.

    Although I do not understand why james's code doesn't run yet it seems like removing the element after it had been read doesn't cause any problem as it must have because modificationCount was still changed and so ConcurrentModificationException must have been thrown.

    ReplyDelete
  20. The behavior described by @james is a bug in the JDK. Basically, removing any element from the list during the second-to-last iteration will cause hasNext() to return false and don't call next() again, thus never calling checkForComodification(), which is the method responsible for throwing ConcurrentModificationException.

    Although Oracle has acknowledged the bug, they also confirmed that it will never be fixed because "the change has demonstrated the potential to have significant compatibility impact upon existing code. (The 'compatibility impact' is that the fix has the potential to replace silent misbehavior with a ConcurrentModificationException)".

    See the official bug report with examples here:
    https://bugs.java.com/bugdatabase/view_bug.do?bug_id=4902078

    ReplyDelete