Исследование вопроса интервью "ArrayList loop remove() использует Iterator"

Когда я был на собеседовании два месяца назад, меня спросилиArrayListКак удалить элементы в цикле, когда я ответилIterator, когда интервьюер спрашивает, почемуIteratorвместоforeachВ то время я не ответил на него, и теперь я снова думаю об этом вопросе, я думаю, что должен это сделать, поэтому я написал небольшую демонстрацию и проверил ее, прочитав исходный код.

Ниже то, что я проверилArrayList4 случая цикла remove() и его результат (на основе оракула jdk1.8):

//List<Integer> list = new ArrayList<>();
//list.add(1);
//list.add(2);
//list.add(3);
//list.add(4);
//循环remove()的4种情况的代码片段：

//#1
for (Integer integer : list) {
    list.remove(integer);
}

结果：
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)
-----------------------------------------------------------------------------------

//#2
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()) {
    Integer integer = iterator.next();
    list.remove(integer);
}

结果：
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)
-----------------------------------------------------------------------------------


//#3
for (int i = 0; i < list.size(); i++) {
    list.remove(i);
}
System.out.println(list);

结果：
[2, 4]
-----------------------------------------------------------------------------------

//#4
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()){
    iterator.next();
    iterator.remove();
}
System.out.println(list.size());

结果：(唯一一个得到期望值的)
0

Видно, что только последняя из этих ситуаций может дать ожидаемый результат, а остальные либо ненормальны, либо не могут дать ожидаемый результат, разберем их по порядку.

#1

//#1
for (Integer integer : list) {
    list.remove(integer);
}

结果：
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)

Через стек исключений мы можем найтиArrayListвнутренний классItrизcheckForComodificationвспыхнуть в методеConcurrentModificationExceptionИсключение (не будем говорить, что происходит с этим исключением) мы открываемArrayListИсходный код, расположенный в строке 901:

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

Этот метод выталкивания исключения на самом деле делает одну вещь, проверяяmodCount != expectedModCountПоскольку это условие выполняется, возникает исключение, продолжайте просмотрmodCountиexpectedModCountЭти две переменные, найденныеmodCountунаследовано отAbstractListАтрибут атрибута с большим комментарием

