Глубокое понимание итераторов в коллекциях Java

Java

👉Все тексты в этой статье являются исключительно оригинальными, при необходимости перепечатки просьба указывать источник перепечатки, спасибо! 😘

Происхождение проблемы

Причина, по которой я захотел написать эту статью сегодня, была чистой случайностью. Прошлой ночью друг-обезьяна из технологической группы WeChat @me задал мне вопрос, код выглядит следующим образом. Он спросил меня, нет ли проблем с записью таким образом, сообщит ли он об ошибке? Затем он сказал, что не может ответить на вопросы, заданные интервьюером, у которого он сегодня ходил на собеседование. 😅

public class CollectionDemo {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("1");
        list.add("3");
        list.add("5");

        for (Object o : list) {
            if ("3".equals(o))
                list.remove(o);
        }
        System.out.println(list);
    }
}

Я не думал об этом тщательно в то время, это казалось простым вопросом, 😏 Но после более внимательного изучения это метод удаления, который выполняет список в расширенном цикле for. Базовые друзья с небольшим знанием Java должны знать, что при использовании итераторов для обхода элементов коллекции, если вам нужно удалить или изменить элементы в коллекции, вы должны использовать метод итератора и абсолютно не можете использовать метод коллекции. сам. Я всегда считал это изречение железным законом. Поэтому я сделал вывод, что с этим кодом есть проблема, и он обязательно сообщит об ошибке. Затем я влепил операцию как тигр, снова набрал этот код и запустил его... Вывод такой:

sca-1

Результат ошарашил, в нормальном выводе ошибки не было, а результат правильный! Поэтому я снова изменил код следующим образом:

public class CollectionDemo {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("1");
      	//其余代码都没有修改，就在list.add("3");之前添加这一行
        list.add("2");
        list.add("3");
        list.add("5");

        for (Object o : list) {
            if ("3".equals(o))
                list.remove(o);
        }
        System.out.println(list);
    }
}

Результат выглядит следующим образом:

sca-2

Результат оказался правильным.

Поэтому я снова изменил код следующим образом:

public class CollectionDemo {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("1");
        list.add("2");
        list.add("3");
      	//其余代码都没有修改，就在list.add("3")之后添加这一行
        list.add("4");
        list.add("5");
        for (Object o : list) {
            if ("3".equals(o))
                list.remove(o);
        }
        System.out.println(list);
    }
}

Результат выглядит следующим образом:

sca-3

На этот раз наконец появилась долгожданная ошибка.

Действительно странно, что был бы такой другой результат? ! Это заставило меня осознать серьезность проблемы, эта проблема не так проста, как представлялось ранее. Вкупе с моим характером ломать кастрюлю и просить до конца, решил изучить и написать что-нибудь кстати, с одной стороны могу пересмотреть в будущем, а так же могу обменяться технологиями с большими парнями. Взволнованный? 😎

Анализ исходного кода

ConcurrentModificationException

Возвращаясь к источнику, поскольку программа выдает исключение, конечно, сначала необходимо уточнить исключение. Придерживаясь привычки изучать технологию и смотреть официальную документацию и исходный код, я заглянул в javadoc ConcurrentModificationException. Исходный текст очень длинный. Вот некоторые ключевые моменты. Если вам интересно, вы можете прочитать Исходный код JDK самостоятельно.

/**
 * This exception may be thrown by methods that have detected concurrent
 * modification of an object when such modification is not permissible.
 
 * For example, it is not generally permissible for one thread to modify a Collection
 * while another thread is iterating over it.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 <i>fail-fast</i> iterators,
 * as they fail quickly and cleanly, rather that risking arbitrary,
 * non-deterministic behavior at an undetermined time in the future.
 
 * Note that this exception does not always indicate that an object has
 * been concurrently modified by a <i>different</i> thread.  If a single
 * thread issues a sequence of method invocations that violates the
 * contract of an object, the object may throw this exception.  For
 * example, if a thread modifies a collection directly while it is
 * iterating over the collection with a fail-fast iterator, the iterator
 * will throw this exception.
*/

Этот большой абзац, вероятно, означает, что это исключение может обнаружить, что объект был одновременно незаконно изменен. Например, коллекция, которая поставляется с jdk, обычно имеет встроенный отказоустойчивый итератор. Когда коллекция обнаруживает, это исключение выдается для таких незаконные одновременные модификации. Так называемая отказоустойчивость, как следует из названия, означает, что при обнаружении исключения чем раньше будет выброшено исключение, тем лучше, чтобы избежать неизвестных скрытых опасностей в будущем. Кроме того, в этом отрывке также говорится, что это исключение появляется не только в случае многопоточной одновременной модификации, но также появляется в одном потоке, как следует из названия.

Однако, прочитав документ в течение длительного времени, я все еще был в замешательстве. О чем, черт возьми, идет речь?

​ Это не имеет значения.В дополнение к выдаче этого исключения, консоль также запрашивает место, где было выброшено конкретное исключение.java.util.ArrayList$Itr.next()ВнутреннийcheckForComodification()метод. Найдите местоположение, указанное исходным кодом ArrayList, как показано на рисунке ниже, чтобы определить местоположение красного поля:

