Как оптимизировать использование листа и поиска через contains в цикле

Что проверяют

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

Как отвечать

Покажите проблему: цикл по orders с allowedIds.contains(order.getId()), где allowedIds это List. При десяти тысячах элементов в каждой коллекции это до ста миллионов сравнений.

Решение и его нюансы:

• построить множество один раз: Set<Long> allowed = new HashSet<>(allowedIds) до цикла, дальше contains в среднем O(1). Итог O(n + m) вместо O(n·m). Создавать множество внутри цикла бессмысленно, это та же линейная работа на каждой итерации;
• equals и hashCode: HashSet опирается на оба метода. Для своих классов они должны быть согласованы, а поля, от которых зависит хеш, не должны меняться, пока объект лежит в множестве. Здесь хорошо подходят record;
• порядок и дубликаты: множество не хранит повторы. Нужен порядок вставки, берите LinkedHashSet, нужны количества, берите Map со счётчиком;
• альтернативы: если данные отсортированы, Collections.binarySearch даёт O(log n) без лишней памяти, для небольшого диапазона целых подходит BitSet;
• скрытые contains: list.removeAll(other) и retainAll вызывают other.contains для каждого элемента, поэтому аргументом тоже лучше передавать HashSet.

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

Где спотыкаются

Замеряют через System.currentTimeMillis() в main. Без прогрева JIT такие цифры ничего не значат, для микробенчмарков есть JMH.

Кладут в HashSet объекты без переопределённых equals и hashCode. Тогда сравнение идёт по ссылке, и contains не находит логически равный объект.

Меняют поле, от которого зависит hashCode, после добавления объекта в множество. Элемент оказывается не в своей корзине, и contains начинает врать.