Универсальное хеширование - 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 }}}$

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

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

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

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

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

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

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

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

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

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

Конструкции

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

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

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

Первоначальное предложение Картера и Вегмана состояло в том, чтобы выбрать простое число и определить ${\ displaystyle p \ geq | U |}$

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

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

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

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

для некоторого целого числа между и . Поскольку , если их разность отлична от нуля и имеет обратный по модулю . Решение для урожайности ${\ displaystyle i}$${\ displaystyle 0}$${\ Displaystyle (п-1) / м}$${\ displaystyle p \ geq | U |}$${\ displaystyle x \ neq y}$${\ displaystyle xy}$${\ 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 h (x) -h (y) \ Equiv (a (xy) ~ {\ bmod {~}} p) {\ pmod {m}}}$.

Поскольку не равен нулю и равномерно распределен в , отсюда следует, что по модулю также равномерно распределен в . Таким образом, распределение почти равномерное с точностью до разницы в вероятности между выборками. В результате статистическое расстояние до однородного семейства составляет , которым можно пренебречь, когда . ${\ displaystyle xy}$${\ 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 x \ neq y}$${\ Displaystyle \ Pr \ {h_ {a} (1) = h_ {a} (m + 1) \} \ geq 2 / (m-1)}$${\ Displaystyle (п-1) ~ {\ bmod {~}} м = 1}$

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

Состояние искусства для хеширования целых чисел является множественно-сдвига схемы описывается Dietzfelbinger и соавт. в 1997 году. Избегая модульной арифметики, этот метод намного проще реализовать, а также он работает значительно быстрее на практике (обычно как минимум в четыре раза). Схема предполагает, что количество бункеров является степенью двойки . Позвольте быть количество бит в машинном слове. Затем хеш-функции параметризуются по нечетным положительным целым числам (которые умещаются в слове битов). Чтобы оценить , умножьте по модулю, а затем сохраните старшие биты в качестве хэш-кода. В математической записи это ${\ 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) >> (w-M)

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

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

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

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

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

${\ displaystyle h_ {a, b} (x) =}$ (size_t) (a*x+b) >> (w-M)

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

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

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

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

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

На практике, если доступна арифметика двойной точности, она создается с помощью семейства хеш-функций с множественным сдвигом. Инициализируйте хеш-функцию вектором случайных нечетных целых чисел по битам каждого. Тогда, если количество ящиков рассчитано на : ${\ 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}}$.

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

${\ 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}$

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

Также возможна сильная универсальность на высокой скорости. Инициализируйте хеш-функцию вектором случайных целых чисел в битах. Вычислить ${\ 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}}$.

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

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

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

Теперь предположим, что мы хотим хешировать , когда хорошая оценка априори неизвестна. Универсальное семейство, предложенное авторами, рассматривает строку как коэффициенты многочлена по модулю большого простого числа. Если , позвольте быть простым и определить: ${\ displaystyle {\ bar {x}} = (x_ {0}, \ dots, x _ {\ ell})}$${\ displaystyle \ ell}$${\ 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 [м]}$

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

uint hash(String x, int a, int p)
	uint h = INITIAL_VALUE
	for (uint i=0 ; i < x.length ; ++i)
		h = ((h*a) + x[i]) mod p
	return h

Этот скользящий хеш Рабина-Карпа основан на линейном конгруэнтном генераторе . Вышеупомянутый алгоритм также известен как мультипликативная хеш-функция . На практике оператора mod и параметра p можно полностью избежать, просто разрешив целочисленное переполнение, потому что это эквивалентно mod ( Max-Int-Value + 1) во многих языках программирования. В таблице ниже показаны значения, выбранные для инициализации h и a для некоторых популярных реализаций.

Рассмотрим две строки и пусть будет длина более длинной; для анализа более короткая строка концептуально дополняется нулями до длины . Столкновение перед применением подразумевает, что это корень многочлена с коэффициентами . Этот многочлен имеет не больше корней по модулю , поэтому вероятность столкновения не больше . Вероятность столкновения из-за случайности доводит общую вероятность столкновения до . Таким образом, если простое число достаточно велико по сравнению с длиной хешированных строк, семейство очень близко к универсальному (по статистической дистанции ). ${\ 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}$

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

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

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

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

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

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

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

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

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

Внешние ссылки

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