Повесть о двух итераторах

Когда вы посмотрите на самые популярные вопросы интервью на Java, вы можете столкнуться с вопросом об отказоустойчивых и отказоустойчивых итераторах:

В чем разница между отказоустойчивыми и отказоустойчивыми итераторами?

Упрощенный ответ таков:

Отказоустойчивый итератор создает ConcurrentModificationException если коллекция изменяется во время итерации, но отказоустойчивая — нет.

Хотя это и имеет смысл, неясно, что интервьюер подразумевает под отказоустойчивостью. Спецификация Java не определяет этот термин, когда речь идет об итераторах. Но есть четыре политики для одновременной модификации.

Параллельная модификация

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

Fail-Fast

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

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

Слабо Последовательный

Большинство одновременных коллекций из пакета java.util.concurrent (таких как ConcurrentHashMap и большинство Queues ) предоставляют слабосогласованные итераторы. Что это означает, очень хорошо объяснено в документации :

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

снимок

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

Неопределенный

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