Почему поиск в List медленнее, чем в Set

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

Знаете ли вы стоимость операций у коллекций, которыми пользуетесь каждый день, и откуда вообще берётся константный поиск. На Android к этому добавляется вопрос про память: лишние объекты на короткоживущих наборах заметны.

Как отвечать

ArrayList.contains идёт по элементам подряд и сравнивает через equals, это O(n). HashSet считает hashCode, попадает в нужную корзину и сравнивает только с тем, что в ней лежит, это O(1) в среднем.

Дальше уточнения, которые и отличают ответ от заученного:

• быстрым поиск делает хеш-таблица, а не само множество. TreeSet ищет за O(log n) сравнениями, LinkedHashSet это тот же хеш плюс порядок обхода;
• всё держится на согласованных hashCode и equals. Объект без них ляжет в множество, но contains по равному по смыслу экземпляру вернёт false. В Kotlin их даёт data class, обычному классу нужно писать самому;
• при массовых коллизиях корзина перестраивается в дерево, и худший случай упирается в O(log n);
• на десятке элементов линейный проход по массиву нередко быстрее: хеш надо посчитать, а узлы множества это лишние объекты и промахи кэша.

Для Android назовите ArraySet и ArrayMap из androidx для небольших наборов и SparseArray для целочисленных ключей, он избавляет от упаковки.

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

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

Знают теорию, но пишут contains по списку внутри цикла по другому списку и получают квадратичное время на ровном месте. Одно преобразование в множество до цикла снимает проблему.

Меняют поле объекта после того, как положили его в множество. Хеш стал другим, элемент остался в старой корзине, и contains отвечает false, хотя объект внутри. Ключи должны быть неизменяемыми.