Какие знаешь реализации листов, которые поддерживают внутреннее копирование во время итерирования?

Реализации List с внутренним копированием во время итерирования

Copy-On-Write коллекции решают проблему потокобезопасности при одновременном чтении и записи. Ключевая идея: вместо блокировки при каждой записи, создаётся копия массива при каждой модификации. Это даёт эффективное чтение за счёт более дорогой записи.

1. CopyOnWriteArrayList

Это основная реализация Copy-On-Write паттерна в Java Collections Framework:

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, Serializable

Как работает

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("A");
list.add("B");
list.add("C");

// ИТЕРИРОВАНИЕ
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
    
    // Внутренне: iterator хранит снимок массива из момента создания
    // Поэтому даже если мы модифицируем list, iterator не видит изменений
}

// МОДИФИКАЦИЯ во время итерирования — БЕЗОПАСНО!
list.add("D");  // Создаёт новую копию внутреннего массива
list.remove(0); // Ещё одна копия
list.set(1, "B-modified"); // И ещё одна копия

// Iterator по-прежнему итерирует старую копию
while (iterator.hasNext()) {
    System.out.println(iterator.next());  // A, B, C (не видит D)
}

Реализация модификации

public class CopyOnWriteArrayList<E> {
    private transient volatile Object[] array;  // Volatile!
    
    public boolean add(E e) {
        synchronized(this) {  // Только одна запись одновременно
            Object[] elements = array;
            int len = elements.length;
            
            // КОПИРОВАНИЕ: создаём новый массив
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            
            // Атомично заменяем reference
            array = newElements;
            return true;
        }
    }
    
    // ЧТЕНИЕ — безопасно без синхронизации
    public E get(int index) {
        return (E) array[index];  // Просто читаем, никаких блокировок
    }
}

Создание Iterator

public class CopyOnWriteArrayList<E> {
    public Iterator<E> iterator() {
        // Снимок массива в момент создания iterator
        return new COWIterator<E>(array, 0);
    }
}

private static class COWIterator<E> implements Iterator<E> {
    private final Object[] snapshot;  // Неизменяемая копия
    private int cursor;
    
    public COWIterator(Object[] elements, int initialCursor) {
        this.snapshot = elements;  // Снимок в момент создания
        this.cursor = initialCursor;
    }
    
    public boolean hasNext() {
        return cursor < snapshot.length;
    }
    
    public E next() {
        if (cursor >= snapshot.length)
            throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }
    
    // remove() не поддерживается!
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

Пример безопасной итерации

CopyOnWriteArrayList<String> cities = new CopyOnWriteArrayList<>();
cities.add("Moscow");
cities.add("SPB");
cities.add("Kazan");

// Поток 1: итерирует
Thread t1 = new Thread(() -> {
    for (String city : cities) {
        System.out.println("T1: " + city);
        try { Thread.sleep(100); } catch (InterruptedException e) {}
    }
});

// Поток 2: модифицирует список
Thread t2 = new Thread(() -> {
    cities.add("Yekaterinburg");
    cities.add("Novosibirsk");
    cities.remove("SPB");
});

t1.start();
Thread.sleep(50);
t2.start();
t1.join();
t2.join();

// T1 итерировал старый снимок: Moscow, SPB, Kazan
// T2 модифицировал список без блокирования T1

Когда использовать CopyOnWriteArrayList

✓ Хорошо для:

• Много читателей, мало писателей
• Итерирование в multi-threaded окружении
• Слушатели событий (Event listeners)
• Кэши, которые редко обновляются

✗ Плохо для:

• Частые модификации (O(n) за каждую операцию)
• Большие списки (копирование всего массива дорого)

2. CopyOnWriteArraySet

Аналог CopyOnWriteArrayList, но для Set:

public class CopyOnWriteArraySet<E> extends AbstractSet<E> {
    private final CopyOnWriteArrayList<E> al;  // Внутренне использует List
    
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<>();
    }
    
    public boolean add(E e) {
        return al.addIfAbsent(e);  // Добавляет только если отсутствует
    }
}

// Пример
CopyOnWriteArraySet<Integer> set = new CopyOnWriteArraySet<>();
set.add(1);
set.add(2);
set.add(3);

for (Integer val : set) {
    System.out.println(val);
    set.add(4);  // Безопасно!
}

3. Collections.synchronizedList vs CopyOnWriteArrayList

Разница в подходах:

// synchronizedList — блокирует каждую операцию
List<String> syncList = Collections.synchronizedList(new ArrayList<>());

// Если итерируем, нужна явная синхронизация:
List<String> list = Collections.synchronizedList(new ArrayList<>());
synchronized(list) {  //必須!
    for (String item : list) {
        // ConcurrentModificationException без этого!
        System.out.println(item);
    }
}

// CopyOnWriteArrayList — не требует явной синхронизации
CopyOnWriteArrayList<String> cowList = new CopyOnWriteArrayList<>();nfor (String item : cowList) {  // Безопасно БЕЗ синхронизации
    System.out.println(item);
    cowList.add("new");  // Тоже безопасно!
}

