Collection throws or doesn't throw ConcurrentModificationException based on the contents of the Collection [duplicate]

Question

The following Java code throws a ConcurrentModificationException, as expected:

public class Evil
{
    public static void main(String[] args) {
        Collection<String> c = new ArrayList<String>();
        c.add("lalala");
        c.add("sososo");
        c.add("ahaaha");
        removeLalala(c);
        System.err.println(c);
    }
    private static void removeLalala(Collection<String> c) 
    {
        for (Iterator<String> i = c.iterator(); i.hasNext();) {
            String s = i.next();
            if(s.equals("lalala")) {
                c.remove(s);
            }
        }
    }
}

But the following example, which differs only in the contents of the Collection, executes without any exception:

public class Evil {
    public static void main(String[] args) 
    {
        Collection<String> c = new ArrayList<String>();
        c.add("lalala");
        c.add("lalala");
        removeLalala(c);
        System.err.println(c);
    }
    private static void removeLalala(Collection<String> c) {
        for (Iterator<String> i = c.iterator(); i.hasNext();) {
            String s = i.next();
            if(s.equals("lalala")) {
                c.remove(s);
            }
        }
    }
}

This prints the output "[lalala]". Why doesn't the second example throw a ConcurrentModificationException when the first example does?

Answer 1

Short answer

Because the fail-fast behavior of an iterator isn't guaranteed.

Long answer

You're getting this exception because you cannot manipulate a collection while iterating over it, except through the iterator.

Bad:

// we're using iterator
for (Iterator<String> i = c.iterator(); i.hasNext();) {  
    // here, the collection will check it hasn't been modified (in effort to fail fast)
    String s = i.next();
    if(s.equals("lalala")) {
        // s is removed from the collection and the collection will take note it was modified
        c.remove(s);
    }
}

Good:

// we're using iterator
for (Iterator<String> i = c.iterator(); i.hasNext();) {  
    // here, the collection will check it hasn't been modified (in effort to fail fast)
    String s = i.next();
    if(s.equals("lalala")) {
        // s is removed from the collection through iterator, so the iterator knows the collection changed and can resume the iteration
        i.remove();
    }
}

---

Now to the "why": In the code above, notice how the modification check is performed - the removal marks the collection as modified, and next iteration checks for any modifications and fails if it detects the collection changed. Another important thing is that ArrayList (not sure about other collections) does not check for modification in hasNext().

Therefore, two strange things may happen:

• If you remove the last element while iterating, nothing will be thrown
  • That's because there's no "next" element, so the iteration ends before reaching the modification-checking code
• If you remove the second-to-last element, ArrayList.hasNext() will actually also return false, because the iterator's current index is now pointing at the last element (former second-to-last).
  • So even in this case, there's no "next" element after the removal

---

Note that this all is in line with ArrayList's documentation:

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.

Edited to add:

This question provides some information on why the concurrent modification check is not performed in hasNext() and is only performed in next().

Answer 2

If you look at the source code for the ArrayList iterator (private nested class Itr), you'll see the flaw in the code.

The code is supposed to be fail-fast, which is done internally in the iterator by calling checkForComodification(), however the hasNext() doesn't make that call, likely for performance reasons.

The hasNext() instead is just:

public boolean hasNext() {
    return cursor != size;
}

This means that when you're on the second last element of the list, and then remove an element (any element), the size is reduced and hasNext() thinks you're on the last element (which you weren't), and returns false, skipping the iteration of the last element without error.

OOPS!!!!