Что будет при использовании функции хэширования как остатка от деления на десять?
Что проверяют
Понимаете ли вы требования к хэш-функции: равномерность и участие всех битов ключа. Вопрос почти всегда ведёт к разговору о том, как устроена хэш-таблица внутри и почему поиск в ней считают константным.
Как отвечать
Программа не сломается, она будет работать медленно и неравномерно. Остаток от деления на десять даёт ровно десять корзин, то есть при росте числа ключей средняя длина цепочки растёт линейно, и обещанная константа превращается в перебор. Вторая беда хуже первой: остаток от десяти это последняя десятичная цифра ключа, а реальные данные по ней почти никогда не распределены ровно. Идентификаторы с шагом десять лягут в одну корзину, цены соберутся на девятке, круглые суммы на нуле.
От приличной хэш-функции ждут другого: она перемешивает все биты входа, а число корзин растёт вместе с данными и берётся либо степенью двойки, либо простым числом. Степень двойки удобна тем, что вместо деления работает битовая маска.
В Go это обычно теоретическая часть: встроенная map считает хэш сама, добавляет к нему случайное зерно при старте процесса для защиты от подобранных коллизий и сама растёт при переполнении корзин. Своё писать стоит только для специальных структур, и тогда берут готовое:
seed := maphash.MakeSeed()
idx := maphash.String(seed, key) & uint64(len(buckets)-1)Где спотыкаются
Называют коллизии ошибкой реализации. Коллизии неизбежны по принципу Дирихле, раз множество ключей больше множества хэшей. Вопрос только в их количестве и в том, как таблица их разрешает: цепочками или открытой адресацией.
Второе: предлагают заменить остаток на SHA-256 или MD5. Криптостойкость в хэш-таблице не нужна, а стоимость такой функции на порядок выше; для таблиц берут быстрые не криптографические функции.
Третье: думают только о функции и забывают про размер таблицы. Даже идеальный хэш при фиксированном числе корзин деградирует по мере роста данных, поэтому рехэширование при заполнении важно ровно так же, как сама функция.