h(x) = [(a*x + b) % p] % N
Давайте сначала рассмотрим a*x + b в изоляции.Если вы представите, что a разбит на сумму степеней двух, a*x - это тогда сумма x битов, сдвинутых влево на совокупность степеней двух, так что каждый бит в x влияет на другие позиции битов.которые установлены в a, и некоторые дополнительные биты, когда суммирование производит переносы в определенных битах.Добавление b микширует в другой набор случайных битов: очень похоже на XORing, но с некоторой дополнительной сложностью от переносов.Если, скажем, x имеет значение между 0 и 255, с битами abcdefgh (каждый из которых равен 0 или 1), то до сих пор мы получили:
(a&1 ? abcdefgh : 0) +
(a&2 ? abcdefgh0 : 0) +
(a&4 ? abcdefgh00 : 0) +
(a&8 ? abcdefgh000 : 0) +
... + // continues for a&16, a&32 etc.
ABCDEFGHIJKLMNOP // however many random bits in "b"
Итак, в "1s""столбец мы суммируем h и P, который может переноситься в столбец" 2s "с g, h и O, и далее он идет.
Если a скажем, 37, то есть 32 + 4 + 1, затем мы добавляем x, x << 2 и x << 5: каждый бит в x, таким образом, влияет на большее количество бит в значении хэша (это хорошодействительно с хэш-функцией криптографической стойкости, изменение любых битов в ключе - будь то один бит, половина или все они - должно в значительной степени случайным образом перевернуть примерно половину бит в значении хэша).
Возвращениев полной формуле давайте представим, что мы пропустили % p и имели только % N, но текущий размер таблицы равен степени двух: % N тогда эквивалентно операции побитового И для некоторого числа менее значимыхбиты.Иными словами, он отбрасывает большую часть случайности, которую мы создали в более значимых битах нашего a * x + b вычисления.Таким образом, чтобы сделать хеш-функцию безопасной для использования с любым количеством сегментов, мы можем сначала ввести % p, что означает, что если в значении хэша есть шаблоны, связанные с степенями двух позиций на этапе суммирования, ониэффективно разбросаны по случайным позициям в диапазоне 0..p.
Рассмотрим, скажем, хэш от 0 до 255 - если бы N равнялось 200, мы бы в два раза с большей вероятностью хешировали ведро в 0..55 диапазонЧтобы сделать этот эффект менее значимым, мы хотим, чтобы значение хеша имело намного больше битов, чем значение MOD, и этот принцип применяется многоуровневым способом к значениям, которые мы должны выбрать для p и N:
a * x + b значения должны иметь тенденцию быть значительно большими, чем p, и распространяться по диапазону, намного большему, чем p, поэтому % p разделяет их больше по сегментам, но
p должно быть намного больше, чем N, поэтому у нас нет низкоиндексированных сегментов со значительно более высокой вероятностью столкновений (что особенно плохо, если вы используете линейное зондирование для разрешенияколлизии).
Например, если мы хотим поддерживать значения от N до 2 24 , и мы выполняем эти вычисления с 32-битным беззнаковымцелые числа, так что a и b имеют случайные значения в этом диапазоне, мы могли бы разделить разницу, выбрав простое число около 2 28 .