Какова асимптотическая сложность доступа по ключу в хэш-таблице
Что проверяют
Знаете ли вы среднюю и худшую оценку и понимаете ли, при каких условиях выполняется средняя.
Как отвечать
В среднем O(1), в худшем O(n).
Механика: ключ пропускается через хеш-функцию, результат указывает на ячейку, и при отсутствии коллизий обращение занимает постоянное время.
Условия, при которых средняя оценка выполняется, назвать обязательно:
- хорошее распределение хеша. Если функция плохая и половина ключей попадает в одну ячейку, поиск вырождается в перебор цепочки;
- приемлемый коэффициент заполнения. При росте таблица перехешируется: выделяется массив большего размера и все элементы перекладываются. Это стоит O(n), но случается редко, поэтому амортизируется.
Худший случай реален не только теоретически: подобрав ключи с одинаковым хешем, можно намеренно превратить операции в линейные и положить сервис. Защита есть в обоих направлениях: в Python и Go при запуске выбирается случайное начальное значение хеша, поэтому подобрать коллизии заранее нельзя, а в Java с восьмой версии длинная цепочка в корзине превращается в дерево, и худший случай улучшается до O(log n).
Важная оговорка, которую редко произносят: постоянное время скрывает стоимость вычисления самого хеша. Для короткого ключа это действительно константа, а для строки в мегабайт хеш считается по всей длине. Строго говоря, оценка постоянная относительно числа элементов, но не относительно размера ключа.
И про практику: постоянное время в асимптотике не означает, что хеш-таблица всегда быстрее. На десятке элементов линейный поиск по массиву обычно выигрывает, потому что данные лежат подряд и попадают в кэш процессора, а хеш ещё надо посчитать.
Где спотыкаются
Называют только среднюю оценку, не упоминая условий.
Не знают про перехеширование и его стоимость.
Забывают, что качество хеш-функции определяет фактическую сложность.
Считают хеш-таблицу быстрее массива при любом размере.