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