background
Yesterday xiao Feng received a company interview phone, one of the interview questions feel a little interesting, here to share with you. The interview question is how ArrayList removes a specified element. It sounds like a simple question, but you can easily fall into the interviewer’s trap if you haven’t actually stepped in the hole.
Problem analysis
Full of doubt
When Xiao Feng heard the interview question, she wondered why the interviewer asked such a simple question. She thought to herself, “For loop, equal judgment, and then deletion would be enough.” But then I thought, no, there must be a trap, otherwise I wouldn’t ask such a seemingly simple question. When you delete a specified element from the ArrayList, you throw an exception when you remove the element directly from the for loop. Small Maple secretly secretly pleased, found the trap buried by the interviewer.
Small maple recalled the day of the test, the code for desensitization transformation. To delete the specified element from the ArrayList, I wrote the following code, clicked the “Run” button with confidence, and threw an exception.
public class TestListMain {
public static void main(String[] args) {
List<String> result = new ArrayList<>();
result.add("a");
result.add("b");
result.add("c");
result.add("d");
for (String s : result) {
if ("b".equals(s)) {
result.remove("b"); }}}}Copy the codeA big red exception will appear soon. OMG, how can this happen? It feels like nothing is wrong with the code. Can see behind a ConcurrentModificationException abnormalities, and it is in the Itr thrown out of this class of a detection method of anomaly, it is how to return a responsibility? We didn’t have this Itr code in our original code, so it was a puzzle.
A dark day seem bright
Since we can’t tell from the source code, let’s take a look at the contents of the compiled source code in the class file. After all, the class file is the actual code executed by the JVM. As it turns out, the for-each statement in our original code was actually executed as an iterator after compilation.
public class TestListMain {
public TestListMain(a) {}public static void main(String[] args) {
List<String> result = new ArrayList();
result.add("a");
result.add("b");
result.add("c");
result.add("d");
// Create an iterator
Iterator var2 = result.iterator();
while(var2.hasNext()) {
String s = (String)var2.next();
if ("b".equals(s)) {
result.remove("b"); }}}}Copy the codeThe Itr is an inner iterator created by ArrayList, so the for-each loop becomes an iterator plus a while loop.
public Iterator<E> iterator(a) {
return new Itr();
}
Copy the codeItr, the inner class iterator, determines whether the iterator has content by determining hasNext(), while the next() method retrieves the content of the iterator.
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]; }... }Copy the codeThe general process is as follows:
The real exception is that the test method throws an exception when the modCount is not equal to the expectedModCount. So we want to look at what the modCount and the expectedModCount are. Where modCount stands for the number of changes in the ArrayList and expectedModCount stands for the number of changes in the iterator. When the Itr iterator is created, modCount is assigned to the expectedModCount, So in this example both modCount and expectedModCount start out at 4 (with the String element added four times). But after the b element is retrieved, the ArrayList is removed, so modCount accumulates to 5. As a result, inconsistencies occur when checking, which ultimately leads to exceptions. Here we find the reason for throwing an exception. The loop uses an iterator to loop through, but the operation on the element is an ArrayList operation, so the iterator finds that the element has been modified during the loop and throws an exception.
Let’s think about it a little bit, why do we have this test? What exactly does this exception do? Let’s open the ConcurrentModificationException annotation is how to describe. Simply put, it is not allowed for one thread to modify the collection and another thread to iterate over the collection. Once this condition is detected, an exception is thrown through the fast-fail mechanism to prevent subsequent unknowns.
/** *** * For example, it is not generally permissible for one thread to modify a Collection * while another thread is iterating over it. In general, the results of the * iteration are undefined under these circumstances. 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. *** **/
public class ConcurrentModificationException extends RuntimeException {... }Copy the codeReview the process
How to delete correctly
Since the exception is thrown because iterators are looping, deletion using ArrayList causes the detection to fail. So we loop through iterators and delete iterators, so that we can be consistent. Of course we can also use the API provided in the List.
public class TestListMain {
public static void main(String[] args) {
List<String> result = new ArrayList<>();
result.add("a");
result.add("b");
result.add("c");
result.add("d");
Iterator<String> iterator = list.iterator();
while (iterator .hasNext()) {
String str = iterator.next();
if ("b".equals(str)) { iterator.remove(); }}}Copy the codeconclusion
This article focuses on the source code analysis of the exception that occurs when ArrayList deletes elements in the for loop. This is also a common interview trap question. Interviewers use this seemingly simple question to test candidates’ knowledge of JDK source code. Xiao Feng’s interview is still going on, so let’s look forward to seeing what kind of trap interview questions he will encounter next time.
Hi, I’m Mufeng. Thanks for your likes, favorites and comments. See you next time! \
Wechat search: Mufeng technical notes, quality articles continue to update, we have learning punch group can pull you in, together with the impact of the big factory, in addition, there are a lot of learning and interview materials to provide everyone, recently in the year-end benefits, hurry to have a look.
