Перейти к основному содержимому

Коллекции в Java

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ
Разработчику Архитектору

Дальше: Типы данных и переменные · Справочник Java

Сначала — теория (раздел 3 "Данные")

Структуры данных — о разделе → реализация и псевдокод операций → Коллекции в контексте ООП.

Ниже — List, Set, Map в Java.

Примеры HashMap, HashSet, подсчёт частот — Lab / консольные задачи, раздел 2.

список.добавить(элемент)              // ArrayList — в конец, O(1) амортиз.
значение := список.получить(индекс)   // O(1)

словарь.записать(ключ, значение)      // HashMap — в среднем O(1)
значение := словарь.прочитать(ключ)

множество.добавить(x)                 // HashSet — уникальность

Play ITЗагрузка интерактивного демо…

Play ITЗагрузка интерактивного демо…

Коллекции в Java​

Что такое коллекция​

★ Коллекции в Java – сложный инструмент для работы с данными, который позволяет хранить, обрабатывать и манипулировать группами объектов.

На практике коллекции решают почти любую задачу "работы со множеством значений": от списка кнопок в UI до кэша результатов запросов и набора уникальных идентификаторов.

Collection — это интерфейс в java.util, который задаёт общий контракт для всех коллекций, хранящих группы объектов. Через него определяются ключевые операции — добавление и удаление элементов, проверка их наличия, очистка коллекции, получение размера и итерация.

Фреймворк коллекций Java (Java Collections Framework, пакет java.util и java.util.concurrent) задаёт общие интерфейсы и взаимозаменяемые реализации. На собеседованиях и в повседневном коде чаще всего встречаются четыре семейства — List, Set, Map, Queue.

Collection
    ├── List
    │   ├── ArrayList          — динамический массив
    │   ├── LinkedList         — двусвязный список; также реализует Deque/Queue
    │   ├── Vector             — синхронизированный ArrayList (legacy)
    │   └── CopyOnWriteArrayList — потокобезопасный список «копия при записи»
    ├── Set
    │   ├── HashSet
    │   ├── LinkedHashSet      — порядок вставки
    │   ├── TreeSet            — сортировка по Comparable/Comparator
    │   └── EnumSet            — множество значений enum
    └── Queue
        ├── PriorityQueue      — куча, по умолчанию минимум на выходе
        ├── ArrayDeque         — быстрая очередь и стек
        └── BlockingQueue*     — потокобезопасная очередь (* java.util.concurrent)

Map (отдельная иерархия, не extends Collection)
    ├── HashMap
    ├── LinkedHashMap          — порядок вставки / access-order (LRU-кэши)
    ├── TreeMap                — сортировка по ключу
    ├── Hashtable              — legacy, synchronized
    └── ConcurrentHashMap      — конкурентный доступ без блокировки всей таблицы

Основные реализации — List, Set, Queue и Map. Интерфейс Collection сам по себе не потокобезопасен: для многопоточности используют обёртки Collections.synchronized*() или классы из java.util.concurrent. Дженерики (List<String>) дают типобезопасность на этапе компиляции.

Map не наследуется от Collection, потому что хранит пары ключ–значение, а не отдельные элементы.

Популярные реализации — когда что брать​

ЗадачаСтруктура
Быстрый доступ по индексуArrayList
Частые вставки/удаления в начале или серединеLinkedList
Только уникальные элементыHashSet
Пары ключ–значениеHashMap
Очередь FIFO или стек LIFO в алгоритмахArrayDeque
Очередь с приоритетомPriorityQueue
Потокобезопасный словарьConcurrentHashMap

Сложность типовых операций (средний случай)​

Оценки для собеседования; у Hash* при плохом распределении хешей время может деградировать.

Реализацияget / containsВставка в конецВставка в середину
ArrayListO(1) по индексуO(1) амортиз.O(n)
LinkedListO(n) по индексуO(1)O(1) с итератором
HashSet / HashMapO(1)O(1)—
TreeSet / TreeMapO(log n)O(log n)—
PriorityQueue—O(log n) offer—

Ordered и Sorted (частый вопрос на собеседовании)​

ТерминСмыслПримеры
OrderedЕсть предсказуемый порядок обхода (не обязательно "по значению")ArrayList — по индексу вставки; LinkedHashSet / LinkedHashMap — порядок добавления
SortedПорядок задаётся правилом сравнения (Comparable / Comparator)TreeSet, TreeMap

