Как работает хэш-таблица

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

Понимаете ли вы устройство и знаете ли способы разрешения коллизий.

Как отвечать

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

Коллизия это совпадение индексов у разных ключей. При конечном массиве она неизбежна, разрешают её двумя способами:

• цепочки: в корзине список пар. Просто и устойчиво, но при плохом хеше вырождается в линейный поиск. В Java длинная цепочка превращается в дерево;
• открытая адресация: ищем следующую свободную ячейку по правилу проб. Экономит память и лучше ложится на кэш процессора, но страдает от кластеризации, а удаление требует пометок, иначе цепочка проб обрывается. Так устроены словари Python.

Коэффициент заполнения определяет частоту коллизий: при превышении порога (обычно 0.7 или 0.75) массив увеличивается и элементы раскладываются заново. Отсюда амортизированная оценка: отдельная вставка иногда стоит линейно, в среднем постоянно.

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

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

Считают коллизии ошибкой.

Знают только цепочки.

Утверждают, что вставка всегда за постоянное время, забывая про перестроение.

Не могут объяснить, зачем нужны требования к ключу.