1,foreach ergodic ArrayList Used in the process add and remove
Let's first look at the use foreach ergodic ArrayList Used in the process add and remove What will happen , Then analyze it again .
public static void main(String[] args) { List<Integer> list = new
ArrayList<>(); for (int i = 0; i < 20; i++) { list.add(i); } for (Integer j :
list) { if (j.equals(3)) { list.remove(3); } System.out.println(j); } }
Operation results ：
0 1 2 3 Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:911) at
java.util.ArrayList$Itr.next(ArrayList.java:861) at test.Test.main(Test.java:12)
The result was ConcurrentModificationException abnormal , Trace where the exception was thrown （ArrayList.java:911）
final void checkForComodification() { if (modCount != expectedModCount) throw
new ConcurrentModificationException(); }
This place tells us if modCount Not equal to expectedModCount
When , This exception message will be thrown , So what do these two parameters represent ? Why not when equal , There will be exceptions ?
2, find by hard and thorough search
2.1,modCount What is it? ?
At this time, let's go to see the source code , When we point to this variable , There will be notes to tell us modCount yes AbstractList
A member variable in a class , This value represents a pair of List Number of modifications .
Now let's have a look remove Whether this variable is increased or decreased in the method .
You can see , stay remove In the method of , Actually, it's just right modCount Carried out ++, that expectedModCount What is it ?
2.2,expectedModCount What is it? ?
expectedModCount yes ArrayList An inner class in ——Itr Member variables in , Let's see how to pull out another inner class Itr.
Through decompilation, you can find foreach After compilation, the internal is implemented using iterators .
Iterators are passed list.iterator() Instantiated ,list.iterator() An inner class is returned Itr Object of , You can see from the source code Itr Realized Iterator Interface , Also stated expectedModCount This member variable , expectedModCount
Express right ArrayList Expected number of modifications , Its initial value is modCount.
2.3, conversant checkForComodification method
You can see the of this class from the source code next and remove Method is called checkForComodification method , notice checkForComodification Are you familiar with it , Isn't that where the exception is thrown .
checkForComodification The method is through judgment modCount and expectedModCount Whether to throw concurrent modification exceptions is determined by equality .
2.4, Process review
By viewing the compiled class file , It can be seen that the general process is as follows ： When j by 3 Time , Called remove method ,remove Modified in method modCount value , Then output j value , Then enter the next cycle , here hasNext by true, Enter the first line of the loop , call next method ,next Method re call checkForComodification method , Then found expectedModCount and modCount atypism , Final throw ConcurrentModificationException
abnormal .
in other words ,expectedModCount Initialize as modCount Yes , But back expectedModCount Not modified , And in remove and
add Modified in the process of modCount , This leads to execution , adopt checkForComodification
Method to determine whether two values are equal , If equal , Then no problem , If not equal , Then throw you an exception .
And this is what we commonly say fail-fast mechanism , That is, fast detection failure mechanism .
3, avoid fail-fast mechanism
3.1, use listIterator or iterator
fail-fast Mechanisms can also be avoided , For example, take out the code above us
public static void main(String[] args) { List<Integer> list = new
ArrayList<>(); for (int i = 0; i < 5; i++) { list.add(i); }
System.out.println(" Before deleting an element "+list.toString()); // Iterator usage listIterator and iterator All right
ListIterator<Integer> listIterator = list.listIterator();
while(listIterator.hasNext()){ Integer integer = listIterator.next();
if(integer==3){ listIterator.remove(); listIterator.add(9); } }
System.out.println(" After deleting an element "+list.toString()); }
In that case , You'll find it works , There is no problem , Let's look at the running results ：
Before deleting an element [0, 1, 2, 3, 4] After deleting an element [0, 1, 2, 9, 4]
The results are also obvious , We achieved in foreach In progress add and remove Operation of .
Here's a note , Iterator usage listIterator and iterator All right , Look at the source code listIterator Actually used ListItr Inner class ,ListItr Yes Itr Class , At the same time, I sealed some methods , for example add,hasPrevious,previous wait . So in the code remove The method is Itr Class ,add The method is ListItr Class
listIterator and iterator difference ：
* Different scope of use ,Iterator Can be applied to all collections ,Set,List and Map And subtypes of these collections . and ListIterator Only for List And its subtypes .
* ListIterator have add method , Can to List Add objects to , and Iterator No .
*
ListIterator and Iterator Both hasNext() and next() method , Sequential backward traversal can be realized , however ListIterator have hasPrevious() and previous() method , Reverse can be achieved （ Sequential forward ） ergodic .Iterator may not .
* ListIterator You can locate the current index ,nextIndex() and previousIndex() Can achieve .Iterator This feature is not available .
* Can be deleted , however ListIterator Object modification can be realized ,set() Method can be implemented .Iterator Can only traverse , Cannot modify .
3.2, use CopyOnWriteArrayList
CopyOnWriteArrayList This class can also solve fail-fast Of the problem , Let's try ：
public static void main(String[] args) { CopyOnWriteArrayList<Integer> list =
new CopyOnWriteArrayList<>(); for (int i = 0; i < 5; i++) { list.add(i); }
System.out.println(" Before deleting an element "+list.toString()); for (Integer integer : list) {
if(integer.equals(3)){ list.remove(3); list.add(9); } }
System.out.println(" After deleting an element "+list.toString()); }
Operation results ：
Before deleting an element [0, 1, 2, 3, 4] After deleting an element [0, 1, 2, 4, 9]
CopyOnWriteArrayList It implements the operation of removing and adding this element , So how is his internal source code implemented , It's actually very simple , copy
That is, he creates a new array , Then copy the old array to the new array , But why is this practice rarely recommended , The root cause is still copy
Because you used replication , Then there must be two spaces for storing the same content , This consumes space , Finally GC
When , Does it take some time to clean him up , So I don't recommend it very much , But there is a need to write it out .
3.2.1,CopyOnWriteArrayList of add method
public boolean add(E e) { // Reentrant lock final ReentrantLock lock = this.lock; // Acquire lock
lock.lock(); try { // Element array Object[] elements = getArray(); // Array length int len =
elements.length; // Copy array Object[] newElements = Arrays.copyOf(elements, len +
1); // Store elements e newElements[len] = e; // Set array setArray(newElements); return true;
} finally { // Release lock lock.unlock(); } }
The processing flow is as follows ：
*
Acquire lock ( Secure access to multiple threads ), Get current Object array , obtain Object The length of the array is length, Go to step ②.
*
according to Object Copy an array with a length of length+1 of Object Array is newElements( here ,newElements[length] by null), Go to the next step .
*
Subscript as length Array element of newElements[length] Set as element e, Reset current Object[] by newElements, Release lock , return . This completes the addition of the element .
3.2.2,CopyOnWriteArrayList of remove method
public E remove(int index) { // Reentrant lock final ReentrantLock lock = this.lock; //
Acquire lock lock.lock(); try { // Get array Object[] elements = getArray(); // Array length int len
= elements.length; // Get old value E oldValue = get(elements, index); // Number of elements to be moved int
numMoved = len - index - 1; if (numMoved == 0) // The number of moves is 0 // Set array after copy
setArray(Arrays.copyOf(elements, len - 1)); else { // The number of moves is not 0 // Newborn array Object[]
newElements = new Object[len - 1]; // copy index Elements before index System.arraycopy(elements,
0, newElements, 0, index); // copy index Elements after index System.arraycopy(elements, index +
1, newElements, index, numMoved); // catalog index setArray(newElements); } // Return old value
return oldValue; } finally { // Release lock lock.unlock(); } }
The processing flow is as follows ：
* Acquire lock , Get array elements, Array length is length, Gets the value of the index elements[index], Calculate the number of elements to be moved (length -
index -
1), If the number is 0, Indicates that the last element of the array is removed , copy elements array , Copy length is length-1, Then set the array , Go to step ③; otherwise , Go to step ②
* Copy first index Elements before index , Re replication index Elements after index , Then set the array .
* Release lock , Return old value .
be careful
CopyOnWriteArrayList solve fail-fast
The problem is not through iterators remove or add Elemental , But through list Per se remove and add method , therefore add The position of the element is also different , The iterator is the next to the current position ,CopyOnWriteArrayList It's straight to the end .
Students with ideas can have a look CopyOnWriteArrayList of listIterator and iterator, It's actually the same , All are returned COWIterator Inner class .
stay COWIterator Not supported in inner class remove,set,add Operational , At least I use jdk1.8 Yes, not supported , Will be thrown directly UnsupportedOperationException abnormal ：
Write here first , I'll add later when I'm free .
Technology