Почему установка длины HashTable в простое число является хорошей практикой?

Question

Я просматривал последнее сообщение Эрика Липперта в блоге для Руководства и правила для GetHashCode , когда я набрал этот пункт:

Мы могли бы быть еще более умными;Подобно тому, как List изменяет свой размер при заполнении, набор сегментов также может изменять свой размер, чтобы средняя длина сегмента оставалась низкой.Кроме того, по техническим причинам часто хорошей идеей является * * * * * * * * * * * * * * * * * * * * - * - - - - - - = 1007 *, а не 100, - это хорошая идея сделать длину набора сегментов простым числом. Мы можем внести множество улучшений в эту хэш-таблицу.Но этот быстрый набросок наивной реализации хеш-таблицы пока подойдет.Я хочу, чтобы все было просто.

Похоже, я что-то упустил.Почему рекомендуется устанавливать его в простое число?

Answer 1

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

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

В качестве примера из реальной жизни Java HashTable изначально были реализованы с использованием простых (или почти простых размеров), но начиная с Java 1.4, дизайн был изменен, чтобы использовать мощность двух чисел, и добавила вторую функцию быстрого хеширования, примененную крезультат начального хэша.Интересная статья, комментирующая, что изменение можно найти здесь .

Так что в основном:

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

• аналогичный эффект может быть достигнут путем последующей обработки результата хеш-функции и использования степени 2 для ускоренияОперация по модулю (битовая маска) и компенсация для последующей обработки.

Answer 2

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

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

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

Answer 3

Скажите, что длина набора вашего сегмента равна степени 2 - это делает вычисления модов довольно быстрыми.Это также означает, что выбор сегмента определяется исключительно старшими m битами хеш-кода.(Где m = 32 - n, где n - степень использования 2).Таким образом, вы сразу же отбрасываете полезные биты хеш-кода.

Или, как в , в этом сообщении блога 2006 года говорится:

Предположим, ваш хэш-кодфункция приводит к следующим хеш-кодам среди прочих {x, 2x, 3x, 4x, 5x, 6x ...}, затем все они будут сгруппированы в всего m блоков, где m = table_length / GreatestCommonFactor (table_length, x).(Это тривиально проверить / вывести это).Теперь вы можете выполнить одно из следующих действий, чтобы избежать кластеризации:

...

Или просто сделать m равным table_length, сделав GreatestCommonFactor (table_length, x) равнымдо 1, то есть, делая table_length взаимно простыми с x.И если x может быть почти любым числом, то убедитесь, что table_length является простым числом.