Универсальное хеширование - Википедия - Universal hashing

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

Вступление

Предположим, мы хотим сопоставить ключи из некоторой вселенной ${ displaystyle U}$ в ${ displaystyle m}$ ящики (помечены ${ Displaystyle [м] = {0, точки, м-1 }}$). Алгоритм должен будет обработать некоторый набор данных ${ Displaystyle S substeq U}$ из ${ Displaystyle | S | = п}$ ключи, о которых заранее не известно. Обычно целью хеширования является получение небольшого количества коллизий (ключей от ${ displaystyle S}$ что земля в том же мусорном ведре). Детерминированная хеш-функция не может предложить никаких гарантий в состязательной обстановке, если размер ${ displaystyle U}$ больше, чем ${ Displaystyle м cdot п}$, поскольку противник может выбрать ${ displaystyle S}$ быть именно тем прообраз корзины. Это означает, что все ключи данных попадают в одну корзину, что делает хеширование бесполезным. Кроме того, детерминированная хеш-функция не позволяет перефразирование: иногда входные данные оказываются плохими для хеш-функции (например, слишком много коллизий), поэтому хочется изменить хеш-функцию.

Решение этих проблем состоит в том, чтобы случайным образом выбрать функцию из семейства хеш-функций. Семейство функций ${ displaystyle H = {h: U to [m] }}$ называется универсальная семья если, ${ displaystyle forall x, y in U, ~ x neq y: ~~ Pr _ {h in H} [h (x) = h (y)] leq { frac {1} {m }}}$.

Другими словами, любые два ключа Вселенной сталкиваются с вероятностью не более ${ displaystyle 1 / m}$ когда хеш-функция ${ displaystyle h}$ выбирается случайным образом из ${ displaystyle H}$. Это именно та вероятность коллизии, которую мы ожидали бы, если бы хеш-функция назначила действительно случайные хэш-коды каждому ключу. Иногда определение смягчается, чтобы допустить вероятность столкновения ${ Displaystyle О (1 / м)}$. Эта концепция была введена Картером и Вегманом.^[1] в 1977 г. и нашел множество приложений в компьютерных науках (см., например, ^[2]). Если у нас есть верхняя граница ${ displaystyle epsilon <1}$ о вероятности столкновения мы говорим, что имеем ${ displaystyle epsilon}$-почти универсальность.

Многие, но не все универсальные семьи имеют следующие более сильные свойство равномерной разницы:

${ displaystyle forall x, y in U, ~ x neq y}$, когда ${ displaystyle h}$ выбирается случайным образом из семьи ${ displaystyle H}$, разница ${ Displaystyle ч (х) -ч (у) ~ { bmod {~}} м}$ равномерно распределен в ${ Displaystyle [м]}$.

Обратите внимание, что определение универсальности касается только того, ${ displaystyle h (x) -h (y) = 0}$, который считает столкновения. Свойство равномерной разницы сильнее.

(Точно так же универсальное семейство может быть универсальным XOR, если ${ displaystyle forall x, y in U, ~ x neq y}$, Значение ${ Displaystyle ч (х) oplus ч (у) ~ { bmod {~}} м}$ равномерно распределен в ${ Displaystyle [м]}$ куда ${ displaystyle oplus}$ - побитовая операция исключающее ИЛИ. Это возможно только если ${ displaystyle m}$ это степень двойки.)

Еще более сильное условие попарная независимость: у нас есть это свойство, когда ${ displaystyle forall x, y in U, ~ x neq y}$ у нас есть вероятность, что ${ displaystyle x, y}$ будет хешировать любую пару хеш-значений ${ displaystyle z_ {1}, z_ {2}}$ как если бы они были совершенно случайными: ${ Displaystyle P (час (х) = z_ {1} земля h (y) = z_ {2}) = 1 / м ^ {2}}$. Попарную независимость иногда называют сильной универсальностью.

