Будет ли проблема с удалением элементов в цикле ArrayList? Я начинаю думать, что должна быть какая-то проблема, но я не знаю, где она будет. После некоторого тестирования и проверки оказывается, что эта «маленькая» проблема не проста!
Нет проблем с удалением не в цикле, иначе нет необходимости в существовании этого метода.То, что мы обсуждаем здесь, это удаление в цикле, и есть много видов методов цикла для ArrayList, здесь определен метод класса remove(), существует пять методов реализации удаления, некоторые методы будут сообщать об ошибке при запуске, а некоторые могут работать, но не могут быть полностью удалены, читатели также могут тестировать один за другим.
public class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("aa");
list.add("bb");
list.add("bb");
list.add("aa");
list.add("cc");
// 删除元素 bb
remove(list, "bb");
for (String str : list) {
System.out.println(str);
}
}
public static void remove(ArrayList<String> list, String elem) {
// 五种不同的循环及删除方法
// 方法一：普通for循环正序删除，删除过程中元素向左移动，不能删除重复的元素
// for (int i = 0; i < list.size(); i++) {
// if (list.get(i).equals(elem)) {
// list.remove(list.get(i));
// }
// }
// 方法二：普通for循环倒序删除，删除过程中元素向左移动，可以删除重复的元素
// for (int i = list.size() - 1; i >= 0; i--) {
// if (list.get(i).equals(elem)) {
// list.remove(list.get(i));
// }
// }
// 方法三：增强for循环删除，使用ArrayList的remove()方法删除，产生并发修改异常 ConcurrentModificationException
// for (String str : list) {
// if (str.equals(elem)) {
// list.remove(str);
// }
// }
// 方法四：迭代器，使用ArrayList的remove()方法删除，产生并发修改异常 ConcurrentModificationException
// Iterator iterator = list.iterator();
// while (iterator.hasNext()) {
// if(iterator.next().equals(elem)) {
// list.remove(iterator.next());
// }
// }
// 方法五：迭代器，使用迭代器的remove()方法删除，可以删除重复的元素，但不推荐
// Iterator iterator = list.iterator();
// while (iterator.hasNext()) {
// if(iterator.next().equals(elem)) {
// iterator.remove();
// }
// }
}
}
Здесь я протестировал пять различных методов удаления, обычный цикл for, расширенный цикл foreach и цикл итератора, всего три метода цикла. Вы также можете оставить сообщение и обсудить с нами!
Для вышеуказанных методов удаления удаляется один элемент в списке, то есть элемент без дубликатов, например «cc». ConcurrentModificationException будет сгенерировано в методе 3 и методе 4. Метод remove() в ArrayList используется в этих двух методах удаления (перейдите и посмотрите код выше). При удалении повторяющихся элементов в списке возможны две ситуации: одна состоит в том, что два повторяющихся элемента находятся рядом друг с другом, например «bb», другая заключается в том, что два повторяющихся элемента не находятся рядом друг с другом, например "аа". При удалении таких элементов метод 1 является нормальным при удалении повторяющихся, но прерывистых элементов, но при удалении повторяющихся и непрерывных элементов будет проблема неполного удаления.Этот метод удаления также использует метод удаления в ArrayList.(). Два других метода можно удалить обычным образом, а вот пятый метод не рекомендуется, о нем речь пойдет позже.
После анализа текущих результатов выясняется, что все проблемы указывают на метод remove() в ArrayList (это похоже на детектива, занимающегося делом. Это может быть иллюзия написания слишком большого количества кода, txtx...) Тогда просмотр исходного кода ArrayList - самый хороший выбор, следующий код ключа, который я перехватил (Java1.8).
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
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
return oldValue;
}
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
}
Видно, что метод remove() перегружен, один — удалять по индексу, а другой — удалять по элементу, что тоже хорошо понятно.
Согласно методу удаления индекса remove(), общие шаги таковы:
- 1. Чтобы проверить, не выходит ли индекс за пределы, нужно проверить, больше ли текущий индекс длины массива или равен ему.
- 2. Количество изменений списка (операций добавления и удаления) увеличивается на 1.
- 3. Сохраните значение, которое нужно удалить.
- 4. Подсчитайте количество перемещенных элементов
- 5. Элемент после позиции удаления перемещается влево, что здесь реализовано копированием массива
- 6. Задайте для последней ссылки на расположение значение null, чтобы сборщик мусора мог освободить эту память.
- 7. Вернуть значение удаленного элемента
Согласно методу удаления элемента remove(), общие шаги таковы:
-
1. Значения элемента делятся на нулевые и ненулевые значения
-
2. Обход цикла и т.д.
-
3. Вызовите функцию fastRemove(i)
-
3.1. Добавьте 1 к количеству ревизий
-
3.2. Подсчитайте количество перемещенных элементов
-
3.3 Копия массива реализует перемещение элемента влево
-
3.4 Установите для последней ссылки местоположения значение null
-
3.5, вернуть ложь
-
-
4. Вернуть истину
Здесь у меня есть вопрос, код в первом методе remove() точно такой же, как код в методе fastRemove(), и первый метод remove() может вызывать fastRemove( как и второй метод remove().) метод, код здесь действительно немного избыточен. Я снова прочитал исходный код Java10. Автор кода изменил его, и код написан очень хорошо. Мне потребовалось много времени, чтобы понять превосходные навыки программирования Даниил: Заинтересованные друзья могут пойти посмотреть.
Акцентируем внимание на процессе удаления.Те, кто изучал структуры данных, возможно, писали такие удаления от руки.Ниже я нарисую картинку, чтобы вы могли более наглядно увидеть весь процесс удаления. Взяв в качестве примера удаление «bb», при обращении к элементу с индексом 1 обнаруживается, что это «bb», и элемент здесь должен быть удален.Согласно приведенным выше шагам удаления, элемент за позиция удаления должна быть смещена вперед и перемещена.После этого нижний индекс элемента "bb" после "bb" равен 1, а нижний индекс следующих элементов также уменьшается на 1 по очереди.Это работа цикла, когда я = 1. В следующем цикле с i = 2 второй элемент «bb» не учитывается, поэтому этот метод удаления имеет проблемы с удалением последовательных повторяющихся элементов. Но если мы сделаем i цикл декремента, то есть цикл обратного порядка метода 2, этой проблемы не будет, и удаление положительного порядка и удаление обратного порядка показано на следующем рисунке.
Теперь, когда мы выяснили причину, по которой его нельзя удалить в обычном режиме, давайте рассмотрим причину, по которой его можно удалить в обычном режиме в методе 5. В методе 5 используется метод remove() в итераторе. Прочитав исходный код ArrayList, вы обнаружите, что есть два закрытых внутренних класса, Itr и ListItr. Itr реализует интерфейс Iterator, а ListItr наследует класс Itr и реализует Интерфейс ListIterator. В классе Itr также есть метод remove(), и итератор фактически вызывает этот метод remove(), я также перехватил исходный код этого метода.
private class Itr implements Iterator<E>
private class ListItr extends Itr implements ListIterator<E>
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification(); // 检查修改次数
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
Видно, что метод remove() в ArrayList вызывается в этом методе remove(), так почему же метод 4 выдает исключение параллельной модификации и здесь нет проблем? Обратите внимание на переменную expectModCount и переменную modCount. modCount также виден в предыдущем коде. Он записывает, сколько раз список модифицировался, а перед ним стоит ожидаемый ModCount. Начальное значение этой переменной равно modCount. . существуетArrayList.this.remove(lastRet);Перед кодом также вызывается метод checkForCommodification(), который проверяет количество модификаций.Этот метод делает очень простые вещи.Если modCount иожидаемыйModCount не равны, то выбрасывается ConcurrentModificationException, и в этом методе remove() есть ``expectedModCount = modCount`, два значения переменных синхронизируются после метода remove() списка ArrayList, поэтому исключение не будет выдано, а в процессе цикла непрерывно повторяющиеся элементы не будут пропущены, поэтому их можно удалить нормально. Все приведенные выше коды выполняются в одном потоке.Если вы переключитесь на многопоточность, метод 5 не может гарантировать согласованность модификации двух переменных, а результат является неопределенным, поэтому этот метод не рекомендуется. Метод 1 можно удалить как в однопоточном, так и в многопоточном режиме. Тестовый код в многопоточном режиме выглядит следующим образом. Здесь я смоделировал только три потока (Примечание: здесь я не использовал лямбда-выражение, недавно добавленное Java8):
import java.util.ArrayList;
import java.util.Iterator;
public class MultiThreadArrayList {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("aa");
list.add("bb");
list.add("bb");
list.add("aa");
list.add("cc");
list.add("dd");
list.add("dd");
list.add("cc");
Thread thread1 = new Thread() {
@Override
public void run() {
remove(list,"aa");
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
};
Thread thread2 = new Thread() {
@Override
public void run() {
remove(list, "bb");
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
};
Thread thread3 = new Thread() {
@Override
public void run() {
remove(list, "dd");
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
};
// 使各个线程处于就绪状态
thread1.start();
thread2.start();
thread3.start();
// 等待前面几个线程完成
try {
thread1.join();
thread2.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
for (String str : list) {
System.out.println(str);
}
}
public static void remove(ArrayList<String> list, String elem) {
// 普通for循环倒序删除，删除过程中元素向左移动，不影响连续删除
for (int i = list.size() - 1; i >= 0; i--) {
if (list.get(i).equals(elem)) {
list.remove(list.get(i));
}
}
// 迭代器删除，多线程环境下无法使用
// Iterator iterator = list.iterator();
// while (iterator.hasNext()) {
// if(iterator.next().equals(elem)) {
// iterator.remove();
// }
// }
}
}
Так как в Java есть проблема с удалением цикла, давайте подумаем. Будет ли такая проблема с удалением списка в Python? Я попробовал из любопытства и обнаружил, что следующий метод также имеет проблему невозможности удалить последовательные повторяющиеся элементы. Второй метод - сообщить об исключении, что нижний индекс списка выходит за пределы. Код теста выглядит следующим образом. Здесь я тестировал только однопоточную среду:
list = []
list.append("aa")
list.append("bb")
list.append("bb")
list.append("aa")
list.append("cc")
# 方法一，存在和 Java 相同的删除问题
# for str in list:
# if str == "bb":
# list.remove(str)
# 方法二，直接报错
# for i in range(len(list)):
# if list[i] == "bb":
# list.remove(list[i])
for str in list:
print(str)
Следующий отрывок взят из Интернета, что является хорошим способом дать профессиональную терминологию вышеупомянутых проблем.
Один: безотказный
При обходе объекта коллекции с помощью итератора, если содержимое объекта коллекции изменяется (добавляется, удаляется, изменяется) во время процесса обхода, будет выдано исключение параллельной модификации.
Принцип: итератор напрямую обращается к содержимому коллекции при обходе и использует переменную modCount в процессе обхода. Если содержимое коллекции изменится во время ее обхода, значение modCount изменится. Всякий раз, когда итератор использует hashNext()/next() для перехода к следующему элементу, он проверяет, является ли переменная modCount ожидаемым значением modCount, и если да, возвращает результат обхода; в противном случае генерирует исключение и завершает обход.
Примечание. Это исключение возникает при обнаружении modCount! =expectedmodCount Это условие. Если измененное значение modCount оказывается равным ожидаемому значению modCount при изменении коллекции, исключение не будет выдано. Следовательно, программирование параллельных операций не может зависеть от того, выброшено это исключение или нет.Это исключение рекомендуется только для обнаружения ошибок параллельной модификации.
Сценарий: все классы коллекций в пакете java.util являются отказоустойчивыми и не могут быть изменены одновременно (изменены во время итерации) в нескольких потоках.
Два: отказоустойчивый
Контейнер коллекции, использующий отказоустойчивый механизм, не имеет прямого доступа к содержимому коллекции во время обхода, а сначала копирует исходное содержимое коллекции и проходит по скопированной коллекции.
Принцип: поскольку копия исходной коллекции просматривается во время итерации, изменения, внесенные в исходную коллекцию в процессе обхода, не могут быть обнаружены итератором, поэтому исключение одновременной модификации не будет инициировано.
Недостатки: Преимущество контента, основанного на копировании, заключается в том, чтобы избежать исключения Concurrent Modification Exception, но точно так же итератор не может получить доступ к измененному контенту, то есть итератор проходит копию коллекции, полученную в момент обхода, и во время при обходе исходные модификации, происходящие с коллекцией, неизвестны итератору.
Сценарий: все контейнеры в пакете java.util.concurrent безопасны для сбоев и могут использоваться и изменяться одновременно в нескольких потоках.
Резюме: Fail-fast можно рассматривать как стратегию предотвращения одновременных изменений в многопоточной среде, прямо говорящую разработчикам не делать этого, создавая исключения. Хотя безопасный сбой не вызывает исключения, если коллекция изменяется в нескольких потоках, разработчикам также следует обратить внимание на проблемы, вызванные многопоточностью.
Добро пожаловать в общедоступную учетную запись WeChat, указанную ниже, и здесь есть различные учебные материалы, которыми можно поделиться бесплатно!