Как устроен hash индекс и как решаются коллизии

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

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

Как отвечать

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

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

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

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

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

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

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

Не знают про открытую адресацию.

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

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