Interview FAQ collection traversal encountered when the pit ConcurrentModificationException analysis

You may be asked the right question in the interview Java Knowledge of the collection , And in-depth collection of the underlying source code , And if you encounter any pitfalls when using collections —— At this time, I want to see if you are careful in your daily work , It is generally not recommended to say , There was no pit , Because this will give the interviewer the feeling that we are not careful in our work , Not carefully .

today ConcurrentModificationException It should be a common exception . Especially for some students who have just joined the work , You may often meet . that , Have you had a detailed understanding of the underlying causes of this anomaly ？

Voice over , If you answer this question during the interview , It's very likely to face deep-seated problems about Java A group interview .

1. ordinary demo

Let's write a simple set traversal demo, To create a situation where ConcurrentModificationException An unusual scene .

/** * @Author One like you * @Date 2018/8/25 * @Description ConcurrentModificationException Abnormal explanation */ public class ConcurrentModificationExceptionDemo { public static void main(String[]args) { // Define a list List<String> list = new ArrayList<>(); // Add some elements list.add(" Zhang San "); list.add(" Li Si "); list.add(" Wang Wu "); list.add(" Zhao Liu "); // Get the iterator Iterator<String> iterator = list.iterator(); // Traverse list The elements in while (iterator.hasNext()) { // Each element in the collection String element = iterator.next(); // Delete Li Si if (" Li Si ".equals(element)) { list.remove(element); } } } }

function demo, You get the following exception ：

2. The cause of the exception is decrypted

2.1 ArrayList.iterator()

Take a look first ArrayList Class iterator() Method implementation , Source code is as follows ：

/**
* Returns an iterator over the elements in this list in proper sequence.
*
* <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator<E> iterator() {
return new Itr();
}

You can see from the source code ,iterator() The method is to return a Itr Class object . Look at the below Itr The specific implementation is as follows ：

/**
* 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();
}
}

Itr This class is not very complicated ,Itr Class is ArrayList One of the classes Private inner class . So you could say ,ArrayList Of iterator() The way is through Itr Class to work .

2.2 Inner class Itr analysis

Itr Class member variable parsing ：

·cursor： Represents the index of the next element to be accessed , from next() The concrete implementation of the method shows that .

·lastRet： Represents the index of the last accessed element .

·expectedModCount： Said to ArrayList Number of changes The expectation of , its The initial value is equal to modCount.

·modCount yes AbstractList A member variable in a class .PS： ArrayList Integrated AbstractList;Itr yes ArrayList The inner class of a class .

protected transient int modCount = 0;

This value is for ArrayList The number of changes , It can be found in add() and remove() In the method , Will be modified modCount.

Itr Class hasNext() Methods to analyze ：

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

If the subscript of the next accessed element is not equal to ArrayList Size , It means that there are elements that need to be accessed , This is easy to understand , If the subscript of the next access element equals ArrayList Size , Means to arrive ArrayList At the end .

Itr Class next() Methods to analyze ：

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];
}

This is a very critical place ： First, in the next() Method is called checkForComodification() Method , And then according to cursor Gets the value of the element , Also on cursor Add... To the value of 1 operation , And then cursor+1 The value of the previous original value is assigned to lastRet,. At the beginning ,cursor by 0,lastRet by -1, So after one call ,cursor The value of is 1,lastRet The value of is 0.

In this case , Into the next() The state after the method is shown in the following figure ： Note that this time ,modCount by 4,expectedModCount Also for the 4.

2.3 ArrayList.remove()

ArrayList.remove() The source code of the method is as follows ：

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);
return true;
}
}
return false;
}

You can see from the source code , Where element deletion is performed directly is not in this method , But in fastRemove() in . Look at the below fastRemove() Method source code ：

private void fastRemove(int index) {
modCount++;
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
}

stay fastRemove() In the method , First of all, modCount add 1 operation （ Because there was a change to the set ）, Then the next step is to delete the element , The final will be size Make a reduction 1 operation , And set the reference to null In order to facilitate the garbage collector for recycling work .

So in this case , The program is running remove() After the method , Notice the values of the variables at this point ： about iterator, Its expectedModCount by 4,cursor The value of is 1,lastRet The value of is 2.

2.4 checkForModification()

After execution list.remove() after , Will enter... Again while loop , Iterate over the next element .

PS： Be careful ！ here ,Itr Medium expectedModCount yes 4, however ,ArrayList inherited AbstractList Medium modCount = 5 了 ！

look down checkForComodification() The method is implemented as follows ：

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

The source code is very simple , Namely modCount and expectedModCount Throw one when it's not equal ConcurrentModificationException abnormal .

summary ： call list.remove() Methods lead to modCount and expectedModCount Is inconsistent . Be careful , Like use for-each It's actually the same problem with iterations .

3. Solution

Itr There is also a remove() Method , There will be no problem with this method . Look at the implementation of this method as follows ：

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();
}
}

This method is actually called ArrayList Of remove() Method , But the key thing is ： This method executes the last line ,expectedModCount = modCount The equivalence between them is modified .

therefore , If you want to delete an element in the iterator , Need to call Itr Class remove Method . Here's a good example ：

4. Expand

The first 3 The solution in this section is to solve the problem of single thread , But in the case of threads , Again, there will be anomalies , Multithreading Demo demo The code is as follows ：

Two threads are used to traverse list, The thread 2 Yes list Deleted , Look at the results of the test ：

The conclusion is that ： multithreading , Use iterator.remove() Or throw out ConcurrentModificationException abnormal .

Maybe some students said ArrayList It's a non thread safe container , Switch to Vector That's fine , In fact, instead of Vector There will still be this kind of mistake . although Vector The method adopted in this paper is synchronized Synced , But because of Vector Is inherited AbstarctList, So by Iterator To access the container , In fact, you don't need to get a lock to access . So clearly , Due to the use iterator Access to the container does not require a lock , In multithreading, when a thread deletes an element , because modCount yes AbstarctList Member variables of , So it can lead to in other threads modCount and expectedModCount It's not worth it . Interested students can try to use Vector modified , Here is the class diagram , No more code demonstrations .

5. extend

If a classmate is in an interview , Answer the above key points to , So congratulations , You can get this question 50 branch 了 .

Why only 50 branch ？？？ because , Next, the interviewer will talk to you about multithreading concurrent containers .

How to solve this problem in the case of multithreading ？？？

Unparalleled teacher gives ideas ：

（1） When using iterators , Use synchronized perhaps Lock To synchronize

（2） Using concurrency containers CopyOnWriteArrayList Instead of ArrayList or Vector