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

ArrayList.removeAll проверяет каждый элемент исходного списка через contains переданной коллекции. Поэтому сложность определяется не только размером ArrayList, но и стоимостью поиска в аргументе: обычно около O(n · m) для другого списка, около O(n) в среднем для HashSet и около O(n · log m) для TreeSet, где n — размер исходного списка, а m — размер переданной коллекции.

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

Java Collections Framework предоставляет единый контракт массовых операций, включая removeAll, для разных видов коллекций. Это позволяет работать с коллекциями через интерфейсы, не привязываясь к конкретной реализации.

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

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

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

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

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

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

Ключевой фактор — сложность contains:

у ArrayList — O(m), поэтому суммарно обычно O(n · m);
у HashSet — в среднем O(1), поэтому суммарно обычно O(n);
у TreeSet — O(log m), поэтому суммарно O(n · log m).

Это оценка основной части алгоритма. Для ArrayList также учитывается линейное уплотнение внутреннего массива, но оно не меняет приведённые оценки в типичном анализе.

Минимальный пример выбора структуры:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

List<String> users = new ArrayList<>(loadUsers());
Set<String> blocked = new HashSet<>(loadBlockedUsers());
users.removeAll(blocked);

Здесь построение HashSet занимает в среднем O(m) и требует дополнительной памяти O(m). После этого удаление обычно выполняется за O(n). Для корректной работы множества элементы должны соблюдать контракт equals и hashCode.

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

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

В сервисе нужно удалить из списка активных идентификаторов все идентификаторы, попавшие в чёрный список. Активный список содержит пять миллионов записей, чёрный список — несколько сотен тысяч.

Первый вариант — передать чёрный список как ArrayList. Он прост, не требует дополнительного преобразования, но потенциально выполняет сотни тысяч сравнений для каждого активного идентификатора.

Второй вариант — предварительно создать HashSet. Он требует дополнительной памяти и времени на построение множества, зато последующие проверки выполняются в среднем за постоянное время. Третий вариант — TreeSet: он сохраняет упорядоченность и поддерживает операции по диапазонам, но для простой проверки принадлежности обычно медленнее HashSet.

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

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

1. Всегда ли преобразование аргумента в HashSet ускоряет removeAll?

Нет. Построение множества само требует времени и памяти. Для маленьких коллекций стоимость преобразования может превысить выигрыш, а при нестандартных или плохо реализованных hashCode преимущество может уменьшиться. Кроме того, HashSet использует равенство и хеш-коды, поэтому изменение этих контрактов меняет смысл проверки принадлежности.

2. Удаляет ли removeAll только одно совпадение каждого значения?

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

3. Гарантирует ли контракт Collection конкретную асимптотику removeAll?

Нет. Контракт определяет логический результат операции, но обычно не фиксирует её точную сложность. Поэтому выбор реализации остаётся частью инженерного решения: для массовой проверки принадлежности обычно выбирают HashSet, для упорядоченных диапазонов — TreeSet, а для сохранения последовательности и небольших объёмов может быть достаточен ArrayList.