Java: fill the gaps

Обход коллекций в Java.



Чтобы ответить на вопросы выше, посмотрим на обход более сложных сущностей, например, графа. Граф - структура данных из вершин и рёбер. В графах часто встречаются циклические пути. Найти гамильтонов путь, то есть обойти вершины графа по одному разу - непростая задача. Алгоритм ведёт учёт посещённых вершин и перебирает разные варианты прежде, чем утвердить один из них. В computer science обход структуры данных называется traverse. Основная идея — выводим текущий элемент, следующий пока неизвестен и считается отдельно.



Вернёмся в мир java. Здесь нет зацикленных графов, все просто — списки, множества, очереди, деревья. При обходе следующий элемент всегда однозначен, а его отсутствие означает конец работы. Поэтому обход выглядит так:

Iterator it=list.iterator();

while(it.hasNext()) 

   int result = it.next(); 

Метод next() возвращает текущий элемент и сразу сдвигает указатель на следующий. Метод hasNext() проверяет, ссылается ли этот указатель куда-нибудь. Этот паттерн повторяется снова и снова и называется Iteration. Важно - указатель на следующий элемент вычисляется заранее. Итератор лежит в основе синтаксиса for (T e: collection).



❌ Так как следующий элемент известен заранее, итератор может показать удалённый элемент. Или не вывести только что добавленный.



ArrayList, HashMap, HashSet и тд. не синхронизированы. Если одновременно итерировать и менять коллекцию разными потоками, можно нарушить целостность данных. Есть два способа этого избежать:

1️⃣ Fail-fast итераторы бросают ConcurrentModificationException при изменениях во время итерации.

2️⃣ Fail-safe итераторы работают с неизменяемой структурой.

Большинство однопоточных коллекций реализуют fail-fast подход.



ConcurrentHashMap потокобезопасен, поэтому изменения во время обхода разрешены. Обход через for реализован через итератор. Указатель на следующий элемент вычисляется заранее. Более подходящий новый элемент не отображается, и выводится 2 элемента.



Метод forEach в ConcurrentHashMap использует подход траверс и вычисляет следующий элемент только когда он запрашивается. Поэтому новый ключ подхватывается и выводится 3 элемента.



❓Почему нельзя использовать траверс по умолчанию?

➡️ Потому что итератор проще и работает быстрее, а условия для пропуска элемента при обходе встречаются редко.



❓Зачем нужно несколько вариантов?

➡️ ConcurrentHashMap может перестраиваться во время обхода. Чтобы во время перестройки не выводить пользователю дубликаты, используется траверс со сложной логикой.



Итого: при выводе элементов ConcurrentHashMap через for и forEach используются разные алгоритмы обхода, поэтому результат вывода тоже разный.



❗️Cинтаксис forEach реализован и для однопоточных коллекций, но там используется итератор, поэтому разницы с for нет.