Какая алгоритмическая сложность поиска элемента в Map, List и отсортированном массиве

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

Базовую асимптотику трёх структур и то, как она выглядит в Kotlin и Android SDK. С Android-разработчиком интервьюер часто идёт дальше: знаете ли вы про SparseArray и ArrayMap и почему на мобильном устройстве память иногда важнее O(1).

Как отвечать

• Map: HashMap ищет по ключу в среднем за O(1), в худшем случае с Java 8 корзина превращается в дерево и поиск для Comparable-ключей ограничен O(log n). В Kotlin mutableMapOf() и mapOf() с несколькими парами создают LinkedHashMap: те же O(1) плюс порядок вставки;
• List: contains, indexOf, find, firstOrNull { } проходят по списку за O(n). Доступ по индексу у ArrayList O(1), эти две операции не путают;
• отсортированный список или массив: бинарный поиск за O(log n). В Kotlin это list.binarySearch(x) и binarySearchBy(key) { it.id }; при промахе возвращается -(insertionPoint + 1), поэтому проверяют < 0.

Дальше Android-специфика:

• SparseArray: как и SparseIntArray, LongSparseArray, хранит ключ int или long без автоупаковки в двух параллельных массивах, ключи отсортированы. Поиск O(log n), вставка в середину O(n);
• ArrayMap: отсортированный массив хэшей плюс массив ключей и значений. Поиск тоже бинарный, O(log n), зато нет отдельного объекта на каждую запись.

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

Итоговое правило: частый поиск по ключу и много данных: HashMap. Небольшая карта с Int-ключами в адаптере или View: SparseArray.

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

Вызывают list.sorted().binarySearch(x) при каждом поиске. Сортировка O(n log n) съедает весь выигрыш, это хуже простого contains.

Делают ключом data class с var-полями и меняют поле после вставки. hashCode меняется, и запись в HashMap больше не находится.

Считают SparseArray универсально быстрее HashMap. На больших объёмах с частыми вставками он медленнее из-за сдвига массивов, его выигрыш в памяти на небольших наборах.