π This article all text pure original, if need to reprint, please indicate the source of reprint, thank you! π
Question origin
The reason why I wanted to write this article today was purely by chance. Last night, a member of the wechat technology group @me asked me a question. The code is as follows. He asked me, “Is there a problem with writing this way? Is there an error?” Then he said that he could not answer the question given by the interviewer who had interviewed him today. π
public class CollectionDemo {
public static void main(String[] args) {
List list = new ArrayList();
list.add("1");
list.add("3");
list.add("5");
for (Object o : list) {
if ("3".equals(o)) list.remove(o); } System.out.println(list); }}Copy the codeI didn’t think about it at the time. It seemed like a simple question, π, but on closer inspection, this is a list remove method in an enhanced for loop. If you’re gay and java-literate, you know that when iterating through a collection of elements, if you want to delete or modify elements in the collection, you must use the iterator method, never the collection itself. I’ve always taken that as an iron rule. So I decided that there was something wrong with the code and that it was bound to report an error. Then I snap a fierce operation such as tiger, the code knocked again, a run…… The following output is displayed:
The result was stunned, unexpectedly normal output error, and the result is correct! So I changed the code again as follows:
public class CollectionDemo {
public static void main(String[] args) {
List list = new ArrayList();
list.add("1");
List.add ("3"); list.add("3"); I added this line before
list.add("2");
list.add("3");
list.add("5");
for (Object o : list) {
if ("3".equals(o)) list.remove(o); } System.out.println(list); }}Copy the codeThe following output is displayed:
It turned out to be correct.
So I changed the code again as follows:
public class CollectionDemo {
public static void main(String[] args) {
List list = new ArrayList();
list.add("1");
list.add("2");
list.add("3");
// The rest of the code is unchanged, just add this line after list.add("3")
list.add("4");
list.add("5");
for (Object o : list) {
if ("3".equals(o)) list.remove(o); } System.out.println(list); }}Copy the codeThe following output is displayed:
This time, there was a long-awaited error.
Is it really strange that there will be such a different result? ! This made me realize the seriousness of the problem, which was not as simple as I had understood before. In addition to his character of breaking the pot to ask the bottom, so I decided to do a good study, incidentally write something, on the one hand, I can review later, but also can exchange technology with various leaders, isn’t it a pleasure? π
Source code analysis
ConcurrentModificationException
After all, since the program throws this exception, of course it needs to be sorted out first. Adhering to the learning technology at the official documentation 2 see the habit of source code, I will look at the javadoc ConcurrentModificationException, the original is very long, this part of the key, interested can read the JDK source code for yourself.
/** * This exception may be thrown by methods that have detected concurrent * modification of an object when such modification is not permissible. * For example, it is not generally permissible for one thread to modify a Collection * while another thread is iterating over it.Some Iterator * implementations (including those of all the general purpose collection implementations * provided by the JRE) may choose to throw this exception if this behavior is * detected. Iterators that do this are known as fail-fast iterators, * as they fail quickly and cleanly, rather that risking arbitrary, * non-deterministic behavior at an undetermined time in the future. * Note that this exception does not always indicate that an object has * been concurrently modified by a different thread. If a single * thread issues a sequence of method invocations that violates the * contract of an object, the object may throw this exception. For * example, if a thread modifies a collection directly while it is * iterating over the collection with a fail-fast iterator, the iterator * will throw this exception. */
Copy the codeThis exception may be raised when an object is detected to have made an illegal concurrent change. For example, JDK collections often have a fail-fast iterator built into them that will be thrown when the collection detects such an illegal concurrent change. The so-called Fail-fast, as the name implies, means that when an exception is detected, the sooner the exception is thrown, the better it is to avoid unknown risks in the future. This exception does not only occur in the case of concurrent modification by multiple threads, but also in the case of single threads.
But it didn’t work. I was still confused after reading the document. What the hell is that all about?
It doesn’t matter, the console not only throws this exception, but also prompts the location of the exception, the checkForComodification() method inside java.util.arrayList $ITr.next (). Navigate to the specified location of the ArrayList source code, as shown below:
The logic of this approach is very simple.
Where is the modCount and expectedModCount? Then come to the place that defines them.
modCount
ModCount is an attribute defined in AbstractList (the parent of ArrayList). The Javadoc for this property is also quite long, so I’ll pick out a few to show you.
/** * 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><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 codeThe value of this field is used to record the number of structural operations on the list. What are structural operations? Operations that affect the size of the List or that result in incorrect results during iteration. A subclass can use the value of this field to implement Fail-fast. To implement fail-fast, modCount++ operations need to be done inside all structural operations, and only once can be added inside each method. You don’t need this value if you don’t want to implement Fail-fast. For example, the add method of ArrayList has modCount++, as shown below:
expectedModCount
Take a look at the expectedModCount. ExpectedModCount is a property defined in java.util.ArrayList$Itr and takes the modCount value of the ArrayList as its initialization value.
Does that make you feel something? Normally, when the ArrayList is initialized, the built-in Itr is initialized as well, and the expectedModCount is the same as the modCount. If there is no iterative operation, nature is not appear inconsistent problems, also won’t throw ConcurrentModificationException. So why does our program cause these two values to be inconsistent? At this point, I’m at my wit’s end without using debug. Because we use an enhanced forEach loop in our program, forEach can be seen as a SYNTAX sugar in the JDK, and the underlying implementation is using iterators. So for clarity, we put breakpoints on all the java.util.ArrayList$Itr methods. The diagram below:
Let’s start debugging with the last error from the first three examples.
We started with 5 elements added to the list, size is equal to 5. The add operation is structural and results in modCount++.
The Itr iterator’s cursor value starts at 0 and moves as the element is traversed. HasNext () determines cursor! = size to see if there’s another element in the list to fetch. If true is returned, next() is used to return the next element.
Obviously we have five elements that we can go to next(). In the next method, the first line of code is checkForComodification() to verify the consistency between expectedModCount and modCount. Obviously, we haven’t done any additional structural operations on the List since we added elements to the List. Naturally, the first three iterations don’t throw exceptions and return elements normally. It’s all shown here.
And after each execution of next(), the cursor moves back one bit in preparation for iterating over the next element.
This is the time to iterate over the third element “3”. If the condition is determined to be true, the deletion operation will be performed.
ModCount++ is indeed found in the remove() method source code. That is, at this point modCount has changed to 6. ExpectedModCount still holds its initial value of 5. Now they don’t agree.
Since there are two elements “4” and “5” after “3”, the iterator will continue to iterate after “3” is deleted, and the previous process will be repeated. HasNext () will be entered first. At this point, the cursor is equal to 3 and size is equal to 4. So I still go to next() and get the next element.
Can be expected at this point checkForComodification () calibration expectedModCount and modCount has been inconsistent, so I throw ConcurrentModificationException.
Preliminary summary
That is, calling a structural operation on the collection in a forEach or iterator causes the modCount value to change, while the value of the expectedModCount is still the initialization value, so the test in next() does not pass a throw exception. This is why, when I first learned iterators, I was asked to use the remove method of iterators instead of using the remove operation of collections during iterator iteration. Why shouldn’t we get an error using the remove method that comes with iterators? The following code:
public class CollectionDemo {
public static void main(String[] args) {
List list = new ArrayList();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
for (Iterator it = list.iterator(); it.hasNext(); ) {
if ("3".equals(it.next())) it.remove(); } System.out.println(list); }}Copy the codeThis is the correct posture taught by the teacher. The result is certainly correct.
Revisited den
To understand the difference, of course, you need to dig deep into the tiger’s den and look at the source code for the List iterator remove method. Arraylist.this. remove this is a call to the remove method of the external ArrayList class. As mentioned above, the remove method of the collection is a structural operation that results in modCount++, ExpectedModCount and expectedModCount are subject to an error when calling next() when iterating over the next element. So the next line expectedModCount = modCount updates the expectedModCount to the latest value of modCount so that the consistency is not broken. This is why using the iterator’s built-in remove method does not throw an exception.
How’s thatοΌ Feel accomplished, feel oneself want to float……
The momentum
However, this only explains the last of the three examples at the beginning of the article, so why can the first two be deleted without error? To be honest, when I encountered this problem, my heart was broken to doubt life.
Still no good solution, go ahead and debug the previous example to see what happens differently.
The preceding elements in the List are traversed the same way as above, and will not be repeated. Look directly at the key, as shown in the figure below. At this point, the element “3” has been traversed, and the remove operation is about to begin. The remove operation is the same as above, and fastRemove() will remove the element, and fastRemove() will indeed execute modCount++, Does cause expectedModCount! = modCount. But…
When iterating over the next element, the cursor will enter hashNext() again. Unfortunately, if hashNext() is not true, return false and the next() method will not be entered again. Naturally, there will be no call to checkForComodification() for verification, and there will be no chance to throw exceptions. In fact, at this point, the last element in the list, “5”, has not been traversed at all. To verify this, add output code to the for loop:
public class CollectionDemo {
public static void main(String[] args) {
List list = new ArrayList();
list.add("1");
list.add("3");
list.add("5");
for (Object o : list) {
System.out.println(o);// Outputs the iterating element
if ("3".equals(o)) list.remove(o); } System.out.println(list); }}Copy the codeYou’ll see that it only prints 1 and 3.
That’s not all, but here’s the final case:
public class CollectionDemo {
public static void main(String[] args) {
List list = new ArrayList();
list.add("1");
list.add("2");
list.add("3");
for (Object o : list) {
if ("3".equals(o)) list.remove(o); } System.out.println(list); }}Copy the codeGuess what? Isn’t it exactly the same as the first example? So it’s successfully deleted. Output 1 and 2. Ha ha π, let you down.
Are you doubting life again? In fact, with so much foreshadowing in front, it is not difficult to infer the reason for this mistake.
Here’s why. Next() returns 3, size is reduced to 2, and hasNext() returns true. My darling…… So Itr iterator is silly to call next (), at the back of the things is all know, checkForComodification () is called again, throw ConcurrentModificationException.
The problem with java.util.arrayList $Itr is the logic of hasNext(). Each time the iterator returns an element, the index of the element in the List is equal to the Itr’s CURSOR value, and each time an element is deleted, the result is size–. It is not difficult to conclude that if the element you want to delete happens to be the second-to-last position in the List, no exception will be thrown, and the correct deletion will be displayed. Like the first example at the beginning of this article, the rest of the cases throw an exception. However, even if there is no exception thrown, the consistency of the expectedModCount and modCount inside the List iterator has been damaged and is just covered up, so such operation may have very big hidden trouble in the future, and it is not recommended to use it in this way. Those that need to manipulate collections during iteration should still use iterators.
In addition to ArrayList, you can find modCount properties in HashMap, and modCount++ operations in the corresponding structural operation methods, such as put(), clear(), etc. Inside the HashMap there is an internal iterator, HashIterator, which maintains an expectedModCount property, and the rest of the routines are just like the ArrayList.
- Today’s technology sharing is shared here, thank you for your busy schedule to take such a long time to read my article π.
- In addition, my notes and articles will be updated on github.
- Here I will update some reading notes from time to time github.com/dujunchen/…
- Here I will occasionally update some backend core features dry github.com/dujunchen/…