Как обеспечить неблокирующий доступ к коллекции ArrayList при одновременном изменении из нескольких потоков в Java

Что проверяют

Понимаете ли вы, что ArrayList потокобезопасным и тем более неблокирующим не сделать, его заменяют. Следом спрашивают, чем CopyOnWriteArrayList отличается от Collections.synchronizedList и что именно в нём не блокируется.

Как отвечать

Начните с того, что ломается у обычного ArrayList: теряются добавления, при расширении массива возможен ArrayIndexOutOfBoundsException или null на месте элемента, итерация во время записи даёт ConcurrentModificationException, причём проверка fail-fast срабатывает не гарантированно.

Дальше варианты по профилю нагрузки:

• CopyOnWriteArrayList: чтение и итерация без блокировок, итератор работает по снимку. Но каждая запись копирует весь массив под внутренней блокировкой, так что это решение для списков, которые читают часто, а меняют редко: слушатели, конфигурация;
• Collections.synchronizedList: блокирующая обёртка, каждый метод под одним монитором, а итерировать нужно вручную внутри synchronized (list);
• ConcurrentLinkedQueue и ConcurrentLinkedDeque: настоящие lock-free структуры на CAS. Подходят, если нужен порядок добавления и обход, но не доступ по индексу;
• ConcurrentHashMap: если к элементам обращаются по ключу, а не по позиции;
• неизменяемый список в AtomicReference: читатель берёт текущую ссылку, писатель собирает новый список и ставит его через compareAndSet в цикле.

Часто лучший ответ убрать общий изменяемый список: каждый поток копит свой результат, а в конце их объединяют, или используют parallelStream().collect(...).

Хорошо различить термины: lock-free означает, что хотя бы один поток всегда продвигается, а «без synchronized» ещё не значит lock-free.

Где спотыкаются

Называют CopyOnWriteArrayList неблокирующим целиком. Запись в нём блокирующая и стоит O(n), на частых изменениях большой коллекции это провал по памяти и CPU.

Думают, что потокобезопасная коллекция делает атомарными составные операции. if (!list.contains(x)) list.add(x) остаётся гонкой, для этого есть addIfAbsent.

Предлагают Vector как современное решение. Это устаревший класс с той же блокировкой на каждом методе.