java.util.ConcurrentModificationException exception reason and solution

created at 02-14-2022 views: 8

problem

Goal: I want to delete elements in the collection during the loop traversal, but I encountered such an error when running the code: java.util.ConcurrentModificationException: null, which is a concurrent modification exception

error code

error

java.util.ConcurrentModificationException
...

reason

To put it simply, in the code of my project, the way of traversal is to enhance the for loop, and the iterator is also used at the bottom.

That is to say, it is traversed with Itr. This Itr is a traversal interface and inner class implemented by ArrayList.

But when I delete it, I use the remove method of ArrayList to operate, not the delete method inside Itr.

Then the question arises:

The remove method of ArrayList modifies the variable modCount inherited from AbstractList; while the remove method of Itr modifies its own variable expectedModCount. The role of these two variables is to record the number of modifications.

Therefore, after using the remove method of ArrayList to delete, the expectedModCount in Itr will be compared with the modCount of ArrayList, the two are not equal, so an error will be thrown.

process

Source code analysis

Here I wrote a code that is convenient to reproduce the problem:

import java.util.ArrayList;

class MyTest{
    public static void main(String[] args){
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i=0; i<10; i++){
            arr.add(i);
        }

        for(Integer i: arr){
            if(i == 5){
                arr.remove(i);
            }
            else{
                System.out.println(i);
            }
        }
    }
}

Run it and see the error:

C:\Users\hzy\Desktop>javac MyTest.java

C:\Users\hzy\Desktop>java MyTest
0
1
2
3
4
Exception in thread "main" java.util.ConcurrentModificationException
        at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1009)
        at java.base/java.util.ArrayList$Itr.next(ArrayList.java:963)
        at test.main(test.java:10)

ok, the error is Itr.next() and Itr.checkForCommodification() in ArrayList.java.

The Itr here is the inner class of ArrayList, which implements the Iterator interface for traversal.

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    ... ...

    /**
     * An optimized version of AbstractList.Itr
     */
    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;

        // prevent creating a synthetic constructor
        Itr() {}

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

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i < size) {
                final Object[] es = elementData;
                if (i >= es.length)
                    throw new ConcurrentModificationException();
                for (; i < size && modCount == expectedModCount; i++)
                    action.accept(elementAt(es, i));
                // update once at end to reduce heap write traffic
                cursor = i;
                lastRet = i - 1;
                checkForComodification();
            }
        }

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

The error is generated after calling checkForComodification() in Itr.next(). In the checkForComodification() function, it is judged whether modCount and expectedModCount are equal. If they are not equal, the exception we encountered will be thrown.

Obviously, our error is because these two variables are not equal.

        ... ...
        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
        ... ...
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

ok, what do these two variables mean?

  • modCount is an abbreviation of modification count, which is the number of times the current ArrayList has been modified. This variable is ArrayList inherited from AbstractList.

    In the IDE, hold down the Ctrl key, and then click the variable modCount with the mouse to jump to the place where it is defined~

  • expectedModCount is an abbreviation of expected modification count, which is the number of times expected to be modified. This variable is defined in the inner class Itr and is initially assigned modCount.

Ok, then why does our writing method cause these two variables to be inconsistent?

The thing to note here is that I call Itr.next() when I iterate, but when I remove elements in the loop, I use ArrayList.this.remove():

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    ... ...
    public boolean remove(Object o) {
        final Object[] es = elementData;
        final int size = this.size;
        int i = 0;
        found: {
            if (o == null) {
                for (; i < size; i++)
                    if (es[i] == null)
                        break found;
            } else {
                for (; i < size; i++)
                    if (o.equals(es[i]))
                        break found;
            }
            return false;
        }
        fastRemove(es, i);
        return true;
    }

    private void fastRemove(Object[] es, int i) {
        modCount++;
        final int newSize;
        if ((newSize = size - 1) > i)
            System.arraycopy(es, i + 1, es, i, newSize - i);
        es[size = newSize] = null;
    }
    ... ...

