ModCount is modCount, modCount is modCount, modCount is modCount, modCount is modCount, modCount is modCount. Let’s start with a quick example.

public static void main(String[] args){
    List<String> list= new ArrayList<>();
    list.add("java");
    list.add("kotlin");
    list.add("dart");

    for (String s:list){
        if (s.equals("dart")) list.remove(s); }}Copy the code

Most people should be done before, and then get a bright red ConcurrentModificationException, specific error stack information is as follows:

Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at collection.ArrayListTest.main(ArrayListTest.java:15)
Copy the code

The error location is the checkForComodification() method in the internal Itr class of ArrayList. As for how to call this method, we first learn what happens in the code on the outside. The class file is compiled by javac and then executed as follows:

./jad ArrayListTest.class
Copy the code

Arraylisttest. jad file, open it directly with a text editor:

public class ArrayListTest {

    public ArrayListTest(a) {}public static void main(String args[]) {
        ArrayList arraylist = new ArrayList();
        arraylist.add("java");
        arraylist.add("kotlin");
        arraylist.add("dart");
        Iterator iterator = arraylist.iterator(); / / 1
        do {
            if(! iterator.hasNext())/ / 2
                break;
            String s = (String)iterator.next(); / / 3
            if(s.equals("dart"))
                arraylist.remove(s);
        } while(true); }}Copy the code

From the decomcompiled code, we can see that the enhanced for loop is just a syntactic sugar that the compiler does for us. It actually calls the iterator to loop. Take a look at the three lines of code highlighted above, which are at the heart of the iteration.

First, get the iterator of the ArrayList.

public Iterator<E> iterator(a) {
    return new Itr();
}
Copy the code

AbstractList defines an iterator Itr, but its subclass ArrayList does not directly use the iterator of its parent class. Instead, it defines an optimized version of Itr. The second line of code in the body of the loop first checks if hasNext() is present, calls next to get the element, and jumps out of the loop if it isn’t. This is the basic implementation of the enhanced for loop. The hasNext() and next() methods are available as follows:

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    Itr() {}

    public boolean hasNext(a) {
        returncursor ! = size; }@SuppressWarnings("unchecked")
    public E next(a) {
        checkForComodification(); // Concurrent detection
        int i = cursor;
        if (i >= size) // Determine if the boundary is crossed
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) // Again, if the boundary is crossed, it may be caused by concurrent modification
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return(E) elementData[lastRet = i]; }...// omit other code
    }
Copy the code

Cursur represents the current cursor position, and hasNext() determines whether the cursor is equal to the set size to determine whether there is a next element. The member variable has an expectedModCount, which is defined as follows:

int expectedModCount = modCount;
Copy the code

Finally, the modCount is assigned to the expectedModCount variable, which literally means the expected number of changes. The first line of the next() method calls the checkForComodification() method, which is used for concurrent detection:

final void checkForComodification(a) {
    if(modCount ! = expectedModCount)// modCount changes during the iteration
        throw new ConcurrentModificationException();
}
Copy the code

This is how the exception is thrown. The modCount and the expectedModCount are not equal, that is, the actual number of changes is not equal to the expected number of changes. ExpectedModCount is assigned during iterator initialization and has a value equal to modCount. If they are not equal during the iteration, it is only possible that the set was modified during the iteration, causing modCount changes. So, what would cause modCount to change? The JDK source code comments say the following (modCount is declared in AbstractList) :

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.

The number of structural changes to the collection. Structural modifications refer to changes in the size of the collection. So modCount should be changed for any method that involves adding or removing elements. Take the remove() method of ArrayList:

public E remove(int index) {
    rangeCheck(index); // boundary detection

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0) // Move all elements after index
        System.arraycopy(elementData, index+1, elementData, index,
                        numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}
Copy the code

Increment it by 1 via modCount++.

Since ArrayLists are not thread-safe, iterating through collections while changing collections can indeed lead to inconsistent code performance across multiple threads. The test code at the beginning of this article does not involve concurrent operations, so why did it throw an exception? This is the fail-fast mechanism of collections.

The fail-fast mechanism does not guarantee that errors will occur, but it does allow exceptions to be thrown when errors do occur. It doesn’t care if you’re actually doing it concurrently, but if it’s possible to do it concurrently, it throws you an exception in advance. This is a robust way to handle collection classes that are not thread-safe. But what if you really want to do this in a single thread? It doesn’t matter, just make modCount and expectedModCount equal, and the ArrayList iterator gives us add() and remove() methods like this:

