Introduction to the
During project development, we often have a need to remove an element from the ArrayList, and if we do it incorrectly, we might throw an exception. Or in an interview, an interviewer might ask you how to delete elements properly during the traverse. So in this article, we will test several ways to delete elements, and investigate the principle, hoping to help you!
ArrayList traverses several positions to delete an element
Firstly, the conclusions are as follows:
Method 1 – Normal for loop positive delete (result: missing element judgment)
Method 2 – Normal for loop reverse delete (result: correct delete)
Method 3 – for-each loop delete (result: throw exception)
Method 4 – Iterator traversal, using arrayList.remove () to remove elements (result: throws an exception)
Iterator Iterator Iterator Iterator remove element (result: correct delete)
Let’s take a closer look at why.
First we initialize an arrayList, assuming we want to delete elements equal to 3.
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
arrayList.add(3);
arrayList.add(4);
arrayList.add(5);
removeWayOne(arrayList);
}
Copy the codeMethod 1 – Normal for loop positive delete (result: missing element judgment)
for (int i = 0; i < arrayList.size(); i++) {
if (arrayList.get(i) == 3) {//3 is the element to be deleted
arrayList.remove(i);
// Add a line I = i-1; When you delete an element, the subscript is reduced by 1
}
System.out.println("Current arrayList is"+arrayList.toString());
}
// The original ArrayList is [1, 2, 3, 3, 4, 5]
// Delete [1, 2, 3, 4, 5]
Copy the codeOutput result:
The current arrayList is [1, 2, 3, 3, 4, 5] The current arrayList is [1, 2, 3, 3, 4, 5] 5] Current arrayList is [1, 2, 3, 4, 5]Copy the codeYou can see that there’s a 3 missing,
The reason is that when you call remove to remove an element, the remove method calls system.arrayCopy () to move the following element to the previous position, so the second 3 moves to the array index 2, and on the next loop, after I +1, I will be 3, The position with subscript 2 in the array will not be judged. Therefore, in this writing, when the element is deleted, the next element B of the deleted element A will move the position of A, while I has been increased by 1, the judgment on element B will be ignored. Therefore, if it is a continuous repeating element, less deletion will be caused.
The solution
I =i-1 can be executed after the element is deleted, so that the array subscript is evaluated again the next time through the loop.
Method 2 – Normal for loop reverse delete (result: correct delete)
for (int i = arrayList.size() -1 ; i>=0; i--) {
if (arrayList.get(i).equals(3)) {
arrayList.remove(i);
}
System.out.println("Current arrayList is"+arrayList.toString());
}
Copy the codeOutput result:
The current arrayList is [1, 2, 3, 3, 4, 5] The current arrayList is [1, 2, 3, 3, 4, 5] 5] Current arrayList is [1, 2, 4, 5]Copy the codeThis method removes elements correctly because when remove is called, the remove method’s call to System.arrayCopy () moves the elements after the deleted element A forward without affecting the elements before it, so a reverse loop removes elements normally.
Method 3 – for-each loop delete (result: throw exception)
public static void removeWayThree(ArrayList<Integer> arrayList) {
for (Integer value : arrayList) {
if (value.equals(3)) {//3 is the element to be deleted
arrayList.remove(value);
}
System.out.println("Current arrayList is"+arrayList.toString()); }}Copy the codeOutput result:
The current arrayList is [1.2.3.3.4.5The current arrayList is [1.2.3.3.4.5The current arrayList is [1.2.3.4.5]
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
at java.util.ArrayList$Itr.next(ArrayList.java:851)
at com.test.ArrayListTest1.removeWayThree(ArrayListTest1.java:50)
at com.test.ArrayListTest1.main(ArrayListTest1.java:24)
Copy the codeWill throw ConcurrentModificationException, mainly depends on the underlying implementation of for-each is to use the ArrayList. The iterator hasNext () method and next () method, we can use the decompiled verification, Decompile validation using the following command on the class that contains the above methods
javac ArrayTest.java// Generate the arraytest.class file
javap -c ArrayListTest.class// Decompile the class file
Copy the codeThe decompilated code for the removeWayThree method is as follows:
public static void removeWayThree(java.util.ArrayList<java.lang.Integer>);
Code:
0: aload_0
1: invokevirtual #12 // Method java/util/ArrayList.iterator:()Ljava/util/Iterator;
4: astore_1
5: aload_1
6: invokeinterface #13.1 / / InterfaceMethod Java/util/Iterator hasNext () Z call Iterator. HasNext () method
11: ifeq 44
14: aload_1
15: invokeinterface #14.1 // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object; Call the iterator.next () method
20: checkcast #9 // class java/lang/Integer
23: astore_2
24: aload_2
25: iconst_3
26: invokestatic #4 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
29: invokevirtual #10 // Method java/lang/Integer.equals:(Ljava/lang/Object;) Z
32: ifeq 41
35: aload_0
36: aload_2
37: invokevirtual #15 // Method java/util/ArrayList.remove:(Ljava/lang/Object;) Z
40: pop
41: goto 5
44: return
Copy the codeYou can clearly see iterator.hasnext () to see if there is a next element, and iterator.next () to get the next element. Because the remove() method calls the fastRemove() method when the element is removed, modCount+1, which means that the array has been modified, increases the number of changes by 1.
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;
}
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 codeAfter deleting elements, the next cycle will call the itr.next () method in the source code below to obtain the next element, and call the checkForComodification() method to verify the ArrayList to judge whether the ArrayList has been modified during traversal. ExpectedModCount due to modCount + 1 before, or initialization time ArrayList. Itr when the object is assigned a value, so will not be equal, then throw ConcurrentModificationException.
So is there any way to keep expectedModCount up-to-date?
Remove () method is used to remove the element and the expectedModCount is updated. Therefore, when deleting the element, the Itr.remove() method can be used to update the expectedModCount. Look at method 5.
private class Itr implements Iterator<E> {
int cursor; / / the cursor
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;// Expected modCount value
public boolean hasNext(a) {
returncursor ! = size; }@SuppressWarnings("unchecked")
public E next(a) {
checkForComodification();// Test whether the expectedModCount is consistent with the current modCount
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;/ / update the expectedModCount
} catch (IndexOutOfBoundsException ex) {
throw newConcurrentModificationException(); }}final void checkForComodification(a) {
if(modCount ! = expectedModCount)throw newConcurrentModificationException(); }}Copy the codeMethod 4 – Iterator traversal, using arrayList.remove () to remove elements (result: throws an exception)
Iterator<Integer> iterator = arrayList.iterator();
while (iterator.hasNext()) {
Integer value = iterator.next();
if (value.equals(3)) {//3 is the element to be deleted
arrayList.remove(value);
}
System.out.println("Current arrayList is"+arrayList.toString());
}
Copy the codeOutput result:
The current arrayList is [1.2.3.3.4.5The current arrayList is [1.2.3.3.4.5The current arrayList is [1.2.3.4.5]
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
at java.util.ArrayList$Itr.next(ArrayList.java:851)
at com.test.ArrayListTest1.removeWayFour(ArrayListTest1.java:61)
at com.test.ArrayListTest1.main(ArrayListTest1.java:25)
Copy the code3 kinds of methods in the compiled code, it is the same as the fourth kind is, so a fourth writing will throw ConcurrentModificationException. The caveat is that each call to iterator’s next() method causes the cursor to move to the right for traversal purposes. You can’t call the next() method more than once in a single loop, or it will cause some elements to be skipped each time. I’ve seen some errors in blogs, such as this one about deleting elements in an ArrayList loop. In the article:
! [image-20200101124822998](/Users/ruiwendaier/Library/Application Support/typora-user-images/image-20200101124822998.png)
Iterator.next () gets the elements, compares them to elem, and if they are equal, calls list.remove(iterator.next()); Iterator.next () is no longer the equivalent of elem, but the next element. We can write a demo to test this
ArrayList<Integer> arrayList = new ArrayList();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
arrayList.add(4);
arrayList.add(5);
arrayList.add(6);
arrayList.add(7);
Integer elem = 3;
Iterator iterator = arrayList.iterator();
while (iterator.hasNext()) {
System.out.println(arrayList);
if(iterator.next().equals(elem)) { arrayList.remove(iterator.next()); }}Copy the codeThe following output is displayed:
[1.2.3.4.5.6.7]
[1.2.3.4.5.6.7]
[1.2.3.4.5.6.7]
[1.2.3.5.6.7]
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
at java.util.ArrayList$Itr.next(ArrayList.java:851)
at com.test.ArrayListTest1.main(ArrayListTest1.java:29)
Copy the codeYou can see that the removed element is not actually 3, but the element after 3, because the cursor moved too much by calling the next() method twice. So use Integer value = iterator.next(); Take the element out and judge.
Iterator Iterator Iterator Iterator remove element (result: correct delete)
Iterator<Integer> iterator = arrayList.iterator();
while (iterator.hasNext()) {
Integer value = iterator.next();
if (value.equals(3)) {//3 is the element to be deletediterator.remove(); }}Copy the codeOutput result:
The current arrayList is [1.2.3.3.4.5The current arrayList is [1.2.3.3.4.5The current arrayList is [1.2.3.4.5The current arrayList is [1.2.4.5The current arrayList is [1.2.4.5The current arrayList is [1.2.4.5]
Copy the codeElements can be deleted correctly.
Iterator.remove (); iterator.remove(); iterator.remove(); The iterator’s expectedModCount variable is updated in the remove() method, so the next time the iterator.next() method is called, the expectedModCount is equal to the modCount and no exception is thrown.
The HashMap traverses several positions to remove elements
Firstly, the conclusions are as follows:
The first method, for-each, iterates over hashmap.entryset and removes it with hashmap.remove () (result: throws an exception).
The second method, for-each, iterates over hashmap.keyset and removes it with hashmap.remove () (result: throws an exception).
Method 3 – use hashmap.entryset ().iterator() to iterate over the delete (result: correct delete).
Let’s take a closer look at why.
The traversal deletion of HashMap is similar to that of ArrayList, except that the API is called differently. To initialize a HashMap, we remove key-value pairs whose key contains the string “3”.
HashMap<String,Integer> hashMap = new HashMap<String,Integer>();
hashMap.put("key1".1);
hashMap.put("key2".2);
hashMap.put("key3".3);
hashMap.put("key4".4);
hashMap.put("key5".5);
hashMap.put("key6".6);
Copy the codeThe first method, -for-each, iterates through hashmap.entryset and removes it using hashmap.remove () (result: throws an exception)
for (Map.Entry<String,Integer> entry: hashMap.entrySet()) { String key = entry.getKey(); if(key.contains("3")){ hashMap.remove(entry.getKey()); } system.out. println(" Current HashMap is "+ HashMap +" current entry is "+entry); }Copy the codeOutput result:
The current HashMap is {key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} Current entry is key1=1The current HashMap is {key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} Current entry is key2=2The current HashMap is {key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} Current entry is key5=5The current HashMap is {key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} Current entry is key6=6The current HashMap is {key1=1, key2=2, key5=5, key6=6, key4=4} Current entry is key3=3
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429)
at java.util.HashMap$EntryIterator.next(HashMap.java:1463)
at java.util.HashMap$EntryIterator.next(HashMap.java:1461)
at com.test.HashMapTest.removeWayOne(HashMapTest.java:29)
at com.test.HashMapTest.main(HashMapTest.java:22)
Copy the codeThe second method, for-each, iterates over hashmap.keyset and removes it using hashmap.remove () (result: throws an exception)
Set<String> keySet = hashMap.keySet();
for(String key : keySet){
if(key.contains("3")){
keySet.remove(key);
}
System.out.println("The current HashMap is"+hashMap+"The current key is"+key);
}
Copy the codeThe following output is displayed:
The current HashMap is {key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} The current key is key1 the current HashMap is {key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} The current key is key2 the current HashMap is {key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} Current key is key5 Current HashMap is {key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} The current key is key6 the current HashMap is {key1=1, key2=2, key5=5, key6=6, key4=4} The current key is key3 Exception in thread"main" java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429)
at java.util.HashMap$KeyIterator.next(HashMap.java:1453)
at com.test.HashMapTest.removeWayTwo(HashMapTest.java:40)
at com.test.HashMapTest.main(HashMapTest.java:23)
Copy the codeMethod 3 – Use hashmap.entryset ().iterator() to iterate over the delete (result: correct delete)
Iterator<Map.Entry<String, Integer>> iterator = hashMap.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Integer> entry = iterator.next();
if(entry.getKey().contains("3")){
iterator.remove();
}
System.out.println("The current HashMap is"+hashMap+"Current entry is"+entry);
}
Copy the codeOutput result:
The current HashMap is {key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} Current entry is key1=1The current HashMap is {key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} Current entry is key2=2The current HashMap is {key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} Current entry is key5=5The current HashMap is {key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} Current entry is key6=6The current HashMap is {key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} Current entry is key4=4The current HashMap is {key1=1, key2=2, key5=5, key6=6, key4=4} Current entry is deletekey=3
Copy the codeMethod 1 and 2 kinds of methods throw ConcurrentModificationException and traverse the ArrayList error – delete methods above, the cause of HashIterator also has a expectedModCount, when times over for the next element, Will call next () method, and then to determine expectedModCount and modCount throw ConcurrentModificationException inconsistent.
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if(t ! =null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null); }}public final boolean hasNext(a) {
returnnext ! =null;
}
final Node<K,V> nextNode(a) {
Node<K,V>[] t;
Node<K,V> e = next;
if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null&& (t = table) ! =null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove(a) {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null.false.false); expectedModCount = modCount; }}Copy the codePS: ConcurrentModificationException is what?
According to the documents of ConcurrentModificationException introduction, some objects do not allow concurrent modification, as these changes behavior is detected, the exception will be thrown. (For example, some collections do not allow one thread to iterate while another thread changes the collection).
Some collections (such as Collection, Vector, ArrayList, Iterator implementations of LinkedList, HashSet, Hashtable, TreeMap, AbstractList, Serialized Form) provide concurrent modification exception detection. These iterators can then be called “fail-fast iterators “, which means that when a concurrent change is detected, an exception is thrown directly, rather than continuing to throw an exception until some error value is obtained.
Exception detection is mainly realized by modCount and expectedModCount variables,
- modCount
The number of times the collection is modified, usually by the collection (such as ArrayList). Each call to add(), remove() causes modCount+1
- expectedModCount
Iterator(arrayList.iterator ()). The expected modCount is held by Iterator(the object returned by arrayList.iterator ()). ExpectedModCount is updated when Iterator’s remove() method is called. (Check out the source code for ArrayList.itr above.)
Then in the Iterator call next () traverse elements, invoked checkForComodification () method compare modCount and expectedModCount, throw ConcurrentModificationException inconsistent.
Single thread operation Iterator is not at that time also can throw ConcurrentModificationException. WechatIMG4995. Jpeg
conclusion
Because the Iterators of ArrayList and HashMap are fail-fast iterators, the iterators compare expectedModCount and modCount when they get the next element and delete the element, and throw exceptions if they are inconsistent.
So when Iterator iterates over elements (the underlying implementation of for-each Iterator is also Iterator) and you need to remove elements, you must use Iterator’s remove() method to remove them. Instead of calling the Remove () method of ArrayList or HashMap itself, which would cause the expectedModCount in Iterator to not update in time and then fetch the next element or delete the element later, ExpectedModCount and modCount inconsistent, and then throw ConcurrentModificationException.