ArrayList, Vector, CopyOnWriteArrayList в многопоточной среде

Я думаю всем известно, что ArrayList совершенно непригоден для многопоточного использования. У меня пробегают мурашки, когда представляю, что, например, метод add будут использовать 2 потока одновременно:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

«Ага!, – скажет кто-то. – Тут нужно использовать java.util.Vector», потому, что:

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

Красота – и add, и remove и прочие модифицирующие методы защищены блокировкой (кстати, такая блокировка называется intrinsic (внутренняя) lock или monitor lock). Обратите внимание на переменную modCount! Мы еще о ней поговорим.

Тут можно прервать чтение и вспомнить как работают итераторы. Что будет, если во время итераций произойдет добавление или удаление элемента?

Давайте глянем на итератор вектора:

public synchronized Iterator<E> iterator() {
    return new Itr();
}

Нам возвращают новый итератор. Познакомимся с ним поближе. Приведу не весь класс, а только важные для нас части:

private class Itr implements Iterator<E> {
    ...
    int expectedModCount = modCount;

    public E next() {
        synchronized (Vector.this) {
            checkForComodification();
            int i = cursor;
            if (i >= elementCount)
                throw new NoSuchElementException();
            cursor = i + 1;
            return elementData(lastRet = i);
        }
    }

    ...

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

Очень интересная строка – инициализация переменной expectedModCount. Как мы уже видели выше, добавление элемента (а также и удаление) влечет увеличение переменной modCount. Итератор запоминает это значение во время создания, и откажется итерироваться, если заметит (вызовом checkForComodification), что состав контейнера изменился. Другими словами,  для нормальной работы, требуется совпадение версий вектора и итератора. В достоверности этого можно убедиться и с одним потоком:

Vector<Integer> v = new Vector<Integer>();
v.add(1);
Iterator<Integer> it = v.iterator();
v.add(2);
while(it.hasNext())
    System.out.println(it.next());  //ConcurrentModificationException

Давайте посмотрим как с этим справляется класс CopyOnWriteArrayList

public boolean add(E e) {

    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

Для меня это было неожиданно – при добавлении (и удалении) создается, а затем используется копия массива. И новый элемент добавляется в эту копию. Как это влияет на работу итератора? Все итераторы продолжают работать со своими старыми массивами,  которые были актуальны на момент создания итераторов. Поэтому все изменения контейнера другими потоками не повлияют на их работу.

Резюме
Контейнеры в многопоточной среде:
ArrayList – непригоден
Vector – пригоден, но скорее всего, не удасться нормально использовать итераторы
CopyOnWriteArrayList – пригоден. Однако, из-за создания копий, разумно использовать когда количество итераций во много раз превосходит число модификаций.

Домашнее задание
1. Выяснить результат работы:

Vector<Integer> v = new Vector<Integer>();
Iterator<Integer> it = v.iterator();
v.add(1);
System.out.println(it.hasNext());

2. Убедиться (проверив исходный код класса CopyOnWriteArrayList), что итератор работает именно с тем массивом, который был на момент создания итератора.