Как использовать структуру данных с быстрым доступом вместо includes для оптимизации

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

Видите ли вы скрытую квадратичную сложность: includes внутри filter или map превращает проход по двум массивам в O(n·m). Следом обычно спрашивают, чем Set отличается от обычного объекта и когда выигрыша не будет.

Как отвечать

Array.prototype.includes это линейный поиск: чтобы ответить «нет», он проходит весь массив. Один вызов не страшен, страшен вызов в цикле: отфильтровать 10 000 товаров по списку из 5 000 выбранных id означает до 50 миллионов сравнений.

Решение: один раз построить структуру с поиском за O(1) в среднем и дальше спрашивать её.

• Set: для вопроса «есть ли значение». const selected = new Set(ids), затем items.filter(i => selected.has(i.id)). Сравнивает по SameValueZero, как и includes, так что NaN находится;
• Map: когда по ключу нужно достать объект, а не просто проверить наличие. Индекс new Map(users.map(u => [u.id, u])) заменяет find в цикле;
• обычный объект: работает, но ключи приводятся к строке, мешают унаследованные свойства вроде toString (спасает Object.create(null) или Object.hasOwn), а частые добавления и удаления ключей движок оптимизирует хуже, чем у Map.

В React такую структуру держат в useMemo от исходного массива, иначе Set пересоздаётся на каждый рендер. Хранить Set выбранных id в состоянии удобно, но обновлять его нужно новым экземпляром: new Set(prev).add(id), иначе React не заметит изменения.

Плюсом будет упомянуть методы union, intersection и difference у Set из ES2025: они уже есть в актуальных браузерах и заменяют ручные пересечения через filter и includes.

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

Строят Set внутри цикла или прямо в теле компонента на каждый рендер. Построение стоит O(n), и выигрыш исчезает.

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

Кладут в Set объекты и ждут поиска по содержимому. Сравнение идёт по ссылке, set.has({ id: 1 }) всегда вернёт false, поэтому в набор кладут примитивные ключи.