HashSet и HashMap — ни ordered, ни sorted: порядок итерации не гарантирован. TreeSet — и ordered, и sorted. На собеседовании не путайте "упорядочен по индексу" (List) с "отсортирован по значению" (Tree*).

Сводка операций по типам​

List (упорядоченный список с индексами, дубликаты допустимы):

ДействиеМетод
Добавить в конецadd(value)
Вставить по индексуadd(index, value)
Прочитатьget(index)
Заменитьset(index, value)
Удалить по индексуremove(index)

Set (уникальные элементы, доступ по значению, без индекса):

ДействиеМетод
Добавитьadd(value)
Удалитьremove(value)
Проверить наличиеcontains(value)

Map (пары ключ–значение, ключи уникальны):

ДействиеМетод
Добавить или заменитьput(key, value)
Прочитатьget(key)
Удалить по ключуremove(key)
Проверить ключ / значениеcontainsKey(key), containsValue(value)

Queue (FIFO — первым вошёл, первым вышел; без доступа по индексу):

ДействиеМетод
Добавить в хвостoffer(value)
Прочитать голову (без удаления)peek()
Извлечь головуpoll()

Deque (очередь с двумя концами + стек):

ДействиеМетод
В конец (очередь)offerLast(value)
В началоofferFirst(value)
Стек: push/poppush(value), pop()
Просмотр концовpeekFirst(), peekLast()

PriorityQueue: те же offer / poll, порядок извлечения — по приоритету (компаратор или Comparable).

Реализации (ArrayList, HashMap, HashSet и др.) поддерживают эти контракты интерфейсов; ниже — нюансы производительности и порядка обхода.

Collection​

Collection – корневой интерфейс, представляющий собой группу элементов (объектов). Он определяет базовые операции над набором данных — добавление, удаление, проверка наличия, размер и т.д.

Данных бывает много, и в памяти их как-то надо структурировать.

Упорядочить – вывод списка пользователей в том порядке, в котором они регистрировались (ArrayList, LinkedHashMap).

Исключать дубликаты – например, загрузка данных из разных источников и удаление повторяющихся записей (HashSet, LinkedHashSet).

Сортировать – рейтинг игроков, сортировка товаров по цене (TreeSet, TreeMap).

Хранить пары "ключ-значение" - кэширование результатов вычислений, например (HashMap, TreeMap).

Работать с очередями и приоритетами – обработка задач в фоновых потоках (PriorityQueue, Deque).

Коллекции активно используются в веб-приложениях, бизнес-логике (валидация, фильтрация), алгоритмах (поиск, сортировка), параллелизме (concurrent коллекции). Функциональная обработка коллекций — в Stream API.

У этого интерфейса есть основные подынтерфейсы:

  • List – упорядоченная коллекция с дубликатами;
  • Set – коллекция без дубликатов (порядок зависит от реализации);
  • Queue – очередь, используется для обработки элементов по принципу FIFO (First In, First Out, первый зашел - первый вышел);
  • Deque – двусторонная очередь.
  • Map не является частью иерархии Collection, но часто рассматривается вместе с ними.

List​

List – упорядоченные списки. Реализует интерфейс List<E>. Поддерживает индексацию и дублирование элементов. Существуют реализации через ArrayList, LinkedList, Vector.

ArrayList​

ArrayList – реализован на основе динамического массива (Array – это массив). Имеет быстрый доступ по индексу, медленную вставку/удаление в середине.

Если нет специальных требований, ArrayList обычно является базовым выбором в business-коде: структура проста, предсказуема и хорошо оптимизируется JVM.

ArrayList, как можно понять из слова Array, основан на обычном массиве (Object[]). При создании выделяется массив фиксированного начального размера (по умолчанию 10).

При добавлении элемента сверх вместимости создается новый массив большего размера (обычно в 1.5 раза) и копируются старые данные.

Пример:

List<String> list = new ArrayList<>();
list.add("Java");

Разбор:

  • Переменная объявлена через интерфейс List, а не конкретный класс, что упрощает замену реализации без переписывания клиентского кода.
  • new ArrayList<>() создаёт динамический массив с возможностью автоматического роста при добавлении элементов.
  • Метод add("Java") вставляет элемент в конец списка и в среднем работает за амортизированное O(1).
  • Такой минимальный пример показывает базовый контракт List: упорядоченность, индексация и поддержка дубликатов.

