Во-первых, я не знаю, уместно ли задавать подобные вопросы или нет, пожалуйста, прости меня, если это не так.
Я читаю ответ на вопрос «Почему хеш-функции должны использовать модуль простых чисел?» , в этом ответе говорится:
Оказывается, что "из-за характера математики", если постоянная, используемая в хэше, и число сегментов взаимно просты, то столкновения минимизируются в некоторых распространенных случаях. Если они не взаимно просты, то между входами есть довольно простые отношения, для которых коллизии не минимизируются. Все хэши выходят равными по модулю общего множителя, что означает, что все они попадут в 1 / n-ю ячейку, у которой есть это значение по модулю общего множителя. Вы получаете в n раз больше столкновений, где n является общим фактором. Поскольку n равно как минимум 2, я бы сказал, что для довольно простого варианта использования неприемлемо генерировать как минимум вдвое больше коллизий, чем обычно. Если какой-то пользователь собирается разбить наш дистрибутив на сегменты, мы хотим, чтобы он был странная авария, а не простое предсказуемое использование.
Я прочитал комментарий под ответом , но я все еще не совсем понимаю следующие предложения:
- Все хэши получаются равными по модулю общего множителя, что означает, что все они попадут в 1 / n-ю ячейку, в которой это значение равно модулю общего множителя.
- Вы получаете в n раз больше столкновений, где n является общим фактором.
Может кто-нибудь объяснить это подробно и привести пример? И как «общий фактор» увеличивает коллизии? Заранее спасибо.