Почему хеш-функции должны использовать модуль простого числа?

Обычно простая хеш-функция работает, беря "составные части" ввода (символы в случае строки), умножая их на степени некоторой константы и складывая их вместе в некотором целочисленном типе. Так, например, типичный (хотя и не очень хороший) хэш строки может быть таким:

(first char) + k * (second char) + k^2 * (third char) + ...

Тогда, если будет введена группа строк с одинаковым первым символом, тогда все результаты будут одинаковыми по модулю k, по крайней мере пока целочисленный тип не переполнится.

[Например, строковый hashCode Java устрашающе похож на этот - он выполняет обратный порядок символов с k = 31. Таким образом, вы получаете поразительные отношения по модулю 31 между строками, которые заканчиваются одинаково, и поразительные отношения по модулю 2 ^ 32 между строками, которые одинаковы, за исключением около конца. Это не сильно портит поведение хеш-таблицы.]

Хеш-таблица работает, принимая модуль хеш-функции по количеству сегментов.

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

Теперь предположим, что кто-то помещает в хеш-таблицу целую группу значений, которые имеют некоторые отношения между элементами, например, все они имеют один и тот же первый символ. Я бы сказал, что это довольно предсказуемая модель использования, поэтому мы не Я не хочу, чтобы это приводило к слишком большому количеству коллизий.

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

Очевидно, что реализации хеш-таблиц не имеют никакого контроля над помещаемыми в них элементами. Они не могут предотвратить их родство. Итак, что нужно сделать, это убедиться, что постоянный счетчик и счетчик ведра взаимно просты. Таким образом, вы не полагаетесь только на «последний» компонент для определения модуля ковша по отношению к некоторому небольшому общему коэффициенту. Насколько я знаю, они не должны быть простыми, чтобы достичь этого, просто взаимно просты.

Но если хеш-функция и хеш-таблица написаны независимо, то хеш-таблица не знает, как работает хеш-функция. Это может быть константа с небольшими коэффициентами. Если вам повезет, он может работать совершенно иначе и быть нелинейным. Если хеш достаточно хорош, то любое количество ведер вполне подойдет. Но параноидальная хеш-таблица не может предполагать хорошую хеш-функцию, поэтому следует использовать простое количество сегментов. Точно так же параноидальная хеш-функция должна использовать большую простую константу, чтобы уменьшить вероятность того, что кто-то использует несколько сегментов, которые имеют общий множитель с константой.

На практике я думаю, что довольно нормально использовать степень 2 как количество ведер. Это удобно и избавляет от необходимости искать или предварительно выбирать простое число нужной величины. Таким образом, вы полагаетесь на хеш-функцию, чтобы не использовать четные множители, что обычно является безопасным предположением. Но вы все равно можете иногда получать плохое хеш-поведение, основанное на хэш-функциях, подобных приведенной выше, и подсчет первичных сегментов может помочь в дальнейшем.

Говоря о принципе, "все должно быть простым" насколько я знаю, достаточное, но не необходимое условие для хорошего распределения по хэш-таблицам. Это позволяет каждому взаимодействовать, не предполагая, что другие следовали тому же правилу.

[Edit: есть еще одна, более специализированная причина использовать простое количество сегментов, то есть если вы обрабатываете столкновения с помощью линейного зондирования. Затем вы вычисляете шаг из хэш-кода, и если этот шаг оказывается фактором количества ведра, вы можете выполнить только (bucket_count / stride) зонды, прежде чем вернуться к тому месту, где вы начали. Разумеется, вам больше всего нужно избегать stride = 0, который должен иметь специальный регистр, но чтобы избежать также bucket_count / stride в специальном регистре, равного небольшому целому числу, вы можете просто сделать bucket_count простым и не заботиться о том, что шаг, если он не равен 0.]