Операции:

  • add(value) — добавление в конец;
  • add(index, value) — вставка в середину;
  • get(index) — чтение по индексу;
  • set(index, value) — замена по индексу;
  • remove(index) — удаление.

Давайте рассмотрим разницу между ArrayList и LinkedList:

Код ITЗагрузка примера кода…

ArrayList — выбор по умолчанию (80% случаев). Использовать в принципе можно всегда, особенно если в основном происходит чтение по индексу, часто проходим по списку в цикле, или не знаем, что выбрать.

List<String> names = new ArrayList<>();
names.add("Alice");    // быстро
names.add("Bob");
String name = names.get(0); // моментально

ArrayList занимает меньше памяти на элемент (только ссылка + маленький overhead массива). LinkedList значительно больше памяти на элемент — каждый узел хранит 3 ссылки (предыдущий, следующий, данные) + объект Node. Для 1 млн элементов разница может быть в 5-10 раз!

При добавлении 11-го элемента в список с capacity=10:

  • Создается новый массив на 15 элементов.
  • Копируются все 10 старых. Это дорого, но случается редко (амортизированно O(1)).

LinkedList​

LinkedList – реализован как двусвязный список. Быстрая вставка/удаление, медленный доступ по индексу. Пример:

List<Integer> numbers = new LinkedList<>();
numbers.add(10);

LinkedList реализован как двусвязный список узлов (Node). Каждый узел хранит данные, ссылку на предыдущий и следующий узел.

Как устроен LinkedList внутри? Упрощённо, как-то так:

private static class Node<E> {
    E item;          // данные
    Node<E> next;    // ссылка на следующий узел
    Node<E> prev;    // ссылка на предыдущий узел
}

Пример:

[null] ← [Узел 1] ↔ [Узел 2] ↔ [Узел 3] → [null]
           │          │          │
        "Кошка"    "Собака"    "Попугай"
  • Первый узел (head): prev = null;
  • Последний узел (tail): next = null;
  • Каждый узел хранит три вещи: данные + две ссылки.

ArrayList при удалении из начала:

list.remove(0); // Удалит первый элемент и сдвинет все остальные — О(n)

LinkedList при get(index):

list.get(250000); // LinkedList пройдет 250000 узлов от начала — очень медленно!

Не требует непрерывного блока памяти — узлы могут быть разбросаны по куче.

Операции:

  • add(value) — добавление в конец;
  • add(index, value) — вставка в середину;
  • get(index) — чтение по индексу;
  • set(index, value) — замена по индексу;
  • remove(index) — удаление.

LinkedList является ускоспециализированной структурой, поэтому её использовать стоит, если количество операций get(index) минимально или отсутствует, если часто вставляют или удаляют элементы в середине или начале списка доступными итераторами.

Vector​

Vector (устаревший) – похож на ArrayList, но каждая операция синхронизирована, поэтому в однопоточном коде медленнее. В новых проектах не используют. Пример:

List<String> legacyList = new Vector<>();

CopyOnWriteArrayList​

CopyOnWriteArrayList — потокобезопасный List из java.util.concurrent. При изменении (add, set, remove) создаётся копия внутреннего массива; чтение и итерация идут по снимку без блокировок. Подходит, когда чтений много, а записей мало (списки подписчиков, конфигурация, снапшоты для итерации). Итератор такого списка относится к fail-safe — подробнее в разделе Fail-fast и fail-safe итераторы.

List<String> listeners = new CopyOnWriteArrayList<>();
listeners.add("handler-1");
for (String h : listeners) { /* без ConcurrentModificationException */ }

Не подходит для частых мутаций: каждая запись копирует весь массив.

Set​

Set – набор уникальных элементов. Интерфейс Set<E> гарантирует отсутствие дубликатов. Существуют реализации через HashSet, LinkedHashSet, TreeSet.

давайте рассмотрим разницу между ними:

Код ITЗагрузка примера кода…

Set — операции интерфейса​

Для HashSet, LinkedHashSet, TreeSet и других реализаций Set доступен один и тот же набор мутаций:

  • add(value) — добавление (дубликат игнорируется);
  • remove(value) — удаление по значению;
  • contains(value) — проверка принадлежности;
  • clear() — очистка;
  • size(), isEmpty() — размер и пустота.