4. Снимки и Snapshot Iterator Pattern

Это общий паттерн для безопасного итерирования:

public class SnapshotList<E> {
    private List<E> data = new ArrayList<>();
    private final Object lock = new Object();
    
    public void add(E element) {
        synchronized(lock) {
            data.add(element);
        }
    }
    
    // Iterator получает снимок в момент создания
    public Iterator<E> iterator() {
        synchronized(lock) {
            // Копируем данные
            return new ArrayList<>(data).iterator();
        }
    }
    
    // Пример использования
    public static void main(String[] args) throws InterruptedException {
        SnapshotList<Integer> list = new SnapshotList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        
        Iterator<Integer> it = list.iterator();
        list.add(4);  // Список изменился
        
        while (it.hasNext()) {
            System.out.println(it.next());  // 1, 2, 3 (без 4)
        }
    }
}

5. ConcurrentHashMap.KeySetView (альтернатива)

Для других типов данных (key-value) есть ConcurrentHashMap:

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
map.put("A", 1);
map.put("B", 2);

// Iterator не выбросит ConcurrentModificationException
for (String key : map.keySet()) {
    System.out.println(key);
    map.put("C", 3);  // Изменяем во время итерирования
}

// Map.values() тоже безопасен
for (Integer val : map.values()) {
    System.out.println(val);
}

6. Производительность: Сравнение

@State(Scope.Thread)
@BenchmarkMode(Mode.AverageTime)
public class ListBenchmark {
    
    @Benchmark
    public void cowList_Read(Blackhole bh) {
        CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
        for (int i = 0; i < 1000; i++) {
            list.add(i);
        }
        for (Integer val : list) {
            bh.consume(val);  // Быстро для чтения
        }
    }
    
    @Benchmark
    public void cowList_Write(Blackhole bh) {
        CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
        for (int i = 0; i < 1000; i++) {
            list.add(i);  // МЕДЛЕННО! O(n) за операцию
        }
        bh.consume(list.size());
    }
    
    @Benchmark
    public void syncList_Write() {
        List<Integer> list = Collections.synchronizedList(new ArrayList<>());
        for (int i = 0; i < 1000; i++) {
            list.add(i);  // Быстрее: O(1) за операцию
        }
    }
}

// Результаты примерно:
// cowList_Read:   ~0.5 ms    ✓ Отлично
// cowList_Write:  ~3.5 ms    ✗ Плохо
// syncList_Write: ~1.0 ms    ✓ Хорошо

7. Реальные примеры использования

Event Listeners (частый case)

public class EventBus {
    private final CopyOnWriteArrayList<EventListener> listeners 
        = new CopyOnWriteArrayList<>();
    
    public void subscribe(EventListener listener) {
        listeners.add(listener);  // Редко
    }
    
    public void unsubscribe(EventListener listener) {
        listeners.remove(listener);  // Редко
    }
    
    public void publish(Event event) {
        // Много читателей, может быть добавлен слушатель
        // во время публикации
        for (EventListener listener : listeners) {  // Часто
            listener.onEvent(event);
        }
    }
}

Кэш с редкими обновлениями

public class CachedDataList {
    private CopyOnWriteArrayList<CachedEntry> entries 
        = new CopyOnWriteArrayList<>();
    
    public List<CachedEntry> getAll() {
        return new ArrayList<>(entries);  // или просто итерируем
    }
    
    public void refresh() {
        // Переупаковываем весь список (редко)
        CopyOnWriteArrayList<CachedEntry> newEntries 
            = new CopyOnWriteArrayList<>();
        // ... загружаем данные ...
        entries = newEntries;
    }
}

8. Ограничения и недостатки

// 1. Iterator.remove() не поддерживается
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("A");
Iterator<String> it = list.iterator();
it.next();
it.remove();  // UnsupportedOperationException!

// 2. Высокое потребление памяти (копии при каждой записи)
CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
for (int i = 0; i < 100000; i++) {
    list.add(i);  // Каждый add = копия всего массива! Плохо!
}

// 3. Снимок может быть старым
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("A");
Iterator<String> it = list.iterator();

list.add("B");  // Добавили
list.add("C");

// Iterator всё ещё видит только [A]
while (it.hasNext()) {
    System.out.println(it.next());  // Только A
}

Выводы

CopyOnWriteArrayList — отличный выбор когда:

• ✓ Много читателей, мало писателей
• ✓ Размер списка небольшой
• ✓ Нужна безопасная итерация без явной синхронизации
• ✓ Слушатели событий

Используй альтернативы когда:

• Collections.synchronizedList() — нужен frequent write + rare iteration
• ConcurrentHashMap — для key-value с частыми обновлениями
• Synchronized блоки — полный контроль над синхронизацией
• Stream API с filter/map — обработка данных

Это мощный паттерн, широко используемый в production коде, особенно в реактивных и event-driven системах.