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

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

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

Как отвечать

Три цифры с объяснением к каждой:

• Map (хэш-таблица): O(1) в среднем и амортизированно. Ключ хэшируется, по хэшу вычисляется бакет. Худший случай, когда все ключи легли в один бакет, это O(n) при списке в бакете и O(log n), если реализация переводит бакет в сбалансированное дерево (так делает HashMap в Java с 8-й версии);
• List (массив): линейный поиск O(n), доступ по индексу O(1). У связного списка O(n) и на поиск, и на доступ по индексу;
• Отсортированный массив: бинарный поиск O(log n), но порядок надо поддерживать: вставка стоит O(n) из-за сдвига, первичная сортировка O(n log n).

Добавьте то, чего нет в учебнике. Константа у хэш-таблицы не бесплатная: O(1) считается от числа элементов, а не от длины ключа, и хэширование длинной строки стоит заметно. На десятках элементов линейный проход по непрерывному массиву обгоняет словарь: нет вычисления хэша, всё лежит в кэше процессора. Отсортированный массив выигрывает, когда нужны ещё и диапазонные запросы или обход по порядку.

Swift-специфика: Dictionary и Set дают O(1) в среднем, хэш затравливается случайным значением на каждый запуск, поэтому подобрать коллизии снаружи невозможно. Array.contains это O(n). Бинарного поиска в стандартной библиотеке нет, его пишут руками или берут partitioningIndex из пакета swift-algorithms.

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

Называют O(1) гарантией, а не средним значением, и не могут описать вырожденный случай.

Забывают про цену поддержания порядка: предлагают отсортированный массив ради O(log n), но не считают вставку, из-за которой поток записей превращает выигрыш в проигрыш.

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