Доступа по индексу у множества нет: элемент ищется по equals / hashCode.

HashSet​

HashSet хранит только уникальные элементы. Внутри — хеш-таблица — в среднем O(1) на add, remove, contains. Порядок обхода не гарантирован. Пример:

Set<String> set = new HashSet<>();
set.add("Apple");

LinkedHashSet​

LinkedHashSet сохраняет порядок вставки элементов. Это комбинация HashSet и связанного списка. Пример:

Set<String> orderedSet = new LinkedHashSet<>();
orderedSet.add("First");

TreeSet​

TreeSet хранит элементы в отсортированном порядке (естественный порядок Comparable или Comparator). Операции — O(log n), реализация на красно-чёрном дереве. Пример:

Set<Integer> sortedSet = new TreeSet<>();
sortedSet.add(5);

EnumSet​

EnumSet — специализированное множество для типов enum. Внутри — битовая маска по константам перечисления: компактно и быстрее общего HashSet для enum. Порядок итерации совпадает с объявлением констант в enum. null не допускается.

enum Day { MON, TUE, WED }
Set<Day> workdays = EnumSet.of(Day.MON, Day.TUE, Day.WED);
Set<Day> weekend = EnumSet.complementOf(workdays);

Play ITЗагрузка интерактивного демо…

Map​

Map – словарь (ключ и значение). Ключи уникальны.

Операции (интерфейс Map, общие для HashMap, TreeMap, LinkedHashMap):

  • put(key, value) — добавление пары или замена значения по существующему ключу;
  • get(key) — чтение значения (null, если ключа нет);
  • remove(key) — удаление записи по ключу;
  • putIfAbsent(key, value) — записать только если ключа ещё не было;
  • replace(key, value) — заменить значение, если ключ есть;
  • containsKey(key), containsValue(value) — проверки;
  • keySet(), values(), entrySet() — представления для обхода.
Map (интерфейс)
    ├── HashMap (класс) - неупорядоченное отображение
    ├── LinkedHashMap (класс) - упорядоченное по вставке
    ├── TreeMap (класс) - упорядоченное по ключу
    └── Hashtable (класс) - синхронизированное отображение

Пример работы с ключами, значениями и порядком:

Код ITЗагрузка примера кода…

Разбор:

  • Пример сравнивает три реализации Map: HashMap (без порядка), LinkedHashMap (порядок вставки) и TreeMap (сортировка по ключу).
  • scores.put("Alice", 99) демонстрирует ключевое свойство словаря: повторная запись с тем же ключом перезаписывает старое значение.
  • history.keySet() показывает, что LinkedHashMap сохраняет последовательность добавления и полезен для сценариев с историей.
  • TreeMap автоматически поддерживает отсортированный обход, поэтому данные выводятся в порядке возрастания ключей без дополнительной сортировки.

HashMap​

HashMap — базовая реализация словаря (пары ключ–значение). В среднем O(1) на get, put, remove. Допускает один null-ключ и несколько null-значений; порядок итерации не гарантирован. Это выбор по умолчанию для кэшей, счётчиков, индексов в памяти.

Пример:

Map<String, Integer> map = new HashMap<>();
map.put("one", 1);

TreeMap​

TreeMap – реализован на основе красно-чёрного дерева. Хранит пары в отсортированном по ключам порядке. Пример:

Map<String, Integer> sortedMap = new TreeMap<>();
sortedMap.put("banana", 2);

Hashtable​

Hashtable – устаревшая, синхронизированная версия HashMap. Не позволяет использовать null в ключах и значениях. Вместо Hashtable лучше использовать ConcurrentHashMap или Collections.synchronizedMap(). Пример:

Map<String, String> legacyMap = new Hashtable<>();
legacyMap.put("key", "value");

LinkedHashMap​

LinkedHashMap сохраняет порядок вставки (или порядок доступа при accessOrder = true — основа LRU-кэшей). Те же O(1), что у HashMap, плюс связный список для порядка. Пример:

Map<String, String> history = new LinkedHashMap<>();
history.put("first", "start");

ConcurrentHashMap​