The remove() function calls the fastRemove() function, which increments the value of modCount by 1.

However, the next time the for loop calls Itr.next() and Itr.next() calls Itr.checkForCommodification(), it will find that the two values of modCount and expectedModCount are not equal! Since expectedModCount is not reassigned during this delete operation, an exception is thrown.

Solution

Change to the iteration method of Iterator, use the remove method of the inner class Itr to delete, to ensure consistency:

import java.util.ArrayList;

class MyTest{
    public static void main(String[] args){
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i=0; i<10; i++){
            arr.add(i);
        }

        for(Iterator<Integer> it=arr.iterator(); it.hasNext();){
            Integer i = it.next();
            if(i == 5){
                it.remove();
            }
            else{
                System.out.println(i);
            }
        }
    }
}

Decrement i by 1 each time you delete

import java.util.ArrayList;

class MyTest{
    public static void main(String[] args){
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i=0; i<10; i++){
            arr.add(i);
        }

        for(int i=0; i<arr.size(); i++){
            if(i == 5){
                arr.remove(i);
                i -= 1;
            }
            else{
                System.out.println(i);
            }
        }
    }
}

Delete in reverse order, first traverse the subscript to be deleted, and then delete from the end

In addition, ArrayList is a query-based data structure, and the bottom layer is implemented by an array, which itself is not suitable for frequent and concurrent modification scenarios.

For frequently modified, you can use LinkedList, for thread safety, you can use CopyOnWriteArrayList of JUC.

– Revised on 2021.4.11 (The following content was written in 2018…

Previous Analysis (2018)

Finally, I looked on the Internet and found that the deletion was performed during the loop, so an error was reported. The reason is: the values of expectedModCount and modCount of the iterator are inconsistent;

The recruitList in my code is an ArrayList, and the loop is an iterator to iterate (refer to the implementation principle of java forEach). So let's take a look at its iterator implementation method:

iterator

As you can see from the comments, what is returned is a reference to the correct sequence of objects of type Itr (@return an iterator over the elements in this list in proper sequence);

Then you can see the implementation of the inner class Itr: As can be seen from the comments:

  • cursor is the subscript of the next returned element;
  • lastRet is the index subscript of the last returned element;
  • expectedModCount: is the expected number of modifications to ArrayList, initialized to modCount; note that expectedModCount is a variable in the inner class Itr, and modCount is ArrayList inherits from A member variable of AbstractList
  • At the end of this inner class I see, if (modCount != expectedModCount) throw new ConcurrentModificationException(); which seems to be the problem; just what is this modCount?
/**
 * An optimized version of AbstractList.Itr
 */
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() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

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

In ArrayList.java, ctrl click modCount to find it, and find that modCount is a member variable of ArrayList inherited from AbstractList, indicating the number of modifications to List, from the comments, as long as there are changes , modCount will add 1; Then why does the remove() method in my code cause an exception? This can be seen in the next() method in the inner class Itr in ArrayList:

next() method

At the beginning, the checkForCommodification(); method will be called to check, initially, cursor is 0, lastRet is -1, after calling once, the value of cursor is 1, The value of lastRet is 0, modCount is 0, and expectedModCount is also 0. Let's see what the remove() method in the code does:

what remove method do

ArrayList.this.remove(lastRet) is called here;

  • For iterator, expectedModCount is 0, cursor is 1, and lastRet is 0;
  • for list, whose modCount is 1 and size is 0;

Then the next time you call the checkForCommodification() method, you will encounter a ConcurrentModificationException exception. The problem is: calling the list.remove() method causes the values of modCount and expectedModCount to be inconsistent

The values of modCount and expectedModCount are inconsistent Solved (2018)

My solution is to change to index traversal, but I need to ensure that the index is normal after deletion:

previous solution

created at:02-14-2022
edited at: 02-14-2022: