Как Java-итераторы ловят изменения: разбор modCount

Зачем это читать

Если вы решали задачу Design HashMap на LeetCode, вы реализовывали put, get и remove. Но самое интересное — что происходит, когда кто-то изменяет карту во время итерации по ней. Разбираем механизм fail-fast итераторов на примере Java: как работает modCount, почему простые решения не работают, и как это применить в реальном коде.

Проблема: неопределённое поведение при изменении во время итерации

Представьте: вы итерируетесь по карте, и в этот момент вызывается put() с новым ключом. Без защиты это приводит к пропуску записей, устаревшим данным или исключениям. Java решает это через ConcurrentModificationException (CME), но важна не сама ошибка, а механизм её обнаружения.

Первая идея: булевый флаг

Простое поле boolean modified на карте, которое устанавливается при изменении. Но это работает только для одного итератора. С двумя итераторами всё ломается: если карта изменилась после создания второго итератора, второй увидит флаг и ошибочно выбросит исключение, хотя для него ничего не менялось.

Вторая идея: временная метка

Использовать lastModified timestamp и сравнивать с временем создания итератора. Проблема — разрешение: две операции могут попасть в одну миллисекунду, и сравнение будет неверным. К тому же currentTimeMillis() не монотонно.

Правильное решение: монотонный счётчик (modCount)

Каждая мутация увеличивает long счётчик. Каждый итератор при создании сохраняет его значение. При каждом next() сравнивает своё сохранённое значение с текущим:

class MyEntryIterator implements Iterator> {
    private long expectedVersion;

    public MyEntryIterator() {
        this.expectedVersion = version; // снимок при создании
    }

    @Override
    public Entry next() {
        if (expectedVersion != version) {
            throw new ConcurrentModificationException();
        }
        // ... продвижение и возврат
    }
}

Никаких общих флагов, никаких часов. Каждый итератор имеет собственный снимок, поэтому случай с двумя итераторами работает корректно. Инкремент гарантирует уникальность значений — нет риска коллизий.

Тонкость: нет «бесплатного» первого вызова

Два итератора созданы подряд, ещё ни один не вызвал next(). Если первый вызовет remove(), то второй при первом же next() получит CME. Итератор B устарел сразу после изменения, даже если он ещё не начал обход. Проверка работает с момента снимка, а не с первого вызова.

Ловушка самоневалидации

Собственный remove() итератора увеличивает общий счётчик. Если не обновить своё expectedVersion сразу, итератор сам себя поймает на следующем вызове:

public void remove() {
    if (!nextCalled) {
        throw new IllegalStateException();
    }
    MyEntry entryToDelete = currentEntry;
    this.next();
    MyHashMap.this.remove(entryToDelete.getKey());
    this.expectedVersion = version; // синхронизация, иначе CME
    this.nextCalled = false;
}

Нюанс: не каждое изменение структурное

Счётчик должен увеличиваться только при структурных изменениях (добавление нового ключа, удаление). Перезапись значения существующего ключа не меняет структуру и не должна инвалидировать итераторы:

if (entry == null) {
    // новый ключ: структурное изменение
    entries[bucket] = new MyEntry(key, value);
    ++count;
    ++version;
} else {
    // существующий ключ: только значение, не структурное
    entry.setValue(value);
}

Это соответствует поведению java.util.HashMap и видно только при реальной реализации.

Практический вывод

Fail-fast итерация — не просто трюк с modCount. Чтобы защититься от второго итератора, гонки в одну миллисекунду и собственных мутаций, нужно реализовать монотонный счётчик. Напишите тесты для многоитераторного случая — они выявят ошибки в реализации и в самих тестах.

Прямо сейчас: если вы используете итераторы в своём коде, проверьте, обрабатываете ли вы ConcurrentModificationException. Попробуйте реализовать собственную коллекцию с fail-fast итератором на Python или Java — это отличная тренировка.