Как устроена хэш-таблица и какие проблемы возникают при коллизиях
Что проверяют
Знаете ли вы способы разрешения коллизий и понимаете ли, откуда берётся деградация.
Как отвечать
Устройство: есть массив корзин. Ключ пропускается через хеш-функцию, результат приводится к индексу корзины, туда и кладётся пара ключ-значение. При хорошем распределении доступ занимает постоянное время.
Коллизия это ситуация, когда два разных ключа дают один индекс. Она неизбежна: ключей бесконечно много, а корзин конечное число.
Два семейства решений:
Цепочки. В корзине хранится список элементов. При коллизии элемент добавляется в него, а поиск перебирает список. Просто и устойчиво к высокой заполненности. Проблема: длинная цепочка превращает поиск в линейный. Отсюда улучшение в некоторых реализациях, где длинная цепочка перестраивается в дерево, ограничивая худший случай логарифмом.
Открытая адресация. Все элементы лежат прямо в массиве, а при занятой ячейке ищется следующая свободная по определённому правилу: линейно, квадратично или по второму хешу. Экономнее по памяти и лучше работает с кэшем процессора, потому что данные лежат подряд. Проблема линейного варианта это кластеризация: занятые ячейки слипаются в длинные группы, и поиск замедляется. Плюс удаление усложняется: нельзя просто освободить ячейку, иначе оборвётся цепочка поиска, поэтому ставится специальная пометка.
Общие проблемы при коллизиях:
- деградация до линейного времени при плохой хеш-функции. Именно поэтому качество вычисления хеша важнее выбора структуры;
- перехеширование при превышении коэффициента заполнения: массив увеличивается, и все элементы перекладываются заново. Стоит линейно, но амортизируется;
- атака подбором коллизий: злоумышленник подбирает ключи с одинаковым хешем и превращает обработку в квадратичную. Защита это случайное начальное значение хеша, применяемое в современных средах.
Про словарь в .NET полезно добавить, что он использует схему с цепочками, реализованными на массивах индексов, а не на связных узлах.
Где спотыкаются
Не знают про открытую адресацию.
Не могут объяснить, почему удаление сложнее при открытой адресации.
Переопределяют равенство без вычисления хеша.
Считают постоянное время безусловной гарантией.