public void add(E e) {
    checkForComodification();

    try {
        int i = cursor;
        ArrayList.this.add(i, e); // Modify modCount after add
        cursor = i + 1;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw newConcurrentModificationException(); }}public void remove(a) {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        ArrayList.this.remove(lastRet); // modCount should be modified after remove
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw newConcurrentModificationException(); }}Copy the code

The above code implementation reassigns the expectedModCount to be equal to modCount after modifying the collection structure. Modify the test code at the beginning of this article:

public static void main(String[] args){
    List<String> list= new ArrayList<>();
    list.add("java");
    list.add("kotlin");
    list.add("dart");

// for (String s:list){
// if (s.equals("dart"))
// list.remove(s);
/ /}

    Iterator<String> iterator=list.iterator();
    while (iterator.hasNext()){
        String s= iterator.next();
        if (s.equals("dart")) iterator.remove(); }}Copy the code

So you don’t get any more errors.

Finally, one last question for you, take a close look:

public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("java");
    list.add("kotlin");
    list.add("dart");

    for (String s : list) {
        if (s.equals("kotlin")) list.remove(s); }}Copy the code

If you don’t see a difference from the question at the beginning of this article, look again. What we were going to delete was dart, the last element in the set. Now I’m going to delete kotlin, the second element in the set. What happens to the execution? If you were good at brain teasers, you’d be able to give the right answer. Yes, this time the element was successfully deleted without any exceptions. Why is that? If dart is deleted, an exception is reported, and if Kotlin is deleted, no problem. Is this discrimination against Dart? Take the iterator code out again:

public boolean hasNext(a) {
    returncursor ! = size; }@SuppressWarnings("unchecked")
public E next(a) {
    checkForComodification(); // Concurrent detection
    int i = cursor;
    if (i >= size) // Determine if the boundary is crossed
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length) // Again, if the boundary is crossed, it may be caused by concurrent modification
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}
Copy the code

ExpectedModCount = modCount = 3 and expectedModCount = 0 after the iterator is initialized because three elements are added to the set. Let’s start by examining the code at the beginning of this article to remove the last element in the collection:

  • After executing the first loop,cursorIs 1, no delete operation is generated,modCount3,expectedModCount3,size3.cursor ! = size.hasNext()And then there’s the element.
  • After executing the second loop,cursorIs 2, the delete operation is still not generated,modCount3,expectedModCount3,size3.cursor ! = size.hasNext()And then there’s the element.
  • After executing the third loop,cursorIs 3, because the deletion operation was generated,modCountIn 4,expectedModCountStill to 3,size2.cursor ! = size.hasNext()Determine there are elements, keep iterating, there are no elements.
  • Continue iterating, callingnext()Method, at this pointexpectedModCount ! = modCountThrow an exception directly.
cycles cursor modCount expectedModCount size
1 1 3 3 3
2 2 3 3 3
3 3 4 3 2

Let’s take a look at how to remove Kotlin:

  • After executing the first loop,cursorIs 1, no delete operation is generated,modCount3,expectedModCount3,size3.cursor ! = size.hasNext()And then there’s the element.
  • After executing the second loop,cursorIs 2, the delete operation is generated,modCountIn 4,expectedModCount3,sizeTo 2.cursor == size.hasNext()Determines there are no more elements and does not call againnext()Methods.

It is not that fail-fast has failed, it is just that hasNext() mistakenly thinks that there is no element left in the set. After two loops, the loop terminates, the next() method is no longer called, and there is no concurrent detection.

cycles cursor modCount expectedModCount size
1 1 3 3 3
2 2 3 3 2

In this paper, by an example of a ConcurrentModificationException, ultimately, parsing the ArrayList iterator source, at the same time shows the Java collections framework fail – fast mechanism. Finally, it is verified that deleting elements in enhanced for loops does not trigger fail-fast 100% of the time.

So much for ArrayList, the next article will take a look at the equally important LinkedList of Lists.

Article first published wechat public account: Bingxin said, focus on Java, Android original knowledge sharing, LeetCode problem solving.

More JDK source code analysis, scan code to pay attention to me!