Как определить значение при коллизии в цепочке хэш-таблицы

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

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

Как отвечать

Алгоритм поиска при цепочках:

• индекс корзины: hash(key) % len(buckets), а при размере, равном степени двойки, дешевле hash & (len-1);
• обход цепочки: идём по узлам корзины и сравниваем ключи через ==. Поэтому узел обязан хранить сам ключ, а не только значение, иначе два ключа с одним индексом неразличимы;
• ускорение: в узле держат и полный хэш. Сначала сравнивают хэши, это дёшево, и только при совпадении сравнивают ключи целиком, что важно для длинных строк;
• сложность: в среднем O(1) при разумном коэффициенте заполнения, в худшем O(n), когда все ключи попали в одну цепочку. Поэтому при превышении порога таблицу расширяют и перераскладывают элементы.

Про Go расскажите отдельно. До версии 1.24 map была цепочечной на уровне корзин: корзина на 8 пар, массив tophash со старшими 8 битами хэша для быстрого отсева и overflow-корзины при переполнении. Рост начинался при средней загрузке 6,5 элемента на корзину. С Go 1.24 используется Swiss Table: открытая адресация, группы по 8 слотов с контрольными байтами, где лежат 7 бит хэша, и поиск проверяет всю группу разом. Сид хэш-функции случаен для каждой карты, поэтому подобрать коллизии снаружи трудно, а порядок обхода к тому же намеренно рандомизирован.

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

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

Сравнивают только хэши. Совпадение хэшей не означает равенства ключей, и такая таблица рано или поздно вернёт чужое значение.

Описывают Go map как массив связных списков по одному элементу. Это неточно даже для старой реализации, а сейчас там вообще открытая адресация.

Обещают O(1) всегда. Без ограничения заполнения и без случайного сида злоумышленник может загнать все ключи в одну цепочку, это атака hash flooding.