ConcurrentHashMap (java.util.concurrent) — потокобезопасная HashMap для конкурентного чтения и записи без синхронизации всей таблицы на каждую операцию (в отличие от Hashtable). null в ключах и значениях запрещён. Используют для общих кэшей, реестров и счётчиков в многопоточных сервисах. Её итератор слабо согласованный (fail-safe) — см. ниже.

Map<String, Integer> cache = new ConcurrentHashMap<>();
cache.merge("hits", 1, Integer::sum);

На собеседовании не путайте с Collections.synchronizedMap(new HashMap<>()) — там блокируется вся карта на каждый вызов.

Play ITЗагрузка интерактивного демо…

Queue​

Queue — очередь: элементы обрабатываются по принципу FIFO (первым вошёл — первым вышел). LinkedList реализует и List, и Deque, и Queue, но для очереди и стека в новом коде предпочитают ArrayDeque — меньше накладных расходов, чем у Stack и LinkedList.

РеализацияНазначение
ArrayDequeFIFO-очередь и LIFO-стек в алгоритмах
PriorityQueueизвлечение по приоритету (куча, по умолчанию минимум)
LinkedListредко как очередь; чаще как список с частыми вставками
ArrayBlockingQueue, LinkedBlockingQueueproducer–consumer, backpressure, пулы потоков

Операции интерфейса Queue (типичная реализация — ArrayDeque):

  • offer(e) — добавить в хвост (предпочтительнее add для очередей: offer не бросает исключение при переполнении);
  • poll() — извлечь и удалить голову (null, если пусто);
  • peek() — посмотреть голову без удаления;
  • element() — как peek, но NoSuchElementException, если пусто. PriorityQueue – элементы извлекаются в порядке приоритета (по значению или с помощью компаратора). Не поддерживает null. Пример:
Queue<Integer> queue = new PriorityQueue<>();
queue.offer(3);
queue.poll(); // 3 (если минимальный)

Пример работы принципов LIFO и FIFO:

Код ITЗагрузка примера кода…

Разбор:

  • PriorityQueue извлекает элементы по приоритету, а не по времени вставки: poll() возвращает минимальный элемент для Integer.
  • Deque (ArrayDeque) совмещает две модели: FIFO-очередь через offerLast/poll и LIFO-стек через push/pop.
  • peekLast() читает хвост без удаления, а pop() удаляет и возвращает элемент из головы дека в стековом режиме.
  • Цикл while (!deque.isEmpty()) безопасно освобождает структуру до конца, извлекая элементы по текущим правилам очереди.

BlockingQueue​

BlockingQueue (java.util.concurrent) — потокобезопасная очередь для схемы producer–consumer. put ждёт свободного места, take ждёт элемента — удобно связывать потоки без ручного wait/notify. Примеры — ArrayBlockingQueue (фиксированная ёмкость), LinkedBlockingQueue, PriorityBlockingQueue.

BlockingQueue<String> tasks = new ArrayBlockingQueue<>(1000);
tasks.put("job-1");   // блокируется, если очередь полна
String job = tasks.take(); // блокируется, если пусто

Deque​

Deque (Double Ended Queue) – можно добавлять или удалять элементы с обоих концов. Реализуется через ArrayDeque или LinkedList.

Операции Deque:

РольВ началоВ конец
ДобавитьofferFirst, addFirstofferLast, addLast
ИзвлечьpollFirst, removeFirstpollLast, removeLast
ПросмотрpeekFirstpeekLast

Как стек (LIFO): push(e) ≡ addFirst, pop() ≡ removeFirst (для ArrayDeque).

Пример:

Deque<String> deque = new ArrayDeque<>();
deque.push("first");
deque.pop();

Давайте теперь разберём, когда что использовать.

Виды​

