Выбор ответа Senior Массивы и хеш-таблицы обновлено
Худший случай хеш-таблицы
Вопрос
Почему операции хеш-таблицы называют O(1) «в среднем», а не всегда?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: При коллизиях ключи попадают в одну корзину, и поиск деградирует до O(n). Хеш-функция может отправить много ключей в одну корзину, и тогда поиск идёт по цепочке.
Варианты ответа
- При коллизиях ключи попадают в одну корзину, и поиск деградирует до O(n)правильный ответ
- Из-за сборки мусора, которая перемещает корзины таблицы
- Потому что ключи в корзинах всегда хранятся отсортированными
- Потому что хеш считается за O(n) от размера таблицы
Разбор
Хеш-функция может отправить много ключей в одну корзину, и тогда поиск идёт по цепочке. С хорошей хеш-функцией и перехешированием при росте это редкость, отсюда O(1) в среднем и амортизированно.
- GC влияет на паузы, но не на асимптотику операций.
- Хеш-таблица не сортирует ключи.
- Хеш зависит от размера ключа, а не таблицы.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.