Краткий ответ

CopyOnWriteArrayList при каждом изменении не модифицирует текущий массив, а создаёт его копию с новым содержимым и затем атомарно заменяет ссылку на массив. Поэтому добавление, удаление и замена элемента обычно требуют O(n) времени и дополнительной памяти, тогда как чтение по индексу остаётся O(1).

Исторический контекст

Подход copy-on-write появился как решение для коллекций, в которых чтения происходят значительно чаще изменений. Его цель — предоставить безопасное чтение из нескольких потоков без блокировки каждого читателя.

В Java такой сценарий представлен классом CopyOnWriteArrayList из пакета java.util.concurrent. Цена простого и быстрого чтения переносится на операции изменения: они становятся дороже и выполняются последовательно.

Постановка проблемы

Если обычный изменяемый список одновременно читают и изменяют разные потоки, без синхронизации возможны гонки, повреждение наблюдаемого состояния и ошибки при обходе. Полная блокировка списка решает проблему согласованности, но заставляет читателей конкурировать с писателями.

У CopyOnWriteArrayList читатели не блокируют друг друга и не ждут завершения записи. Однако использование этой коллекции для большого списка с частыми изменениями приводит к постоянному копированию массива, повышенному выделению памяти и дополнительной нагрузке на сборщик мусора.

Подробное решение

Внутри коллекция хранит ссылку на массив элементов. Операция чтения получает актуальный массив и обращается к его элементу; для get это O(1). Итератор также запоминает массив, существовавший на момент создания, поэтому последующие изменения списка не требуют блокировки текущего обхода.

Операция записи захватывает внутреннюю блокировку, создаёт новый массив, копирует в него старые элементы, вносит изменение и публикует новую ссылку на массив. Копирование занимает O(n) времени и требует примерно O(n) дополнительной памяти на время операции.

Например:

import java.util.concurrent.CopyOnWriteArrayList;

var events = new CopyOnWriteArrayList<String>();
events.add("start");

for (String event : events) {
    events.add("audit");
}

System.out.println(events); // [start, audit]

Итератор проходит по снимку, созданному до добавления, поэтому новый элемент не появляется в текущем обходе. Само добавление всё равно создало новый массив.

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

Ситуация из практики

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

Рассматривались три варианта. ArrayList без синхронизации был небезопасен; синхронизированная коллекция обеспечивала корректность, но блокировала читателей; CopyOnWriteArrayList увеличивала стоимость редкого обновления, зато позволяла безопасно обходить список без блокировки читателей.

Выбран был CopyOnWriteArrayList, поскольку список небольшой, чтений на порядки больше, чем изменений, а задержка обновления конфигурации некритична. В результате чтения выполнялись без конкуренции за общий lock, а стоимость копирования возникала только при смене конфигурации.

Что кандидаты часто упускают

Можно ли считать операции чтения полностью независимыми от записи?

Читатели не блокируют писателей и друг друга, но они видят конкретный опубликованный снимок массива. Чтение, начавшееся до публикации новой версии, может увидеть старое содержимое; это нормальное свойство snapshot-семантики, а не ошибка согласованности.
Почему CopyOnWriteArrayList не подходит для частых добавлений?

Каждое добавление копирует весь массив, поэтому серия из m добавлений в список размера порядка n может суммарно потребовать порядка O(mn) копирований. Помимо времени, создаётся много временных массивов, что увеличивает давление на сборщик мусора; для такого сценария обычно выбирают другую concurrent-структуру или явную пакетную замену списка.
Защищает ли CopyOnWriteArrayList составной сценарий «проверить, затем изменить»?

Нет. Отдельные операции коллекции потокобезопасны, но последовательность нескольких операций не становится атомарной автоматически. Если решение зависит от результата проверки и последующего изменения, требуется подходящая атомарная операция самой коллекции либо внешняя синхронизация.