ТипКогда использоватьПример
ArrayListНужен быстрый доступ по индексуСписок пользователей, список товаров в корзине
LinkedListЧастые вставки или удаления в начале или серединеРеализация очереди, стека, история действий (undo/redo)
HashSetНужны уникальные элементы, порядок не важенПроверка уникальности email, фильтрация дубликатов из базы данных
LinkedHashSetНужна уникальность и сохранение порядка вставкиИстория посещённых страниц, удаление дубликатов с сохранением порядка
TreeSetНужен отсортированный наборРейтинг игроков, очередь задач с приоритетом
HashMapОбычный словарь, скорость важнее порядкаКэширование объектов по ключу, хранение параметров конфигурации
LinkedHashMapНужен порядок вставкиЛог-файл с записями в порядке добавления, кэш LRU (Least Recently Used)
TreeMapНужен отсортированный словарьРейтинг студентов, поиск значений в диапазоне (например, дат)
PriorityQueueНужна очередь с приоритетомСистема обслуживания в банке, планировщик задач
ArrayDequeОчередь FIFO или стек LIFOОбход графа, парсинг, отмена действий
CopyOnWriteArrayListМного читателей, редкие записиСписок слушателей, снапшот для итерации
EnumSetМножество констант enumФлаги дней недели, разрешённые роли
ConcurrentHashMapОбщий словарь в нескольких потокахКэш, счётчики, реестр сервисов
BlockingQueueProducer–consumer между потокамиПул задач, буфер событий
Vector / HashtableУстаревшие, лучше избегать в новых проектахПоддержка устаревшего кода; вместо них — ConcurrentHashMap, CopyOnWriteArrayList

Класс Collections​

Утилитный класс java.util.Collections (не путать с Collections Framework) — статические методы над коллекциями и массивами-списками.

МетодНазначение
Collections.sort(list)сортировка List на месте (Comparable или Comparator)
Collections.reverse(list)разворот порядка
Collections.shuffle(list)случайная перестановка
Collections.unmodifiableList(list)представление только для чтения (изменения исходного списка всё ещё видны)
Collections.synchronizedList(list)обёртка с синхронизацией каждого вызова
Collections.emptyList(), singletonList(x)пустой и одноэлементный списки

В Java 9+ для неизменяемых коллекций предпочтительны фабрики List.of(), Set.of(), Map.of().

List<String> names = new ArrayList<>(List.of("Bob", "Ann", "Zoe"));
Collections.sort(names);
Collections.reverse(names);
List<String> readOnly = Collections.unmodifiableList(names);

Общие методы коллекций​

Все коллекции имеют общие методы, но не все реализации поддерживают все операции. Давайте соберём важнейшие:

  • add(E e) добавляет элемент в коллекцию, используется в List, Set, Queue, для Set игнорирует дубликаты.
  • remove(Object o) удаляет указанный элемент, используется во всех коллекциях, возвращает true, если элемент был найден.
  • contains(Object o) проверяет наличие элемента, использует equals() и hashCode().
  • containsKey() и containsValue() проверет наличие элемента для Map;
  • get(int index) получает элемент по индексу, используется только в List, причем в ArrayList – делает быстро, в LinkedList – медленно.
  • put(K key, V value) добавляет пару ключ-значение, используется в Map, перезаписывает значение, если ключ уже есть.
  • get(Object key) получает значение по ключу, используется в Map, возвращает null, если ключ не найден.
  • poll() извлекает и удаляет первый элемент, используется в Queue, Deque, возвращает null, если очередь пуста.
  • offer(E e) добавляет элемент в очередь, используется в Queue, возвращает false, если не удалось добавить.
  • peek() возвращает, но не удаляет первый элемент, используется в Queue, полезно для проверки перед извлечением.

Примеры:

Код ITЗагрузка примера кода…

Fail-fast и fail-safe итераторы​

Обход коллекции — последовательный просмотр элементов. В Java для этого используют

  • цикл for-each (for (String s : list));
  • интерфейс Iterator с методами hasNext(), next(), remove();
  • внутри for-each JVM создаёт Iterator автоматически (циклы в Java, паттерн "Итератор").

Пока итератор переходит к следующему элементу, код может изменить коллекцию. Структурная модификация — любое действие, которое меняет размер или внутреннюю схему хранения

  • add, remove, clear у списка или множества;
  • put с новым ключом, remove по ключу у Map.

Замена значения на месте (list.set, map.put с уже существующим ключом) структурой не считается — счётчик модификаций при этом не меняется.

Реализации из java.util дают fail-fast итераторы

Классы java.util.concurrent обходят коллекцию по стратегии fail-safe

  • CopyOnWriteArrayList, ConcurrentHashMap;
  • у ConcurrentHashMap в документации JDK тот же смысл называют слабо согласованным (weakly consistent) итератором.

Сравнение стратегий​

Fail-fastFail-safe
Типичные классыArrayList, HashMap, HashSetCopyOnWriteArrayList, ConcurrentHashMap
Изменение во время обходаConcurrentModificationExceptionобход продолжается
Задача механизмасразу показать ошибку в логике программыустойчивый обход при параллельных записях

