Что дает использование массива флагов вместо Set?

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

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

Как отвечать

Массив флагов выигрывает, когда ключ это целое из известного и небольшого диапазона. Тогда обращение сводится к адресной арифметике: ни вычисления хеша, ни сравнения объектов, ни узлов таблицы, ни упаковки чисел в объекты.

Разница в памяти на порядок: boolean[] занимает байт на элемент, а множество целых держит на каждый элемент объект-обёртку, узел таблицы и ссылку в массиве корзин, это десятки байт. Добавьте локальность: массив читается подряд и хорошо ложится в кеш процессора, множество идёт по ссылкам.

Если диапазон широкий, но нужна плотность, берут BitSet, где значение занимает бит, или маску в long для набора до 64 признаков. Для перечислений тот же приём уже упакован в EnumSet.

Что теряете: размер зависит от диапазона, а не от числа элементов; отрицательные и разреженные ключи требуют смещения; чтобы перечислить содержимое, надо просканировать весь массив; нет объединения, пересечения и типобезопасности. Уместные случаи: отметки посещённых вершин при обходе, присутствие символов, решето, подсчёт повторов.

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

Обосновывают выбор тем, что у множества сложность хуже. У хеш-множества поиск в среднем константный и на приличной хеш-функции таким и остаётся. Выигрыш массива не в асимптотике, а в константе и в памяти.

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

Оптимизируют вслепую. Массив, смысл индекса которого нигде не записан, читается хуже соседнего кода; а если структуру приходится очищать перед каждым прогоном, заполнение нулями стоит пропорционально диапазону и съедает весь выигрыш на коротких наборах.