First, local environment

  • Editor: IntelliJ IDEA 2017

  • JDK version: JDK 1.8

Second, the phenomenon caused

In some businesses, we will iterate through the collection and remove the elements that need to be removed, and may remove multiple elements. For example, when managing a group and kicking people, the business logic of kicking people is probably to go through the relationships of the group, find the person to kick and remove him.

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");

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

So a piece of code like this, it throws an exception

java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
	at java.util.ArrayList$Itr.next(ArrayList.java:851)
	at com.lonelycountry.test3.Test1.test3(Test1.java:68)
Copy the code

But some of you are lucky enough to have written the following code, which cleverly or accidentally avoids this trap

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");

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

Iii. Solutions

1. Add a break to the code that deletes the internal elements of the collection only once

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");

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

2. Use iterators

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");

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

Four, view the source code to find problems

1, traversal method source (ArrayList as an example)

Use a for loop iterates through the collection and use iterators iterate through the set to use the same method, in the ArrayList class have an internal class implements the Iterator interface, there is a call next () method is traversal methods (cutting only a part of the way).

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess.Cloneable.java.io.Serializable {
    private class Itr implements Iterator<E> {
        public E next(a) {
            checkForComodification();// This is where the exception is thrown
            // The bottom is normal cursor movement
            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]; }}}Copy the code

The first line of the next() method calls the checkForComodification() method, which is used to verify that there are no illegal operations.

final void checkForComodification(a) {
    ModCount++ = modCount++ = modCount++
    // When a method is called, the predicted operands and the actual operands are not synchronized
    if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
}
Copy the code

2, ArrayList itself remove(Object O) method source analysis

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess.Cloneable.java.io.Serializable {
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true; }}else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index); // Focus on this method
                    return true; }}return false;
    }
    
    private void fastRemove(int index) {
        modCount++; // this is what causes ！！！！
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        elementData[--size] = null; // clear to let GC do its work}}Copy the code

In the remove(Object O) method, the index to be deleted is found. After the index is valid, the fastRemove(int Index) method is executed. The first step of the method is to +1 the actual operand and then perform the array operation, while the expectedModCount does not change. It is expected that when the next() method is executed, the checkForComodification() method will definitely throw an exception.

public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos, 
    int length);
Copy the code

The arrayCopy () method of the System class is used for group operations. The underlying call should be C or C++ (I guess). I checked the documentation and explained the logic.

Index srcPos, length srcPos, and then overwrite the destPos position in dest. But why in the operation group with such a complex method I do not know, there is a master of the algorithm SAO years can guide me oh.

3, ArrayList iterator inner class remove() method source analysis

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess.Cloneable.java.io.Serializable {
    private class Itr implements Iterator<E> {
        public void remove(a) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

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

This method essentially calls the remove(int index) method of the ArrayList itself, but secretly synchronise the actual operands with the predicted operands because this line of logic causes the iterator to iterate over the delete without throwing an exception. You must be wondering why you don’t add a line to the Remove (Object O) method if you know why. This is not possible because the variable expectedModCount is a variable in the Itr inner class and the Remove (Object O) method is declared outside the ArrayList class. Cannot manipulate variables that interfere with inner classes.

Five, the summary

This paper mainly analyzes the code differences between the two traversal sets, and the locations and causes of errors. There is also the puzzle of why the system.arrayCopy () method is used when calling the fastRemove(int index) method.