Что такое хэш-таблица, как она устроена и какие проблемы возникают при коллизиях

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

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

Как отвечать

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

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

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

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

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

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

Считают коллизии ошибкой, а не нормой.

Не знают ни одного способа разрешения, кроме цепочек.

Забывают про перехеширование и уверяют, что вставка всегда O(1).

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