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

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

Умеете ли вы выбирать структуру под тип запроса: поиск по ключу, по значению или по порядку. Интервьюер ждёт три оценки с оговорками про конкретные реализации. Следом спрашивают, почему Collections.binarySearch на LinkedList не даёт логарифма или чем TreeMap отличается от HashMap.

Как отвечать

• HashMap.get: в среднем O(1). Худший случай с Java 8 ограничен O(log n) для ключей с Comparable, потому что переполненная корзина превращается в дерево. LinkedHashMap даёт те же оценки и хранит порядок вставки;
• TreeMap.get: O(log n) всегда, это красно-чёрное дерево. Зато есть floorKey, ceilingKey, subMap, то есть поиск по диапазону, которого у хэш-таблицы нет;
• Map.containsValue: O(n) для любой реализации, значения не индексируются;
• List.contains и indexOf: O(n), линейный проход с вызовом equals. Не путайте с ArrayList.get(i): это доступ по индексу за O(1), а у LinkedList тот же get(i) уже O(n);
• отсортированный массив: Arrays.binarySearch за O(log n) и O(1) памяти.

Про бинарный поиск в JDK две важные детали. Если элемента нет, возвращается -(insertionPoint + 1), поэтому проверка делается через < 0, а место вставки получается как -(i + 1). Collections.binarySearch логарифмичен только на списках с RandomAccess. На LinkedList он переходит на поиск итератором: сравнений по-прежнему O(log n), но переходов по ссылкам O(n).

Хорошо закончить выбором. Много поисков по ключу, порядок не важен: HashMap или HashSet. Нужен порядок или диапазоны: TreeMap. Данные почти не меняются, а важны память и предсказуемость: отсортированный массив с бинарным поиском. На десятке элементов линейный проход по массиву бывает быстрее хэширования, асимптотика там не главное.

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

Говорят «поиск в Map всегда O(1)». Без слов «в среднем» и без условия о хорошем hashCode ответ неполный.

Сравнивают результат binarySearch с -1. Отрицательным будет любой промах, а ровно -1 только при точке вставки 0.

Вызывают Arrays.binarySearch на несортированном массиве или сортируют перед каждым поиском. В первом случае результат не определён, во втором каждый поиск стоит O(n log n).