Введение
В процессе разработки проекта нам часто требуется удалить элемент в ArrayList, и при использовании некорректного метода удаления может быть выброшено исключение. Или на собеседовании интервьюер спросит, как нормально удалять элементы при обходе. Итак, в этой статье мы протестируем несколько способов удаления элементов и изучим принципы, надеясь всем помочь!
Несколько поз удаления элементов при обходе ArrayList
Первый вывод таков:
Первый метод - нормальный для цикла прямой последовательности (Результат: будет пропущена оценка элемента)
2-й метод - нормальный цикл for для удаления в обратном порядке (результат: удаление правильно)
3-й метод - удаление цикла for-each (результат: исключение)
4-й метод — обход итератора, используйте ArrayList.remove() для удаления элементов (результат: исключение исключения)
5-й метод - обход итератора, используйте удаление итератора для удаления элементов (результат: правильное удаление)
Давайте подробно рассмотрим причины ниже!
Во-первых, инициализируйте массив ArrayList, предположим, что мы хотим удалить элемент 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);
}
Первый способ - нормальный для удаления цикла в положительном порядке (результат: оценка элемента будет пропущена)
for (int i = 0; i < arrayList.size(); i++) {
if (arrayList.get(i) == 3) {//3是要删除的元素
arrayList.remove(i);
//解决方案: 加一行代码i = i - 1; 删除元素后，下标减1
}
System.out.println("当前arrayList是"+arrayList.toString());
}
//原ArrayList是[1, 2, 3, 3, 4, 5]
//删除后是[1, 2, 3, 4, 5]
Выходной результат:
当前arrayList是[1, 2, 3, 3, 4, 5]
当前arrayList是[1, 2, 3, 3, 4, 5]
当前arrayList是[1, 2, 3, 4, 5]
当前arrayList是[1, 2, 3, 4, 5]
当前arrayList是[1, 2, 3, 4, 5]
Вы можете видеть, что было удалено на один меньше 3,
Причина в том, что при вызове remove для удаления элемента метод remove вызывает метод System.arraycopy() для перемещения следующего элемента на предыдущую позицию, то есть вторая 3 переместится на позицию, где индекс массива равен 2, а в следующем цикле, после i+1, i будет 3, а позиция индекса массива 2 не будет оцениваться, поэтому при таком способе записи при удалении элемента следующий элемент b удаленного элемент a переместит позицию a, и если было добавлено 1, оценка элемента b будет проигнорирована, поэтому, если это непрерывный повторяющийся элемент, это приведет к меньшему удалению.
решение
Вы можете выполнить i=i-1 после удаления элемента, чтобы индекс массива снова оценивался в следующем цикле.
2-й метод - нормальный цикл for для удаления в обратном порядке (результат: удаление правильно)
for (int i = arrayList.size() -1 ; i>=0; i--) {
if (arrayList.get(i).equals(3)) {
arrayList.remove(i);
}
System.out.println("当前arrayList是"+arrayList.toString());
}
Выходной результат:
当前arrayList是[1, 2, 3, 3, 4, 5]
当前arrayList是[1, 2, 3, 3, 4, 5]
当前arrayList是[1, 2, 3, 4, 5]
当前arrayList是[1, 2, 4, 5]
当前arrayList是[1, 2, 4, 5]
当前arrayList是[1, 2, 4, 5]
Этот метод может правильно удалять элементы, потому что при вызове remove для удаления элемента метод удаления вызывает System.arraycopy() для перемещения элемента после удаленного элемента вперед, не затрагивая элемент перед элементом a, поэтому обход в обратном порядке может быть нормальный Удалить элементы.
3-й метод - удаление цикла for-each (результат: исключение)
public static void removeWayThree(ArrayList<Integer> arrayList) {
for (Integer value : arrayList) {
if (value.equals(3)) {//3是要删除的元素
arrayList.remove(value);
}
System.out.println("当前arrayList是"+arrayList.toString());
}
}
Выходной результат:
当前arrayList是[1, 2, 3, 3, 4, 5]
当前arrayList是[1, 2, 3, 3, 4, 5]
当前arrayList是[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)
Будет выдано исключение ConcurrentModificationException, главным образом потому, что базовая реализация for-each реализована с использованием метода hasNext() и метода next() в ArrayList.iterator, мы можем использовать декомпиляцию для проверки, используйте следующую команду для класса, содержащего вышеуказанный метод Проверка декомпиляции
javac ArrayTest.java//生成ArrayTest.class文件
javap -c ArrayListTest.class//对class文件反编译
Декомпилированный код для получения метода removeWayThree выглядит следующим образом:
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 调用Iterator.hasNext()方法
11: ifeq 44
14: aload_1
15: invokeinterface #14, 1 // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;调用Iterator.next()方法
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
Хорошо видно, должен ли itrator.hasnext() определить, есть ли следующий элемент, и метод item.next() получит следующий элемент. Потому что при удалении элементов метод remove() вызывает метод FASTREMOVE(), который модифицирует modcount+1, и будет модифицироваться представление массива, причем количество раз +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
}
При удалении элемента вызывается следующий цикл, вызывается метод ITR.NEXT() в следующем исходном коде, а метод checkforcomodification() вызывает список массивов для проверки списка массивов, и определяется, был ли он изменен путем обхода arraylist.Поскольку значение объекта ArrayList.iTR передается в Modcount + 1, а ожидаемый счетчик модов инициализируется, значение объекта ArrayList.iTR не равно, то возникает исключение ConcurrentModificationException.
Так есть ли способ сделать ожидаемое обновление ModCount вовремя?
Как вы можете видеть в исходном коде Itr ниже, ожидаемыйModCount будет обновлен после удаления элемента в методе Itr.remove(), поэтому мы можем использовать метод Itr.remove() для удаления элемента, чтобы гарантировать, что ожидаемыйModCount обновляется. Подробнее см. в способе 5.
private class Itr implements Iterator<E> {
int cursor; // 游标
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;//期待的modCount值
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();//判断expectedModCount与当前的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() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;//更新expectedModCount
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
4-й метод — обход итератора, используйте ArrayList.remove() для удаления элементов (результат: исключение исключения)
Iterator<Integer> iterator = arrayList.iterator();
while (iterator.hasNext()) {
Integer value = iterator.next();
if (value.equals(3)) {//3是要删除的元素
arrayList.remove(value);
}
System.out.println("当前arrayList是"+arrayList.toString());
}
Выходной результат:
当前arrayList是[1, 2, 3, 3, 4, 5]
当前arrayList是[1, 2, 3, 3, 4, 5]
当前arrayList是[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)
Скомпилированный код третьего метода фактически совпадает с четвертым методом, поэтому четвертый метод также вызовет исключение ConcurrentModificationException. Следует отметить, что каждый раз, когда вызывается метод итератора next(), курсор будет перемещаться вправо для достижения цели обхода. Поэтому метод next() не может вызываться несколько раз в одном цикле, иначе он приведет к тому, что некоторые элементы будут пропущены каждый раз, когда цикл зацикливается.Я видел некоторые неправильные записи в некоторых блогах, таких как этот"Удаление элементов в цикле ArrayList, будет ли проблема? 》в статье:
Сначала вызовите iterator.next(), чтобы получить элемент и сравнить его с elem. Если он равен, то вызовите list.remove(iterator.next());, чтобы удалить элемент. В настоящее время iterator.next() больше не равно elem. , но последний элемент, мы можем написать демо, чтобы протестировать его
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());
}
}
Результат выглядит следующим образом:
[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)
Видно, что удаленный элемент на самом деле не 3, а элемент после 3, потому что метод next() вызывается дважды, заставляя курсор перемещаться дальше. Таким образом, вы должны использовать Integer value = iterator.next();, чтобы извлечь элемент для оценки.
5-й метод - обход итератора, используйте удаление итератора для удаления элементов (результат: правильное удаление)
Iterator<Integer> iterator = arrayList.iterator();
while (iterator.hasNext()) {
Integer value = iterator.next();
if (value.equals(3)) {//3是需要删除的元素
iterator.remove();
}
}
Выходной результат:
当前arrayList是[1, 2, 3, 3, 4, 5]
当前arrayList是[1, 2, 3, 3, 4, 5]
当前arrayList是[1, 2, 3, 4, 5]
当前arrayList是[1, 2, 4, 5]
当前arrayList是[1, 2, 4, 5]
当前arrayList是[1, 2, 4, 5]
Элементы могут быть удалены правильно.
Третья разница с первым, а затем четырьмя способами использования ITERATOR.REMOVE (); Удалить элементы, а в методе удаления () итератора будут обновлены переменные ITERATOR, поэтому следующий цикл вызовов ITERATOR.Next (когда) Метод, ожидаемый MODCOUNT и MODCOUNT равный, никакое исключение не бросается.
Несколько поз удаления элементов при обходе HashMap
Первый вывод таков:
1-й метод - for-each перебирает HashMap.entrySet, удаляет с помощью HashMap.remove() (результат: выдает исключение).
Второй метод - for-each проходит HashMap.keySet, использует HashMap.remove() для удаления (результат: выдает исключение).
3-й метод — используйте HashMap.entrySet().iterator() для перебора удалений (результат: правильное удаление).
Давайте подробно рассмотрим причины ниже!
Удалить метод прохождения ArrayList и hashmap Похожие, но разные вызовы API. Во-первых, инициализируйте Hashmap, мы хотим удалить ключ, который содержит значение ключа «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);
Метод 1 - for-each перебирает HashMap.entrySet, удаляет с помощью HashMap.remove() (результат: выдает исключение)
for (Map.Entry<String,Integer> entry: hashMap.entrySet()) {
String key = entry.getKey();
if(key.contains("3")){
hashMap.remove(entry.getKey());
}
System.out.println("当前HashMap是"+hashMap+" 当前entry是"+entry);
}
Выходной результат:
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key1=1
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key2=2
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key5=5
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key6=6
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 当前entry是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)
Второй метод - for-each проходит через HashMap.keySet и удаляет с помощью HashMap.remove() (результат: выдает исключение)
Set<String> keySet = hashMap.keySet();
for(String key : keySet){
if(key.contains("3")){
keySet.remove(key);
}
System.out.println("当前HashMap是"+hashMap+" 当前key是"+key);
}
Результат выглядит следующим образом:
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key1
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key2
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key5
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key6
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 当前key是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)
3-й метод — используйте HashMap.entrySet().iterator() для перебора удалений (результат: правильное удаление)
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("当前HashMap是"+hashMap+" 当前entry是"+entry);
}
Выходной результат:
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key1=1
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key2=2
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key5=5
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key6=6
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key4=4
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 当前entry是deletekey=3
Первый метод и второй метод выбрасывают исключение concurrentmodificationException для вышеприведенного обхода ошибки arrayList — причина метода удаления, имеет ожидаемый счетчик модов, и когда дело доходит до следующего элемента, вызывается метод next(), а затем EXPECTEDMODCOUNT и MODCOUNT оцениваются, и исключение ConcurrentModificationException выдается без согласования.
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() {
return next != null;
}
final Node<K,V> nextNode() {
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() {
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;
}
}
PS: что такое ConcurrentModificationException?
Согласно документации ConcurrentModificationException, некоторые объекты не допускают одновременных изменений, и это исключение выдается при обнаружении таких изменений. (Например, некоторые коллекции не позволяют одному потоку проходить, пока другой поток изменяет коллекцию).
Некоторые реализации итераторов для коллекций (такие как Collection, Vector, ArrayList, LinkedList, HashSet, Hashtable, TreeMap, AbstractList, Serialized Form), которые обеспечивают такое обнаружение параллельных модификаций, могут называться «отказоустойчивыми итераторами», что означает отказоустойчивые итераторы. , то есть при обнаружении одновременных модификаций сразу выбрасывается исключение вместо продолжения выполнения, и исключение выбрасывается при получении некоторых значений ошибки.
Обнаружение аномалии в основном достигается с помощью двух переменных, modCount иожидаемыйModCount,
- modCount
Количество модификаций коллекции, которое обычно хранится в коллекции (например, ArrayList).Каждый раз, когда вызывается метод add(), метод remove() возвращает modCount+1
- expectedModCount
Ожидаемый modCount обычно хранится в Iterator (объект итератора, возвращаемый методом ArrayList.iterator()). Как правило, начальное значение присваивается при инициализации Iterator, а ожидаемое значение ModCount обновляется при вызове метода iterator remove(). называется. (Вы можете посмотреть исходный код ArrayList.Itr выше)
Затем вызов в итераторе next() проходит по элементам, вызывает метод checkForComodification() относительно modCount иожидаемыйModCount, несогласованный выброс ConcurrentModificationException.
Однорезочный эксплуатационный итератор бросает ConcurrentModificationException не исключение. (Приведенный выше пример)
Wechatimg4995.jpeg.
Суммировать
Поскольку итераторы ArrayList и HashMap являются "отказоустойчивыми итераторами", упомянутыми выше, итератор будет сравнивать ожидаемыйModCount и modCount, когда он получит следующий элемент и удалит элемент, и будет выдано исключение, если они несовместимы.
Поэтому при использовании Iterator для обхода элементов (для каждого обхода базовая реализация также является Iterator), вам нужно удалить элементы, вы должны использоватьМетод итератора remove()Для удаления вместо непосредственного вызова метода remove() самого ArrayList или HashMap, иначе ожидаемыйModCount в итераторе не будет обновляться вовремя, а при получении следующего элемента или удалении элемента ожидаемыеModCount и modCount несовместимы , а затем создается исключение ConcurrentModificationException.