/**
 * 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>This field is used by the iterator and list iterator implementation
 * returned by the {@code iterator} and {@code listIterator} methods.
 * If the value of this field changes unexpectedly, the iterator (or list
 * iterator) will throw a {@code ConcurrentModificationException} in
 * response to the {@code next}, {@code remove}, {@code previous},
 * {@code set} or {@code add} operations.  This provides
 * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
 * the face of concurrent modification during iteration.
 *
 * <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;

Грубо означает, что это поле используется дляfail-fastКласс поведения подколлекции, используемый для записи того, сколько раз коллекция была изменена, мы возвращаемся кArrayListможно найти вadd(E e)метод в цепочке вызововensureExplicitCapacity(int minCapacity)Центральная встречаmodCountАвтоматическое приращение:

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

Мы вызываем 4 раза при инициализации спискаadd(E e)а сейчасmodCountзначение4

найти сноваexpectedModCount: эта переменная определена вArrayListизIteratorкласс реализацииItr, который по умолчанию назначаетсяmodCount

Теперь, когда мы знаем, что это за две переменные, давайте начнем.ItrДобавьте точку останова в соответствующий метод (компиляторforeachскомпилировать для использованияIteratorпуть, так что мы смотрим наItrВот и все), начинаем отладку:

цикл:

на каждой итерацииnext()будет вызван, когдаcheckForComodification()

list.remove():

существуетArrayListизremove(Object o)снова позвонил вfastRemove(index):

fastRemove(index)средняя параmodCountавтоинкремент, только что сказалmodCountпосле 4 разadd(E e)После инициализации4так++после сейчас5:

Перейдите к следующей итерации:

выполнить сноваnext(),next()перечислитьcheckForComodification(), то в процессе вышеmodCountтак какfastRemove(index)Операция стала5иexpectedModCountТогда никто не двигается, поэтому быстро выполняются условия для выдачи исключения.modCount != expectedModCount(то есть вышеупомянутыйfail-fast), программа завершает работу.

#2

//#2
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()) {
    Integer integer = iterator.next();
    list.remove(integer);
}

结果：
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)

На самом деле это № 2 и № 1 одинаковы,foreachбудет оптимизирован во время компиляции дляIteratorвызов, так что просто посмотрите на # 1.

#3

//#3
for (int i = 0; i < list.size(); i++) {
    list.remove(i);
}
System.out.println(list);

结果：
[2, 4]

Такая серьезная ерунда может возникнуть при написании кода в сонном состоянии... Без текстового пояснения, используйтеprintln()Давайте объясним:

第0次循环开始
remove(0)前的list: [1, 2, 3, 4]
remove(0)前的list.size()=4
执行了remove(0)
remove(0)后的list.size()=3
remove(0)后的list: [2, 3, 4]
下一次循环的i=1
下一次循环的list.size()=3
第0次循环结束
是否还有条件进入下次循环?: true

第1次循环开始
remove(1)前的list: [2, 3, 4]
remove(1)前的list.size()=3
执行了remove(1)
remove(1)后的list.size()=2
remove(1)后的list: [2, 4]
下一次循环的i=2
下一次循环的list.size()=2
第1次循环结束
是否还有条件进入下次循环?: false


Process finished with exit code 0

ФактическиArrayListсерединаItrиспользовать游标и最后一次返回值索引решить этоsizeЧем больше вы удаляете, тем меньше, но неловкая ситуация, когда индекс удаляемого элемента становится все больше и больше, это будет объяснено в № 4.

#4

Это правильный способ исполнения восьми классиков, используяArrayListсредний итераторItrизremove()Вместо того, чтобы использоватьArrayListсебяremove(), давайте отладим его и посмотрим, что происходит:

Повторить:

ItrИнициализация: курсор курсора = 0, индекс последнего возвращаемого значения lastRet = -1, ожидаемое количество модификаций expectModCount = modCount = 4;

повторяющийсяhasNext(): Проверить, достиг ли курсор текущего спискаsizeЕсли это не так, вы можете продолжить итерацию:

повторяющийсяnext():checkForComodification()В настоящее времяexpectedModCountиmodCountравен и не бросаетConcurrentModificationException, а затем извлеките курсор (первая итерация курсора0), соответствующий элементу списка, а затем переместите курсор на +1, то есть переместите курсор назад, чтобы он указывал на следующий элемент, а затем установите исходное значение курсора0Назначьте индекс последнего возвращаемого значения, то есть последнее возвращение является индексом0соответствующий элемент

iterator.remove():такой жеcheckForComodification()тогда позвониArrayListизremove(lastRet)Удалить последний возвращенный элемент после удаленияmodCountповысится

После завершения удаления присвоить курсору индекс последнего возвращаемого значения, то есть переместить курсор на одну позицию назад в предыдущую позицию, а затем сбросить индекс последнего возвращаемого значения до начального значения.-1,НаконецexpectedModCountОн переназначается на новый после завершения предыдущего процесса.modCount

Как видно из предыдущих двух шагов, хотя списокsizeКаждыйremove()мегаполис-1, но так как каждыйremove()откатит курсор, а затем сбросит индекс последнего возвращаемого значения, поэтому фактического возврата нетremove()является первым из текущего набора0элементы, он не появится в #3sizeЧем меньше удаление, тем больше становится индекс удаляемого элемента.remove()в процессеexpectedModCountиmodCountВсегда сохраняйте равенство через присваивание, поэтому оно также не отображаетсяfail-fastВыбрасывается исключение.

Вышеизложенное представляет собой небольшое исследование, которое я провел по вопросу интервью "ArrayList loop remove() использует итератор", пройдясь по исходному коду. Я не рассматривал сценарий параллелизма. Написание этой статьи заняло около 3 часов, и офис был ушел после написания этой статьи.Я один, мне тоже пора бы вернуться, сегодня 1024 День программиста, всех с праздником!

---

2017.10.25 Обновление №1

благодарный@llearnНапоминаем, что № 3 также можно использовать с умом, чтобы получить правильный результат (при повторном опросе, я думаю, можно сказать интервьюеру, что нет необходимости использоватьIteratorДа, спасибо@llearn:

//#3 Я думаю, что это может быть
for (int i = 0; i < list.size(); ) {
list.remove(0);
}
System.out.println(list);

2017.10.25 Обновление №2

благодарный@ChinLongнапоминание, предоставляет альтернативуIteratorСпособ, то есть обратный цикл (об этой схеме я тоже думал, когда заканчивал писать статью, но сам на демо не подтверждал), спасибо@ChinLong:

Однако никто не любит, когда я удаляю его задом наперёд.
Я слышал, как другие говорят, что скорость итерации немного выше в перевернутом виде???
for (int i = list.size() -1; i >= 0; i-- ) {
list.remove(i);
}
System.out.println(list);