User Эллеонора Керри
Эллеонора Керри
41 уровень

Сказ о двух итераторах: стратегии конкурентной модификации в Java

Статья из группы Java Developer
Автор заметки — Гжегож Мирек — разработчик программного обеспечения из Кракова (Польша). Он занялся разработкой на Java около 6 лет назад, ещё в университете, и, с этого времени, неустанно шлифует своё мастерство в данной сфере. Его особенно интересует вопрос производительности JVM и оптимизации, о чем он, в основном, и пишет в своём блоге.
Сказ о двух итераторах: стратегии конкурентной модификации в Java  - 1
Среди наиболее популярных вопросов на собеседованиях по языку Java есть и такой: В чём различие между fail-fast и fail-safe итераторами? Максимально упрощённый ответ на него: Fail-fast итератор генерирует исключение ConcurrentModificationException, если коллекция меняется во время итерации, а fail-safe – нет. Хотя это звучит достаточно осмысленно, остается непонятным, что интервьюер понимает под fail-safe? Спецификации языка Java не определяют этот термин в отношении итераторов. Однако существуют четыре стратегии конкурентной модификации.

Конкурентная модификация

Во-первых, давайте определимся, что такое конкурентная (или параллельная) модификация. Допустим у нас есть коллекция и при активном итераторе происходят какие-либо её изменения, не исходящие от данного итератора. В таком случае у нас получается конкурентная модификация. Приведу простейший пример: допустим, у нас есть несколько нитей. Первая нить выполняет итерации, а вторая вставляет элементы в ту же коллекцию или удаляет их из неё. Однако мы можем получить исключение ConcurrentModificationException и при работе в однопоточной среде:

List<String> cities = new ArrayList<>();
cities.add(“Warsaw”);
cities.add(“Prague”);
cities.add(“Budapest”);
 
Iterator<String> cityIterator = cities.iterator();
cityIterator.next();
cities.remove(1);
cityIterator.next(); // генерирует ConcurrentModificationException

Fail-fast

Вышеприведенный фрагмент кода – пример fail-fast итератора. Как вы можете видеть, при попытке извлечения второго элемента из итератора было сгенерировано исключение ConcurrentModificationException. Откуда итератор узнает, что коллекция была модифицирована после его создания? Например, в коллекции может быть метка даты/времени, скажем, lastModified. При создании итератора вам стоит скопировать это поле и сохранить его в объекте итератора. Затем, при каждом вызове метода next(), нужно будет просто сравнить значение lastModified из коллекции с копией из итератора. Очень близкий подход используется, например, в реализации класса ArrayList. В нём есть переменная экземпляра modCount, в которой хранится количество модификаций списка:

final void checkForComodification() {
   if (modCount != expectedModCount)
       throw new ConcurrentModificationException();
}
Важно отметить, что fail-fast итераторы работают на основе принципа "по мере возможности", то есть не дается никаких гарантий генерации исключения ConcurrentModificationException в случае конкурентной модификации. Так что полагаться на это не стоит – скорее, их следует использовать для обнаружения ошибок. Большинство неконкурентных коллекций предоставляют fail-fast итераторы.

Слабая согласованность

Большинство конкурентных коллекций из пакета java.util.concurrent (например, ConcurrentHashMap и большинство Queue) предоставляют слабо согласованные итераторы. Смысл этого термина очень хорошо разъясняется в документации:
  • Они могут обрабатываться конкурентно с другими операциями
  • Они никогда не генерируют исключение ConcurrentModificationException
  • Они гарантированно обходят существовавшие на момент создания итератора элементы ровно один раз, и могут (но не обязаны) отражать последующие модификации.

Снимок состояния

При такой стратегии итератор связывается с состоянием коллекции на момент его создания – это и есть снимок состояния (снепшот) коллекции. Любые произведенные над исходной коллекцией изменения приводят к созданию новой версии нижележащей структуры данных. При этом наш снимок состояния остается неизменным, так что он не отражает изменения в коллекции, которые произошли после создания итератора. Это старая добрая методика копирования при записи (copy-on-write, COW). Она полностью решает проблему конкурентных модификаций, поэтому исключение ConcurrentModificationException при таком подходе не генерируется. Кроме того, итераторы не поддерживают операции, которые меняют элементы. Коллекции с копированием при записи обычно требуют слишком больших расходов ресурсов при использовании, но имеет смысл воспользоваться ими, если изменения происходят намного реже, чем обходы итераторов. Примерами могут служить классы CopyOnWriteArrayList и CopyOnWriteArraySet.

Неопределенное поведение

Неопределенное поведение может встретиться вам в устаревших унаследованных типах коллекций, таких как Vector и Hashtable. В обеих есть стандартные fail-fast итераторы, но кроме этого, они позволяет использовать реализации интерфейса Enumeration, а они не знают, как себя вести в случае конкурентной модификации. Вы можете столкнуться с тем, что некоторые элементы повторяются или оказываются пропущенными, а то и вовсе увидите какие-то странные исключения. Лучше с ними не играться!
Что еще почитать?

Как в Java напечатать числа от 1 до 100 без циклов и условий?

Топ-10 библиотек Java, которые помогут сэкономить время

Комментарии (12)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
Валерий Емельянов Уровень 41, Краснодар, Россия
12 ноября 2021
У итератора есть метод remove(). И возникает вопрос: Можно ли удалить элемент из коллекции в итерации цикла по коллекции?
🦔 Виктор Уровень 20, Москва, Россия Expert
26 сентября 2020
Ранова-то сюда 7 уровней ссылают... p.p.s. и похоже, что блог, который рекламирует статья, уже мёртв, упс! Короче, всё что я понял и забрал к себе на канал: Среди наиболее популярных вопросов на собеседованиях по языку Java есть и такой: В чём различие между fail-fast и fail-safe итераторами? Максимально упрощённый ответ на него: Fail-fast итератор генерирует исключение ConcurrentModificationException, если коллекция меняется во время итерации, а fail-safe – нет. -- Канал в телеге про Java и Android, в котором есть книги для скачивания, статьи, видеоуроки, чат для обмена знаниями и моральной поддержки : ) Давайте учиться вместе: @LetsCodeIt p. s. Мой личный телеграм канал вкатывальщика в прогерство: @SefoNotasi
Josef Уровень 18, Ивано-Франковск, Украина
1 сентября 2020
каждое слово понял... по отдельности🙂
Yakov Stoykov Уровень 16, Одесса, Украина
1 декабря 2019
Как я понял, я сюда с 12 уровнем рано сунулся. 😬
Sergei Azarov Уровень 18, Москва
4 октября 2019
что интервьюер понимает под fail-safe? Науке это неизвестно, поэтому почитайте про Fail-fast...
Андрей Кутиль Уровень 26, Киев, Украина
9 мая 2019
Мда, я так понимаю статья написана чисто как реклама блога. Потому что написано ужасно, это больше похоже на вырваный кусок страницы с книги на 1к страниц.
Farid Уровень 13
28 ноября 2018

CopyOnWriteArrayList и CopyOnWriteArraySet
Не хватает примеров по этим классам