Guide language:
I recently wrote a bug that I deleted an element in the list when iterating through it. Actually, I have read Ali’s Java development specification before, and I know that it will cause a problem to delete an element when iterating through it, but I still didn’t notice it when I wrote fast, so IT is good to study the mechanism in the list. Let’s take a look at what Ali’s specification says:
The fail-fast mechanism is a kind of error mechanism in Java Collection. Fail-fast events can occur when multiple threads operate on the contents of the same collection. For example, when thread A iterates through A collection, the contents of the collection are changed by other threads. Then thread A access to the collection, will throw ConcurrentModificationException, produce fail – fast. It is simply a Java mechanism to prevent concurrent exceptions, but it can also be generated in a single thread.
Case analysis:
Next, I’ll take a look at six examples of what happens when you delete an element while iterating through a list, and explore its source code. Create a list:
private List<String> list = new ArrayList<String>() {{
add(Elements of "1");
add("Element 2");
add("Three elements");
}};
Copy the code1. Plain old for loops
public void test1(a) {
for (int i = 0; i < list.size() - 1; i++) {
if ("Three elements".equals(list.get(i))) {
System.out.println("I found element three.");
}
if ("Element 2".equals(list.get(i))) { list.remove(i); }}}// It won't say find element 3 because iterating through element 2 removes element 2 and the size of the list becomes smaller
// There is a problem
Copy the code2. Another case of the for loop
public void test2(a) {
for (int i = 0; i < list.size() - 1; i++) {
if ("Element 2".equals(list.get(i))) {
list.remove(i);
}
if ("Three elements".equals(list.get(i))) {
System.out.println("I found element three."); }}}// It prints element 3, but it actually prints when iterating through element 2
// iterate over element 2 and delete to the condition of element 3 where I is 1 less than before
// The output is correct
Copy the codeEnhance the for loop
public void test3(a) {
for (String item : list) {
if ("Element 2".equals(item)) {
list.remove(item);
}
if ("Three elements".equals(item)) {
System.out.println("I found element three."); }}}// The result here is slightly different from the above but there is still no print statement for element 3
// Decompile the Java file to see why
public void test3(a) {
Iterator var1 = this.list.iterator();
while(var1.hasNext()) {
// To show the difference here
String var2 = (String)var1.next();
if ("Element 2".equals(var2)) {
this.list.remove(var2);
}
if ("Three elements".equals(var2)) {
System.out.println("I found element three."); }}}Copy the codeThe decompilated file can see that the enhanced for decompilation uses an iterator to see if there are any more elements, and remove uses a list method. Let’s look at hasNext(),next() in the ArrayList. The following is the inner class Itr in ArrayList that implements the Iterator interface.
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();
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(a) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw newConcurrentModificationException(); }}@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(a) {
if(modCount ! = expectedModCount)throw newConcurrentModificationException(); }}Copy the codeCursor = I + 1 when next() is executed, so when running to “element 2”. Equal (item), element 2 is removed, HasNext () cursor == size; hasNext() cursor == size;
4.foreach
public void test4(a) {
list.forEach(
item -> {
if ("Element 2".equals(item)) {
list.remove(item);
}
if ("Three elements".equals(item)) {
System.out.println("I found element three."); }}); }Thrown here / / we are looking forward to have fail - fast Java. Util. ConcurrentModificationException
Copy the codeCheck out the source code for ArrayList
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if(modCount ! = expectedModCount) {throw newConcurrentModificationException(); }}Copy the codeIf (modCount! = expectedModCount) { throw new ConcurrentModificationException(); }, so where did this modCount element come from? So let’s find AbstractList, which is the parent of ArrayList. Look inside the source code is how to say
/**
* The number of times this list has been <i>structurally modified</i>.
* 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.
*
* <p>This field is used by the iterator and list iterator implementation
* returned by the {@code iterator} and {@code listIterator} methods.
* If the value of this field changes unexpectedly, the iterator (or list
* iterator) will throw a {@code ConcurrentModificationException} in
* response to the {@code next}, {@code remove}, {@code previous},
* {@code set} or {@code add} operations. This provides
* <i>fail-fast</i> behavior, rather than non-deterministic behavior in
* the face of concurrent modification during iteration.
*
* <p><b>Use of this field by subclasses is optional.</b> If a subclass
* wishes to provide fail-fast iterators (and list iterators), then it
* merely has to increment this field in its {@code add(int, E)} and
* {@code remove(int)} methods (and any other methods that it overrides
* that result in structural modifications to the list). A single call to
* {@code add(int, E)} or {@code remove(int)} must add no more than
* one to this field, or the iterators (and list iterators) will throw
* bogus {@code ConcurrentModificationExceptions}. If an implementation
* does not wish to provide fail-fast iterators, this field may be
* ignored.
*/
protected transient int modCount = 0;
Copy the codeStudents who are good at English can take a look by themselves, while those who are not good at English can open Google Translate or Youdao Dictionary silently.
For the rest of you, just look at the first paragraph and you’ll almost know what it does. This field records the number of structural changes to the list (add, remove). If it is returned to throw ConcurrentModificationException caused by other ways. So let’s take a look at the add and remove methods of a subclass’s ArrayList.
// This is the submethod in add
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// remove(int index)
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
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
return oldValue;
}
// This is remove(Object o)
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
}
Copy the codeModCount++ = modCount++ = modCount++ Yes, modCount is incremented by one when adding and removing. Okay, let’s go back and see why test4() throws an exception. First of all, we know that there are three elements in the list so modCount is 3 when it’s done adding elements. Then it starts iterating, and when it finds element 2, it removes element 2, and modCount becomes 4. We’ll get to ArrayList later
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if(modCount ! = expectedModCount) {throw newConcurrentModificationException(); }}Copy the codeYou can see that modCoun is assigned to the expectedModCount, and then both the for loop and the final if condition break the modCount. If the modCount and the expectedModCount are not equal in the if loop, an exception is thrown. When traversing element 2, action.accept(elementData[I]); When this line is finished, the loop is rolled out because modCount == expectedModCount is not equal, so it does not print out that element 3 is found and the exception is thrown when the if condition is executed.
5. The iterator
Let’s look at the correct way to use it, using iterators
public void test5(a) {
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String temp = iterator.next();
if ("Element 2".equals(temp)) {
iterator.remove();
}
if ("Three elements".equals(temp)) {
System.out.println("I found element three."); }}}// It prints out element 3
Copy the codeWe saw the code for this iterator in test3 above, so why does it work? In fact, the principle is very sand sculpture, do not believe you see!
This is the remove method of the iterator
public void remove(a) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
ExpectedModCount = expectedModCount (expectedModCount
} catch (IndexOutOfBoundsException ex) {
throw newConcurrentModificationException(); }}Copy the codeSo it can find element 3, because remove directly ignores modCount.
6.removeIf
Jdk8 also provides a new way to encapsulate the removal of elements while traversing them, removeIf(), as follows:
list.removeIf(item -> "Element 2".equals(item)
Copy the codeIf YOU click on it, you can see that the code is pretty much the same as the last one but it’s just one layer wrapped around it.
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true; }}return removed;
}
Copy the codeConclusion:
1. We explored several ways to delete elements repeatedly and learned the basic concept of Fail-Fast. 2. Learned after traversal when removing elements to use iterators oh, and find that even a single thread can still throw ConcurrentModificationException. 3. Use CopyOnWriteArrayList for multithreaded lists, or lock iterators, depending on your preferences