sca-4

Логика этого метода очень проста.

sca-5

Так где же modCount и ожидаемыйModCount? Следуйте за ними, чтобы определить их.

modCount

modCount — это свойство, определенное в AbstractList (родительском классе ArrayList). Javadoc этого свойства также довольно длинный, поэтому я выбрал часть для всеобщего ознакомления.

/**
* 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><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;

Вероятно, это означает, что значение этого поля используется для записи количества структурных манипуляций со списком. Что такое структурированная операция? Это операция, которая влияет на емкость списка или приводит к неправильным результатам в процессе итерации. Подклассы могут использовать значение этого поля для реализации отказоустойчивости. Если вы хотите добиться отказоустойчивости, вам нужно делать внутри методы всех структурных операцийmodCount++операций и может быть увеличен только один раз внутри каждого метода. Это значение не требуется, если вы не хотите реализовывать отказоустойчивость. Например, метод добавления ArrayList имеетmodCount++операции, как показано на следующем рисунке:

sca-9

expectedModCount

Давайте снова посмотрим на ожидаемый ModCount. ожидаемыйModCount определен вjava.util.ArrayList$Itrсвойства внутри и будет использовать значение modCount из ArrayList в качестве значения инициализации.

sca-6

Вы немного чувствуете, когда видите это? То есть в нормальных условиях после инициализации ArrayList также инициализируется встроенный Itr, а ожидаемые значения ModCount и modCount непротиворечивы. Если нет итерационной операции, не будет и несогласованности, и ConcurrentModificationException не будет выброшено. Так почему же наша программа делает эти два значения несовместимыми? На данный момент не используйте ультимативную версию — отлаживать я все равно ничего не могу. Поскольку в нашей программе используется усовершенствованный цикл forEach, фактически forEach можно рассматривать как синтаксический сахар для jdk, а нижний слой реализован с помощью итераторов. Итак, чтобы ясно видеть, мыjava.util.ArrayList$Itrточки останова добавляются к методам. Как показано ниже:

sca-7

Давайте начнем отладку, взяв в качестве примера последнюю ошибку, указанную в первых трех примерах.

В начале в список добавляется 5 элементов, а размер равен 5. Как мы уже знаем, операция добавления является структурной операцией, которая приводит кmodCount++.

sca-8

Значение курсора итератора Itr будет начинаться с 0 и перемещаться по мере перемещения элементов. hasNext() выносит решениеcursor != sizeчтобы определить, есть ли в списке следующий элемент для выборки. Если он возвращает true, он переходит к next() для возврата следующего элемента.

sca-10

Очевидно, у нас есть 5 элементов, и мы можем перейти к next(). В следующем методе первой строкой кода является checkForCommodification() для проверки соответствия ожидаемых значений ModCount и modCount. Очевидно, что никаких дополнительных структурных операций над списком мы не производили с момента добавления элементов в список, естественно, первые 3 итерации не вызовут исключения и вернут элемент нормально. Все как показано.

sca-11

И после каждого выполнения next() курсор будет перемещаться назад на одну позицию, готовясь к повторению следующего элемента.

sca-12

Теперь пришло время перебрать третий элемент «3». Естественное условие if считается истинным, и будет введена операция удаления.

sca-13

Изучив исходный код метода remove(), я обнаружил, чтоmodCount++. То есть значение modCount в это время стало равным 6. Ожидаемый ModCount по-прежнему сохраняет начальное значение 5. Теперь они несовместимы.

sca-14

sca-15

Поскольку в списке есть два элемента «4» и «5» после «3», после удаления элемента «3» итератор продолжит итерацию, повторяя предыдущий процесс, он сначала войдет в hasNext(), в это время курсор равен 3, а размер равен 4, что, естественно, выполняется, поэтому он будет продолжать вводить next() для извлечения следующего элемента.

sca-16

Можно ожидать, что в это время функция checkForCommodification() проверит, несовместимы ли expectModCount и modCount, поэтому будет выброшено исключение ConcurrentModificationException.

sca-17

предварительное резюме

Другими словами, вызов структурной операции над коллекцией в forEach или итераторе приведет к изменению значения modCount, а значение expectModCount по-прежнему будет инициализированным значением, поэтому проверка в next() завершится ошибкой и выдаст исключение. Вот почему, когда я впервые узнал об итераторах, большие ребята сказали мне не использовать метод удаления, который поставляется с коллекцией во время процесса итерации, а использовать метод удаления, который поставляется с итератором. Так зачем использовать метод удаления, поставляемый с итератором, чтобы не сообщать об ошибке? Следующий код:

public class CollectionDemo {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        list.add("5");
        for (Iterator it = list.iterator(); it.hasNext(); ) {
            if ("3".equals(it.next()))
                it.remove();
        }
        System.out.println(list);
    }
}

Это правильная поза, которой учит учитель. Результат, конечно, правильный.

sca-18

Исследуйте логово тигра снова

Чтобы понять разницу, конечно, нужно еще углубиться в логово тигра, а потом посмотреть исходный код метода удаления итератора List. Следующий код в основном фокусируется на двух строках красного поля: первая строка предназначена для удаления итерируемых элементов.ArrayList.this.removeЭто вызов метода удаления внешнего класса ArrayList.Как упоминалось выше, метод удаления коллекции является структурной операцией, результатом которой будет modCount++, поэтому при повторении следующего элемента проверяется согласованность ожидаемыхModCount и modCount при вызове next(). Он должен сообщить об ошибке, чтобы предотвратить эту проблему, поэтому следующая строкаexpectedModCount = modCountОбновите ожидаемое значение ModCount до последнего значения modCount, чтобы согласованность не нарушалась. Вот почему использование метода удаления, поставляемого с итераторами, не вызывает исключения.

sca-19

Как насчет этого? Вы чувствуете, что закончили, чувствуете, что собираетесь плыть...

все за один раз

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

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

Процесс обхода предыдущих элементов в списке такой же, как и выше, и повторяться не будет. Посмотрите непосредственно на ключевые точки, как показано на рисунке ниже. В это время был пройден элемент "3". Операция удаления вот-вот начнется. Операция удаления такая же, как и выше. FastRemove() будет вызывается для удаления элемента, и fastRemove() действительно будет выполнен.modCount++, привело кexpectedModCount != modCount. но......

sca-20

Когда следующий элемент будет перебираться, он все равно будет вводить hashNext() для принятия решения.К сожалению, в это время и курсор, и размер равны 2, то есть, если условие hashNext() не установлено, он будет вернет false, и он больше не войдет в метод next(). , естественно, он не вызовет checkForCommodification() для проверки, и не будет шанса сгенерировать исключение. На самом деле, в это время последний элемент «5» в списке вообще не был пройден. Чтобы убедиться в этом, вы можете добавить код вывода в цикл for:

public class CollectionDemo {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("1");
        list.add("3");
        list.add("5");

        for (Object o : list) {
            System.out.println(o);//输出正在迭代的元素
            if ("3".equals(o))
                list.remove(o);
        }
        System.out.println(list);
    }
}

Вы обнаружите, что выводятся только 1 и 3.

sca-22

На этом все еще не закончилось, и, наконец, есть еще одна ситуация, код выглядит следующим образом:

public class CollectionDemo {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("1");
        list.add("2");
        list.add("3");
        for (Object o : list) {
            if ("3".equals(o))
                list.remove(o);
        }
        System.out.println(list);
    }
}

Угадайте, каков результат? Кому-то покажется, что это не совсем то же самое, что и первый пример статьи? То, что успешно удалено, выведите 1 и 2. Хе-хе🙄, ты разочарован.

sca-23

Вы снова сомневаетесь в вашей жизни? На самом деле, с таким количеством предстоящих предвещаний, не сложно выводить причину этой ошибки.

Причина все еще здесь. Первые два элемента "1" и "2" проходятся, и проблем нет. При запуске обхода "3" элемент "3" возвращается через next(), и курсор будет увеличен до 3 в на этот раз и размер будет Вызов для удаления уменьшен до 2. В это время условие в hasNext() возвращает true и устанавливается снова! Дорогой мой... Итак, итератор Itr по глупости снова вызовет next(), и все станет известно, снова будет вызвана функция checkForCommodification(), выбрасывая ConcurrentModificationException.

sca-24

На самом деле, на основе всего процесса анализа, упомянутого выше, мы можем сделать вывод: на самом деле, ключевым моментом всего процесса является то, чтоjava.util.ArrayList$ItrЛогика метода hasNext(). Нетрудно заметить, что всякий раз, когда итератор возвращает элемент, индекс элемента в списке равен значению курсора Itr, и удаление элемента каждый раз приводит кsize--, нетрудно сделать вывод, что если элемент, который вы хотите удалить, окажется в предпоследней позиции списка, он не вызовет исключение, и будет отображаться правильная операция удаления, как и в первом примере в начале статьи, а остальные вызовут исключение. Но даже если исключение не выбрасывается, на самом деле непротиворечивость ожидаемыхModCount и modCount внутри итератора List на данный момент нарушена, но она скрыта, так что такая операция может таить в себе большие скрытые опасности в последующем, и я лично не рекомендую это использование. , метод итератора должен использоваться для управления коллекцией в процессе итерации.

Кроме того, на самом деле, в дополнение к ArrayList, вы обнаружите, что в HashMap также будут атрибуты modCount, и в соответствующих им структурных методах операций, таких как put(), clear() и т. д., будут правильныеmodCount++операции, а также внутри HashMap есть внутренний итератор HashIterator, который внутри поддерживает ожидаемое свойство ModCount, а остальные подпрограммы аналогичны ArrayList.

  • Сегодняшняя техническая информация опубликована здесь, спасибо, что так долго читали мою статью 😊.
  • Кроме того, мои заметки и статьи будут обновляться на моем github.
    • Здесь я буду обновлять некоторые заметки о чтении время от времениgithub.com/dujunchen/...
    • Здесь я буду время от времени обновлять некоторые основные темы.github.com/dujunchen/...
Категории