JavaRush/Java блог/Java Developer/Сказ о двух итераторах: стратегии конкурентной модификаци...

Сказ о двух итераторах: стратегии конкурентной модификации в 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, а они не знают, как себя вести в случае конкурентной модификации. Вы можете столкнуться с тем, что некоторые элементы повторяются или оказываются пропущенными, а то и вовсе увидите какие-то странные исключения. Лучше с ними не играться!
Комментарии (13)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
12 сентября 2022, 17:56
Очень интересно, но мало что понятно 🤨
12 ноября 2021, 12:17
У итератора есть метод remove(). И возникает вопрос: Можно ли удалить элемент из коллекции в итерации цикла по коллекции?
🦔 Виктор веду учебный тг-канал в t.me/Javangelion Expert
26 сентября 2020, 16:18
Ранова-то сюда 7 уровней ссылают... p.p.s. и похоже, что блог, который рекламирует статья, уже мёртв, упс! Короче, всё что я понял и забрал к себе на канал: Среди наиболее популярных вопросов на собеседованиях по языку Java есть и такой: В чём различие между fail-fast и fail-safe итераторами? Максимально упрощённый ответ на него: Fail-fast итератор генерирует исключение ConcurrentModificationException, если коллекция меняется во время итерации, а fail-safe – нет. -- Канал в телеге про Java и Android, в котором есть книги для скачивания, статьи, видеоуроки, чат для обмена знаниями и моральной поддержки : ) Давайте учиться вместе: @LetsCodeIt p. s. Мой личный телеграм канал вкатывальщика в прогерство: @SefoNotasi
Josef Software Developer в SoftServe
1 сентября 2020, 10:51
каждое слово понял... по отдельности🙂
Yakov Stoykov
Уровень 16
1 декабря 2019, 20:05
Как я понял, я сюда с 12 уровнем рано сунулся. 😬
5 января 2020, 08:09
+
Raphael
Уровень 41
13 апреля 2020, 02:27
++
Alukard Vampire hunter в The Hellsing Expert
18 апреля 2020, 20:57
я на седьмом как-то попал😅
Sergei Azarov
Уровень 18
4 октября 2019, 10:24
что интервьюер понимает под fail-safe? Науке это неизвестно, поэтому почитайте про Fail-fast...
Гудини
Уровень 23
8 ноября 2019, 19:46
Вроде бы по смыслу это слабо согласованные итераторы, хотя кто знает.
Андрей Кутиль
Уровень 26
9 мая 2019, 09:56
Мда, я так понимаю статья написана чисто как реклама блога. Потому что написано ужасно, это больше похоже на вырваный кусок страницы с книги на 1к страниц.
Farid
Уровень 13
28 ноября 2018, 06:04
CopyOnWriteArrayList и CopyOnWriteArraySet
Не хватает примеров по этим классам
Sergey
Уровень 41
5 сентября 2020, 07:18