Зачем нужна хэш-функция, если ключи — это числа
Что проверяют
Понимаете ли вы, что хэш-функция нужна не для того, чтобы превратить ключ в число, а для равномерного распределения ключей по таблице. Следом спрашивают, как это устроено в рантайме Go и когда хэш-таблица вообще не нужна.
Как отвечать
Число ещё не индекс. У таблицы ограниченное число ячеек, и ключ нужно отобразить в одну из них. В Go их количество это степень двойки, а позиция берётся из битов хэша маской. Если бы хэшем был сам ключ, позицию определяла бы только часть его битов:
- закономерности в ключах: ID с шагом 1024, только чётные числа, временные метки, кратные секунде. Без перемешивания такие ключи попадают в малую долю ячеек, и поиск деградирует от O(1) к линейному;
- перемешивание битов: хорошая хэш-функция делает так, что каждый бит ключа влияет на результат, и соседние или круглые числа разлетаются по всей таблице;
- защита от атак: у каждой мапы в Go своё случайное зерно хэша, поэтому нельзя заранее подобрать тысячи ключей с одинаковым хэшем и превратить мапу в список (hash flooding). Если хэш равен ключу, такая атака тривиальна;
- рантайм Go: на процессорах с AES-инструкциями хэш считается на них, для ключей
int32,int64иstringесть отдельные быстрые пути доступа. С Go 1.24 мапы построены на Swiss tables: часть битов хэша выбирает группу слотов, а 7 бит хранятся в управляющем байте и позволяют отсеять лишние слоты без сравнения ключей.
Сильный финал: если ключи плотные и в известном диапазоне, скажем от 0 до 10 000, хэш-таблица не нужна, хватит среза с прямой адресацией. Хэш нужен именно потому, что ключи в общем случае произвольные.
Где спотыкаются
Говорят, что хэш-функция разрешает коллизии. Их разрешает сама таблица: цепочки, открытая адресация, поиск по группам в Swiss tables. Функция только делает их редкими.
Путают хэш для таблиц с криптографическим и вспоминают хранение паролей. Мапе нужна скорость и равномерность, а не стойкость, и SHA-256 здесь был бы просто медленным.
Предлагают key % n как универсальный ответ. С простым n это работает сносно, но при n, равном степени двойки, остаток просто отбрасывает старшие биты, и закономерности в ключах бьют напрямую.