Обычно простая хеш-функция работает, беря «составляющие части» ввода (символы в случае строки), умножая их на степени некоторой константы и складывая их вместе в некоторый целочисленный тип. Так, например, типичный (хотя и не особенно хороший) хеш строки может быть:
(first char) + k * (second char) + k^2 * (third char) + ...
Тогда, если будет введен набор строк, имеющих все одинаковые первые символы, то все результаты будут одинаковыми по модулю k, по крайней мере, до тех пор, пока целочисленный тип не переполнится.
[Например, строковый хэш-код Java очень похож на этот - он выполняет обратный порядок символов с k = 31. Таким образом, вы получаете поразительные отношения по модулю 31 между строками, которые заканчиваются одинаково, и поразительные отношения по модулю 2 ^ 32 между строками, которые одинаковы, за исключением конца. Это серьезно не портит хеш-таблицу поведения.]
Хеш-таблица работает, принимая модуль хеш-функции над количеством сегментов.
В хеш-таблице важно не создавать коллизии для вероятных случаев, поскольку коллизии снижают эффективность хеш-таблицы.
Теперь предположим, что кто-то помещает целую кучу значений в хеш-таблицу, которые имеют некоторую связь между элементами, как у всех, имеющих один и тот же первый символ. Я бы сказал, что это довольно предсказуемый шаблон использования, поэтому мы не хотим, чтобы он вызывал слишком много коллизий.
Оказывается, что "из-за природы математики", если константа, используемая в хэше, и число сегментов равны взаимно просты , то столкновения минимизируются в некоторых распространенных случаях. Если они не являются взаимно простыми , то существуют некоторые довольно простые отношения между входами, для которых коллизии не минимизируются. Все хэши получаются равными по модулю общего множителя, что означает, что все они попадут в 1 / n-ую ячейку, которая имеет это значение по модулю общего множителя. Вы получаете в n раз больше столкновений, где n является общим фактором. Поскольку n равно по крайней мере 2, я бы сказал, что для довольно простого варианта использования неприемлемо генерировать как минимум вдвое больше коллизий, чем обычно. Если какой-то пользователь собирается разбить наш дистрибутив на сегменты, мы хотим, чтобы это был странный случай, а не простое предсказуемое использование.
Теперь реализации с хеш-таблицами, очевидно, не контролируют элементы, помещенные в них. Они не могут помешать им быть связанными. Поэтому нужно убедиться, что константа и число сегментов взаимно просты. Таким образом, вы не полагаетесь только на «последний» компонент для определения модуля ковша относительно некоторого небольшого общего фактора. Насколько я знаю, они не должны быть первыми, чтобы достичь этого, просто взаимно.
Но если хеш-функция и хеш-таблица пишутся независимо, то хеш-таблица не знает, как работает хеш-функция. Это может быть использование постоянной с небольшими факторами. Если вам повезет, он может работать совершенно иначе и быть нелинейным. Если хеш достаточно хорош, то любое количество сегментов в порядке. Но параноидальная хеш-таблица не может принять хорошую хэш-функцию, поэтому следует использовать простое число сегментов. Аналогично, параноидальная хеш-функция должна использовать большую простую константу, чтобы уменьшить вероятность того, что кто-то использует несколько сегментов, у которых, как правило, есть общий множитель с константой.
На практике, я думаю, вполне нормально использовать степень 2 в качестве количества сегментов. Это удобно и избавляет от необходимости искать или предварительно выбирать простое число правильной величины. Таким образом, вы полагаетесь на хеш-функцию, чтобы не использовать даже множители, что обычно является безопасным допущением. Но вы все равно можете время от времени получать плохое поведение при хешировании, основанное на хеш-функциях, таких как приведенная выше, и простое число сегментов может помочь в дальнейшем.
Если говорить о принципе, что «все должно быть простым», насколько я знаю, достаточное, но не необходимое условие для хорошего распределения по хеш-таблицам. Это позволяет всем взаимодействовать друг с другом без необходимости предполагать, что другие следовали тому же правилу.
[Редактировать: есть еще одна, более специализированная причина использовать простое число сегментов, то есть если вы обрабатываете столкновения с линейным зондированием. Затем вы вычисляете шаг по хеш-коду, и если этот шаг становится фактором подсчета сегментов, вы можете только выполнить (bucket_count / stride) зонды, прежде чем вернетесь к тому, с чего начали. Конечно, вам больше всего нужно избегать: stride = 0, что, конечно, должно быть в специальном регистре, но чтобы избежать также специального случая, когда bucket_count / stride равен маленькому целому числу, вы можете просто сделать простое число bucket_count и не заботиться о том, что при условии, что это не 0.]