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

Руководство по CopyOnWriteArrayList

· 3 мин. чтения

Задача: Медиана двух отсортированных массивов

Даны два отсортированных массива размерами n и m. Найдите медиану слияния этих двух массивов.
Временная сложность решения должна быть O(log(m + n)) ...

ANDROMEDA

1. Обзор

В этой быстрой статье мы рассмотрим CopyOnWriteArrayList из пакета java.util.concurrent .

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

2. API CopyOnWriteArrayList

В дизайне CopyOnWriteArrayList используется интересный метод, позволяющий сделать его потокобезопасным без необходимости синхронизации. Когда мы используем любой из методов модификации, таких как add() или remove() , все содержимое CopyOnWriteArrayList копируется в новую внутреннюю копию.

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

Когда мы вызываем метод iterator() для CopyOnWriteArrayList, мы возвращаем Iterator с резервной копией неизменного снимка содержимого CopyOnWriteArrayList .

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

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

3. Перебор CopyOnWriteArrayList при вставке

Допустим, мы создаем экземпляр CopyOnWriteArrayList , в котором хранятся целые числа:

CopyOnWriteArrayList<Integer> numbers 
= new CopyOnWriteArrayList<>(new Integer[]{1, 3, 5, 8});

Затем мы хотим выполнить итерацию по этому массиву, поэтому мы создаем экземпляр Iterator :

Iterator<Integer> iterator = numbers.iterator();

После создания Iterator мы добавляем новый элемент в список чисел :

numbers.add(10);

Имейте в виду, что когда мы создаем итератор для CopyOnWriteArrayList, мы получаем неизменный снимок данных в списке на момент вызова iterator() .

Из-за этого при переборе мы не увидим числа 10 в итерации:

List<Integer> result = new LinkedList<>();
iterator.forEachRemaining(result::add);

assertThat(result).containsOnly(1, 3, 5, 8);

Последующая итерация с использованием только что созданного Iterator также вернет добавленное число 10:

Iterator<Integer> iterator2 = numbers.iterator();
List<Integer> result2 = new LinkedList<>();
iterator2.forEachRemaining(result2::add);

assertThat(result2).containsOnly(1, 3, 5, 8, 10);

4. Удаление во время итерации не допускается

CopyOnWriteArrayList был создан, чтобы обеспечить возможность безопасного повторения элементов даже при изменении базового списка.

Из-за механизма копирования операция remove() для возвращаемого Iterator не разрешена, что приводит к исключению UnsupportedOperationException:

@Test(expected = UnsupportedOperationException.class)
public void whenIterateOverItAndTryToRemoveElement_thenShouldThrowException() {

CopyOnWriteArrayList<Integer> numbers
= new CopyOnWriteArrayList<>(new Integer[]{1, 3, 5, 8});

Iterator<Integer> iterator = numbers.iterator();
while (iterator.hasNext()) {
iterator.remove();
}
}

5. Вывод

В этом кратком руководстве мы рассмотрели реализацию CopyOnWriteArrayList из пакета java.util.concurrent .

Мы увидели интересную семантику этого списка и то, как его можно повторять потокобезопасным способом, в то время как другие потоки могут продолжать вставлять или удалять элементы из него.

Реализацию всех этих примеров и фрагментов кода можно найти в проекте GitHub — это проект Maven, поэтому его должно быть легко импортировать и запускать как есть.