Еще одно свойство - однородность. Мы говорим, что семья однородна, если все хеш-значения одинаково вероятны: ${ Displaystyle Р (час (х) = г) = 1 / м}$ для любого значения хеш-функции ${ displaystyle z}$. Универсальность не означает единообразия. Однако сильная универсальность предполагает единообразие.

Учитывая семейство со свойством равномерного расстояния, можно создать попарно независимое или строго универсальное хеш-семейство, добавив равномерно распределенную случайную константу со значениями в ${ Displaystyle [м]}$ к хеш-функциям. (Аналогично, если ${ displaystyle m}$ является степенью двойки, мы можем добиться попарной независимости от универсального семейства хеш-кодов XOR, выполнив исключающую или с равномерно распределенной случайной константой.) Поскольку сдвиг на константу иногда не имеет значения в приложениях (например, в хеш-таблицах), тщательное различие между свойством равномерного расстояния и попарно независимым иногда не делается.^[3]

Для некоторых приложений (например, хеш-таблиц) важно, чтобы наименее значимые биты хеш-значений также были универсальными. Когда семья строго универсальна, это гарантировано: если ${ displaystyle H}$ сильно универсальная семья с ${ displaystyle m = 2 ^ {L}}$, то семейство функций ${ Displaystyle ч { bmod {2 ^ {L '}}}}$ для всех ${ displaystyle h in H}$ также сильно универсален для ${ Displaystyle L ' leq L}$. К сожалению, этого нельзя сказать о (просто) универсальных семьях. Например, семья, состоящая из функции идентичности ${ Displaystyle ч (х) = х}$ явно универсальный, но семейство, состоящее из функции ${ Displaystyle ч (х) = х { bmod {2 ^ {L '}}}}$ не может быть универсальным.

UMAC и Поли1305-AES и несколько других код аутентификации сообщения алгоритмы основаны на универсальном хешировании.^[4][5]В таких приложениях программное обеспечение выбирает новую хеш-функцию для каждого сообщения на основе уникального одноразового номера для этого сообщения.

Некоторые реализации хеш-таблиц основаны на универсальном хешировании. В таких приложениях обычно программное обеспечение выбирает новую хеш-функцию только после того, как замечает, что "слишком много" ключей столкнулись; до тех пор одна и та же хеш-функция продолжает использоваться снова и снова (некоторые схемы разрешения конфликтов, такие как динамическое идеальное хеширование, выбирайте новую хеш-функцию каждый раз, когда возникает конфликт. Другие схемы разрешения коллизий, такие как кукушка и Хеширование с двумя вариантами, разрешите несколько коллизий перед выбором новой хеш-функции). Обзор самых быстрых известных универсальных и сильно универсальных хеш-функций для целых чисел, векторов и строк можно найти в.^[6]

Математические гарантии

Для любого фиксированного набора ${ displaystyle S}$ из ${ displaystyle n}$ ключи, использование универсального семейства гарантирует следующие свойства.

1. Для любых фиксированных ${ displaystyle x}$ в ${ displaystyle S}$, ожидаемое количество ключей в корзине ${ Displaystyle ч (х)}$ является ${ displaystyle n / m}$. При реализации хеш-таблиц цепочка, это число пропорционально ожидаемому времени выполнения операции с ключом ${ displaystyle x}$ (например, запрос, вставка или удаление).
2. Ожидаемое количество пар ключей ${ displaystyle x, y}$ в ${ displaystyle S}$ с ${ Displaystyle х neq y}$ которые сталкиваются (${ Displaystyle ч (х) = ч (у)}$) ограничена сверху величиной ${ Displaystyle п (п-1) / 2м}$, что в порядке ${ Displaystyle О (п ^ {2} / м)}$. Когда количество ящиков, ${ displaystyle m}$ выбирается линейно по ${ displaystyle n}$ (т.е. определяется функцией в ${ Displaystyle Omega (п)}$) ожидаемое количество столкновений равно ${ Displaystyle О (п)}$. При хешировании в ${ Displaystyle п ^ {2}}$ бункеры, коллизий вообще нет с вероятностью не меньше половины.
3. Ожидаемое количество ключей в ящиках не менее ${ displaystyle t}$ ключей в них ограничено сверху ${ Displaystyle 2n / (т-2 (п / м) +1)}$.^[7] Таким образом, если емкость каждого бункера ограничена до трехкратного среднего размера (${ displaystyle t = 3n / m}$) общее количество ключей в переполненных ячейках не превышает ${ Displaystyle О (м)}$. Это справедливо только для хеш-семейства, вероятность столкновения которого ограничена сверху величиной ${ displaystyle 1 / m}$. Если используется более слабое определение, ограничивая его ${ Displaystyle О (1 / м)}$, этот результат больше не соответствует действительности.^[7]

Поскольку приведенные выше гарантии справедливы для любого фиксированного набора ${ displaystyle S}$, они сохраняются, если набор данных выбран противником. Однако злоумышленник должен сделать этот выбор до (или независимо от) случайного выбора алгоритмом хэш-функции. Если злоумышленник может наблюдать случайный выбор алгоритма, случайность не имеет смысла, и ситуация аналогична детерминированному хешированию.

Вторая и третья гарантия обычно используются вместе с перефразирование. Например, может быть подготовлен рандомизированный алгоритм для обработки некоторых ${ Displaystyle О (п)}$ количество столкновений. Если он наблюдает слишком много столкновений, он выбирает другое случайное ${ displaystyle h}$ из семьи и повторяется. Универсальность гарантирует, что количество повторений будет геометрическая случайная величина.

Конструкции

Поскольку любые компьютерные данные могут быть представлены как одно или несколько машинных слов, обычно требуются хэш-функции для трех типов доменов: машинные слова («целые числа»); векторы машинных слов фиксированной длины; и векторы переменной длины («строки»).

Хеширование целых чисел

Этот раздел относится к случаю хеширования целых чисел, которые помещаются в машинные слова; таким образом, такие операции, как умножение, сложение, деление и т. д., представляют собой дешевые инструкции машинного уровня. Пусть вселенная будет хеширована ${ Displaystyle U = {0, точки, м-1 }}$.

Оригинальное предложение Картера и Вегмана^[1] было выбрать прайм ${ displaystyle p geq m}$ и определить

${ displaystyle h_ {a, b} (x) = ((ax + b) ~ { bmod {~}} p) ~ { bmod {~}} m}$

куда ${ displaystyle a, b}$ случайно выбранные целые числа по модулю ${ displaystyle p}$ с ${ displaystyle a neq 0}$. (Это единственная итерация линейный конгруэнтный генератор.)

Чтобы увидеть это ${ displaystyle H = {h_ {a, b} }}$ универсальная семья, обратите внимание, что ${ Displaystyle ч (х) = ч (у)}$ только когда

${ Displaystyle топор + Ь эквив ау + Ь + я cdot m { pmod {p}}}$

для некоторого целого числа ${ displaystyle i}$ между ${ displaystyle 0}$ и ${ Displaystyle (п-1) / м}$. Если ${ Displaystyle х neq y}$, их отличие, ${ displaystyle x-y}$ отличен от нуля и имеет обратный по модулю ${ displaystyle p}$. Решение для ${ displaystyle a}$ дает

${ Displaystyle а экви я CDOT м CDOT (х-у) ^ {- 1} { pmod {p}}}$.

Есть ${ displaystyle p-1}$ возможные варианты для ${ displaystyle a}$ (поскольку ${ displaystyle a = 0}$ исключено) и, варьируя ${ displaystyle i}$ в допустимом диапазоне, ${ Displaystyle lfloor (п-1) / м rfloor}$ возможные ненулевые значения для правой части. Таким образом, вероятность столкновения равна

${ Displaystyle lfloor (p-1) / m rfloor / (p-1) leq ((p-1) / m) / (p-1) = 1 / m}$.

Другой способ увидеть ${ displaystyle H}$ универсальное семейство через понятие статистическое расстояние. Напишите разницу ${ Displaystyle ч (х) -ч (у)}$ в качестве

${ Displaystyle ч (х) -ч (у) эквив (а (х-у) ~ { bmod {~}} р) { pmod {м}}}$.

С ${ displaystyle x-y}$ отличен от нуля и ${ displaystyle a}$ равномерно распределен в ${ Displaystyle {1, точки, п-1 }}$, следует, что ${ Displaystyle а (х-у)}$ по модулю ${ displaystyle p}$ также равномерно распределен в ${ Displaystyle {1, точки, п-1 }}$. Распределение ${ Displaystyle (ч (х) -ч (у)) ~ { bmod {~}} м}$ таким образом, почти равномерно, с точностью до разницы в вероятности ${ displaystyle pm 1 / p}$ между образцами. В результате статистическое расстояние до однородного семейства равно ${ Displaystyle О (м / п)}$, который становится незначительным, когда ${ displaystyle p gg m}$.

Семейство более простых хеш-функций

${ displaystyle h_ {a} (x) = (ax ~ { bmod {~}} p) ~ { bmod {~}} m}$

только примерно универсальный: ${ Displaystyle Pr {h_ {a} (x) = h_ {a} (y) } leq 2 / m}$ для всех ${ Displaystyle х neq y}$.^[1] Более того, этот анализ почти точен; Картер и Вегман ^[1] покажи это ${ displaystyle Pr {h_ {a} (1) = h_ {a} (m + 1) } geq 2 / (m-1)}$ в любое время ${ Displaystyle (п-1) ~ { bmod {~}} м = 1}$.

Избегайте модульной арифметики

Современное состояние хеширования целых чисел - многократно-сдвиг схема, описанная Dietzfelbinger et al. в 1997 г.^[8] Избегая модульной арифметики, этот метод намного проще реализовать, а на практике он работает значительно быстрее (обычно как минимум в четыре раза).^[9]). Схема предполагает, что количество ящиков является степенью двойки, ${ displaystyle m = 2 ^ {M}}$. Позволять ${ displaystyle w}$ быть количеством бит в машинном слове. Затем хеш-функции параметризуются над нечетными положительными целыми числами. ${ displaystyle a <2 ^ {w}}$ (это вписывается в слово ${ displaystyle w}$ биты). Оценить ${ displaystyle h_ {a} (x)}$, умножить ${ displaystyle x}$ к ${ displaystyle a}$ по модулю ${ displaystyle 2 ^ {w}}$ а затем сохраните высокий порядок ${ displaystyle M}$ биты как хэш-код. В математической записи это

${ displaystyle h_ {a} (x) = (a cdot x , , { bmod {,}} 2 ^ {w}) , , mathrm {div} , , 2 ^ { wM}}$

и это может быть реализовано в C -подобные языки программирования

${ displaystyle h_ {a} (x) =}$ (size_t) (a * x) >> (ш-м)

Эта схема делает нет удовлетворяют свойству равномерной разности и только ${ displaystyle 2 / m}$-почти универсальный; для любого ${ Displaystyle х neq y}$, ${ Displaystyle Pr {h_ {a} (x) = h_ {a} (y) } leq 2 / m}$.

Чтобы понять поведение хэш-функции, обратите внимание, что если ${ displaystyle ax { bmod {2}} ^ {w}}$ и ${ displaystyle ay { bmod {2}} ^ {w}}$ имеют те же самые старшие биты M, тогда ${ Displaystyle а (х-у) { bmod {2}} ^ {ш}}$ имеет либо все единицы, либо все нули в качестве своих M бит наивысшего порядка (в зависимости от того, ${ displaystyle ax { bmod {2}} ^ {w}}$ или же ${ displaystyle ay { bmod {2}} ^ {w}}$ больше). Предположим, что младший бит набора ${ displaystyle x-y}$ появляется на позиции ${ displaystyle w-c}$. С ${ displaystyle a}$ является случайным нечетным целым числом, а нечетные целые имеют обратные звенеть ${ displaystyle Z_ {2 ^ {w}}}$, следует, что ${ Displaystyle а (х-у) { bmod {2}} ^ {ш}}$ будут равномерно распределены среди ${ displaystyle w}$-битовые целые числа с младшим битом установленной позиции ${ displaystyle w-c}$. Вероятность того, что все эти биты - это все 0 или все 1, поэтому не превышает ${ Displaystyle 2/2 ^ {M} = 2 / м}$.С другой стороны, если ${ displaystyle c$, то старшие M битов ${ Displaystyle а (х-у) { bmod {2}} ^ {ш}}$ содержат как 0, так и 1, поэтому очевидно, что ${ Displaystyle ч (х) neq ч (у)}$. Наконец, если ${ displaystyle c = M}$ затем укусил ${ Displaystyle ш-М}$ из ${ Displaystyle а (х-у) { bmod {2}} ^ {ш}}$ равно 1 и ${ displaystyle h_ {a} (x) = h_ {a} (y)}$ если и только если биты ${ Displaystyle ш-1, ldots, ш-М + 1}$ также равны 1, что с вероятностью ${ Displaystyle 1/2 ^ {М-1} = 2 / м}$.

Этот анализ точен, как можно показать на примере ${ Displaystyle х = 2 ^ {ш-М-2}}$ и ${ displaystyle y = 3x}$. Чтобы получить действительно «универсальную» хеш-функцию, можно использовать схему умножения-сложения-сдвига.

${ displaystyle h_ {a, b} (x) = ((ax + b) { bmod {2}} ^ {w}) , mathrm {div} , 2 ^ {w-M}}$

который может быть реализован в C -подобные языки программирования

${ displaystyle h_ {a, b} (x) =}$ (size_t) (a * x + b) >> (ш-М)

куда ${ displaystyle a}$ является случайным нечетным положительным целым числом с ${ displaystyle a <2 ^ {w}}$ и ${ displaystyle b}$ является случайным неотрицательным целым числом с ${ Displaystyle б <2 ^ {ш-М}}$. С этим выбором ${ displaystyle a}$ и ${ displaystyle b}$, ${ Displaystyle Pr {h_ {a, b} (x) = h_ {a, b} (y) } leq 1 / m}$ для всех ${ Displaystyle х not Equiv Y { pmod {2 ^ {w}}}}$.^[10] Это немного отличается, но существенно от неправильного перевода в английской газете.^[11]

Хеширование векторов

В этом разделе рассматривается хеширование вектора машинных слов фиксированной длины. Интерпретировать ввод как вектор ${ displaystyle { bar {x}} = (x_ {0}, dots, x_ {k-1})}$ из ${ displaystyle k}$ машинные слова (целые числа ${ displaystyle w}$ бит каждый). Если ${ displaystyle H}$ является универсальным семейством со свойством равномерного различия, следующее семейство (восходящее к Картеру и Вегману^[1]) также обладает свойством равномерной разности (а значит, универсальным):

${ displaystyle h ({ bar {x}}) = left ( sum _ {i = 0} ^ {k-1} h_ {i} (x_ {i}) right) , { bmod { ~}} м}$, где каждый ${ displaystyle h_ {i} in H}$ выбирается независимо случайно.

Если ${ displaystyle m}$ является степенью двойки, можно заменить суммирование исключающим или.^[12]

На практике, если доступна арифметика с двойной точностью, она создается с помощью семейства хэш-функций с множественным сдвигом.^[13] Инициализируйте хеш-функцию вектором ${ displaystyle { bar {a}} = (a_ {0}, dots, a_ {k-1})}$ случайных странный целые числа на ${ displaystyle 2w}$ бит каждый. Тогда, если количество бункеров равно ${ displaystyle m = 2 ^ {M}}$ за ${ displaystyle M leq w}$:

${ displaystyle h _ { bar {a}} ({ bar {x}}) = left ({ big (} sum _ {i = 0} ^ {k-1} x_ {i} cdot a_ {i} { big)} ~ { bmod {~}} 2 ^ {2w} right) , , mathrm {div} , , 2 ^ {2w-M}}$.

Число умножений можно уменьшить вдвое, что на практике дает примерно двукратное ускорение.^[12] Инициализируйте хеш-функцию вектором ${ displaystyle { bar {a}} = (a_ {0}, dots, a_ {k-1})}$ случайных странный целые числа на ${ displaystyle 2w}$ бит каждый. Следующее семейство хешей является универсальным:^[14]

${ displaystyle h _ { bar {a}} ({ bar {x}}) = left ({ Big (} sum _ {i = 0} ^ { lceil k / 2 rceil} (x_ { 2i} + a_ {2i}) cdot (x_ {2i + 1} + a_ {2i + 1}) { Big)} { bmod {~}} 2 ^ {2w} right) , , mathrm {div} , , 2 ^ {2w-M}}$.

Если операции с двойной точностью недоступны, можно интерпретировать ввод как вектор полуслов (${ displaystyle w / 2}$-битовые целые числа). Затем алгоритм будет использовать ${ Displaystyle lceil к / 2 rceil}$ умножения, где ${ displaystyle k}$ число полуслов в векторе. Таким образом, алгоритм работает со «скоростью» одно умножение на слово ввода.

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

Также возможна сильная универсальность на высокой скорости.^[16] Инициализируйте хеш-функцию вектором ${ displaystyle { bar {a}} = (a_ {0}, dots, a_ {k})}$ случайных целых чисел на ${ displaystyle 2w}$ биты. Вычислить

${ displaystyle h _ { bar {a}} ({ bar {x}}) ^ { mathrm {strong}} = (a_ {0} + sum _ {i = 0} ^ {k-1} a_ {i + 1} x_ {i} { bmod {~}} 2 ^ {2w}) , , mathrm {div} , , 2 ^ {w}}$.

Результат универсален на ${ displaystyle w}$ биты. Экспериментально было обнаружено, что он работает при 0,2 цикла ЦП на байт на последних процессорах Intel для ${ displaystyle w = 32}$.

Хеширование строк

Это относится к хешированию переменный размер вектор машинных слов. Если длина строки может быть ограничена небольшим числом, лучше всего использовать векторное решение сверху (концептуально дополняя вектор нулями до верхней границы). Требуемое пространство - это максимальная длина строки, но время для оценки ${ displaystyle h (s)}$ это просто длина ${ displaystyle s}$. Пока в строке запрещены нули, заполнение нулями можно игнорировать при оценке хэш-функции, не влияя на универсальность.^[12] Обратите внимание: если в строке разрешены нули, то, возможно, лучше всего добавить фиктивный ненулевой символ (например, 1) ко всем строкам перед заполнением: это гарантирует, что универсальность не будет затронута.^[16]

Теперь предположим, что мы хотим хешировать ${ displaystyle { bar {x}} = (x_ {0}, dots, x _ { ell})}$, где хорошая граница ${ displaystyle ell}$ не известно априори. Универсальная семья, предложенная ^[13] лечит строку ${ displaystyle x}$ как коэффициенты многочлена по модулю большого простого числа. Если ${ Displaystyle х_ {я} в [и]}$, позволять ${ Displaystyle п geq макс {и, м }}$ быть простым и определить:

${ displaystyle h_ {a} ({ bar {x}}) = h _ { mathrm {int}} left ({ big (} sum _ {i = 0} ^ { ell} x_ {i} cdot a ^ { ell -i} { big)} { bmod {~}} p right)}$, куда ${ Displaystyle а в [п]}$ равномерно случайный и ${ displaystyle h _ { mathrm {int}}}$ выбирается случайным образом из универсальной целочисленной области отображения семейства ${ Displaystyle [п] mapsto [м]}$.

Используя свойства модульной арифметики, вышеупомянутое можно вычислить без получения больших чисел для больших строк следующим образом:^[17]

uint хэш(Нить Икс, int а, int п)	uint час = ПЕРВОНАЧАЛЬНЫЙ ЗНАЧЕНИЕ	за (uint я=0 ; я < Икс.длина ; ++я)		час = ((час*а) + Икс[я]) мод п	возвращаться час

Этот Катящийся хеш Рабина-Карпа основан на линейный конгруэнтный генератор.^[18]Вышеупомянутый алгоритм также известен как Мультипликативная хеш-функция.^[19] На практике мод оператор и параметр п можно полностью избежать, просто допустив переполнение целого числа, потому что это эквивалентно мод (Максимальное значение Int + 1) на многих языках программирования. В таблице ниже показаны значения, выбранные для инициализации. час и для некоторых популярных реализаций.

Рассмотрим две строки ${ displaystyle { bar {x}}, { bar {y}}}$ и разреши ${ displaystyle ell}$ быть длиной более длинного; для анализа более короткая строка концептуально дополняется нулями до длины ${ displaystyle ell}$. Столкновение перед применением ${ displaystyle h _ { mathrm {int}}}$ подразумевает, что ${ displaystyle a}$ является корнем многочлена с коэффициентами ${ displaystyle { bar {x}} - { bar {y}}}$. Этот многочлен имеет не более ${ displaystyle ell}$ корни по модулю ${ displaystyle p}$, поэтому вероятность столкновения не превосходит ${ displaystyle ell / p}$. Вероятность столкновения из-за случайного ${ displaystyle h _ { mathrm {int}}}$ доводит общую вероятность столкновения до ${ displaystyle { frac {1} {m}} + { frac { ell} {p}}}$. Таким образом, если простое число ${ displaystyle p}$ достаточно велико по сравнению с длиной хешированных строк, семейство очень близко к универсальному (в статистическое расстояние ).

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

Избегайте модульной арифметики

Чтобы уменьшить вычислительные затраты модульной арифметики, на практике используются три приема:^[12]

1. Один выбирает премьер ${ displaystyle p}$ быть близким к степени двойки, например Мерсенн прайм. Это позволяет выполнять арифметические операции по модулю ${ displaystyle p}$ быть реализовано без деления (с использованием более быстрых операций, таких как сложение и сдвиги). Например, на современных архитектурах можно работать с ${ displaystyle p = 2 ^ {61} -1}$, пока ${ displaystyle x_ {i}}$- 32-битные значения.
2. К блокам можно применить векторное хеширование. Например, к каждому блоку из 16 слов строки применяется векторное хеширование, а к ${ Displaystyle lceil к / 16 rceil}$ полученные результаты. Поскольку более медленное хеширование строки применяется к значительно меньшему вектору, это будет по существу так же быстро, как и хеширование вектора.
3. В качестве делителя выбирается степень двойки, что позволяет выполнять арифметические операции по модулю ${ displaystyle 2 ^ {w}}$ быть реализовано без разделения (с использованием более быстрых операций битовая маскировка ). В Семейство хэш-функций NH использует этот подход.

Смотрите также

• K-независимое хеширование
• Скользящее хеширование
• Хеширование табуляции
• Мудрая независимость
• Универсальная односторонняя хеш-функция
• Последовательность с низким расхождением
• Идеальное хеширование

Рекомендации

дальнейшее чтение

• Кнут, Дональд Эрвин (1998). Искусство программирования, Vol. III: Сортировка и поиск (3-е изд.). Чтение, месса; Лондон: Аддисон-Уэсли. ISBN  0-201-89685-0.

внешняя ссылка

• Структуры открытых данных - Раздел 5.1.1 - Мультипликативное хеширование, Пэт Морин