Счётчик modCount​

У изменяемых коллекций java.util есть скрытое поле modCount — счётчик структурных изменений. Каждый add, remove, clear (и аналоги у Map) увеличивают его на единицу.

При создании итератора запоминается expectedModCount = modCount. Перед каждым шагом (next(), hasNext()) итератор сравнивает ожидаемое значение с текущим. Если числа разошлись — коллекцию меняли, пока шёл обход, и JVM бросает исключение.

List<String> list = new ArrayList<>(List.of("a", "b", "c"));
for (String s : list) {
    if (s.equals("b")) {
        list.remove(s); // ConcurrentModificationException
    }
}

Цикл for-each вызывает list.remove() напрямую, минуя итератор. Итератор об этом не узнаёт через свой API, зато modCount уже другой — срабатывает проверка.

Fail-fast помогает отладке в одном потоке. ConcurrentModificationException указывает на место, где коллекцию изменили во время обхода (иерархия исключения).

Синхронизация потоков решается другими средствами. Два потока могут одновременно писать в ArrayList — данные испортятся без гарантированного исключения. Общий доступ оформляют через потокобезопасные коллекции и блокировки. Fail-fast описывает корректный однопоточный обход через Iterator и for-each.

Как безопасно удалять при fail-fast обходе​

  • Iterator.remove() — единственный способ удаления, встроенный в сам обход;
  • removeIf(условие) — внутри вызывает итератор;
  • новая коллекция — собрать элементы, которые нужно оставить, в отдельный List;
  • Stream + filter + collect — для декларативной фильтрации (Stream API).
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("b")) {
        it.remove(); // modCount обновляется согласованно с итератором
    }
}

Тот же смысл в одну строку — list.removeIf(s -> s.equals("b")).

Снимок и слабая согласованность​

Конкурентные коллекции из java.util.concurrent не опираются на modCount при обходе.

CopyOnWriteArrayList при записи копирует весь внутренний массив. Итератор, созданный до add или remove, читает снимок старого массива. Элементы, добавленные после старта цикла, в этом проходе не появятся — поведение задокументировано. Подробнее о классе — выше.

ConcurrentHashMap выдаёт слабо согласованный итератор

  • показывает состояние карты на момент создания и всё, что успело появиться позже;
  • не обещает увидеть каждое свежее изменение;
  • может кратко показать элемент, который другой поток уже удалил;
  • при параллельных put и remove обход не прерывается исключением.

Описание класса — выше. Общая картина коллекций в коде — Коллекции в контексте ООП.

Ограничения fail-safe реализаций​

  • итератор отстаёт от "живой" коллекции — свежие записи могут не попасть в текущий проход;
  • CopyOnWriteArrayList при частых add/remove копирует массив целиком — растут расход памяти и время CPU;
  • ConcurrentHashMap защищает отдельные операции get/put, но составной сценарий "прочитал — посчитал — записал" всё равно требует synchronized, Lock или атомарных структур (многопоточность в Java).
Fail-fast и потокобезопасность

Fail-fast проверяет согласованность обхода и структурных изменений в одном потоке.
Fail-safe держит итератор рабочим, когда коллекцию меняют параллельно.
Выбор реализации (ArrayList, CopyOnWriteArrayList, Collections.synchronizedList и др.) зависит от того, сколько потоков читает и пишет данные — см. JVM, память и потоки.

Как не утонуть в выборе коллекции​

Практическое правило для старта:

  1. Начинайте с ArrayList и HashMap.
  2. Переходите на LinkedHashMap или TreeMap, когда нужен порядок.
  3. Используйте HashSet, когда важна уникальность.
  4. Берите ArrayDeque для стека и очереди в алгоритмах.
О сложности операций

Почти все "быстрые" оценки для Hash* структур — это средний случай. При плохих хешах или перегрузке бакетов фактическое время может вырасти.

Частые ошибки при работе с коллекциями​

  • Удаление или добавление в for-each без Iterator.remove() — ConcurrentModificationException у fail-fast коллекций (разбор механизма).
  • Использование изменяемого объекта как ключа HashMap.
  • Ожидание фиксированного порядка у HashSet/HashMap.
  • Сравнение сложности ArrayList и LinkedList без учёта реального профиля операций.

Связанные статьи​

Содержание