Универсальное хеширование

Техника выбора хеш-функций

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

Введение

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

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

Другими словами, любые два разных ключа вселенной сталкиваются с максимальной вероятностью, когда хеш-функция рисуется равномерно случайным образом из . Это именно та вероятность коллизии, которую мы могли бы ожидать, если бы хэш-функция присваивала каждому ключу действительно случайные хэш-коды. ${\displaystyle 1/m}$ ${\displaystyle h}$ ${\displaystyle H}$

Иногда определение смягчается постоянным коэффициентом, требуя только вероятность столкновения, а не . Эта концепция была введена Картером и Вегманом ^[1] в 1977 году и нашла многочисленные применения в информатике (см., например, [ ^2] ) . ${\displaystyle O(1/m)}$ ${\displaystyle \leq 1/m}$

Если у нас есть верхняя граница вероятности столкновения, мы говорим, что имеем -почти универсальность. Так, например, универсальная семья обладает почти универсальностью. ${\displaystyle \epsilon <1}$ ${\displaystyle \epsilon }$ ${\displaystyle 1/m}$

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

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

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

(Аналогично, универсальное семейство может быть универсальным XOR , если значение равномерно распределено в где — побитовое исключающее действие или операция. Это возможно только в том случае, если — степень двойки.) ${\displaystyle \forall x,y\in U,~x\neq y}$ ${\displaystyle h(x)\oplus h(y)~{\bmod {~}}m}$ ${\displaystyle [m]}$ ${\displaystyle \oplus }$ ${\displaystyle m}$

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

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

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

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

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

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

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

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

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

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

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

Конструкции

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

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

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

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

${\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 h(x)=h(y)}$

${\displaystyle ax+b\equiv ay+b+i\cdot m{\pmod {p}}}$

для некоторого целого числа между и . Так как , если их разность отлична от нуля и имеет обратную по модулю . Решение проблемы доходности ${\displaystyle i}$ ${\displaystyle 0}$ ${\displaystyle (p-1)/m}$ ${\displaystyle p\geq |U|}$ ${\displaystyle x\neq y}$ ${\displaystyle x-y}$ ${\displaystyle p}$ ${\displaystyle a}$

${\displaystyle a\equiv i\cdot m\cdot (x-y)^{-1}{\pmod {p}}}$.

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

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

Другой способ увидеть универсальную семью – это использовать понятие статистического расстояния . Запишите разницу как ${\displaystyle H}$ ${\displaystyle h(x)-h(y)}$

${\displaystyle h(x)-h(y)\equiv (a(x-y)~{\bmod {~}}p){\pmod {m}}}$.

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

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

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

является лишь приблизительно универсальным: для всех . ^[1] Более того, этот анализ почти точен; Картер и Вегман ^[1] показывают, что всякий раз, когда . ${\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 (p-1)~{\bmod {~}}m=1}$

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

Современным способом хеширования целых чисел является схема с множественным сдвигом , описанная Дитцфельбингером и др. в 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^{w-M}.}$

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

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

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

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

где – случайное положительное целое число с и – случайное неотрицательное целое число с . Для этого необходимо выполнить арифметические действия с целыми числами без знака -бита. Эта версия множественного сдвига принадлежит Дитцфельбингеру и позже была более точно проанализирована Вельфелем. ^[10] ${\displaystyle a}$ ${\displaystyle a<2^{2w}}$ ${\displaystyle b}$ ${\displaystyle b<2^{2w}}$ ${\displaystyle 2w}$

Векторы хеширования

В этом разделе рассматривается хеширование вектора машинных слов фиксированной длины. Интерпретируйте входные данные как вектор машинных слов ( каждое целое число битов). Если — универсальное семейство со свойством равномерной разности, то следующее семейство (восходящее к Картеру и Вегману ^[1] ) также обладает свойством равномерной разности (и, следовательно, является универсальным): ${\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 {~}}m}$, где каждый выбирается независимо случайным образом. ${\displaystyle h_{i}\in H}$

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

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

Можно сократить вдвое количество умножений, что на практике примерно означает двукратное ускорение. ^[11] Инициализируйте хэш-функцию вектором случайных нечетных целых чисел по битам каждое. Следующее семейство хешей является универсальным: ^[13] ${\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 k/2\rceil }$ ${\displaystyle k}$

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

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

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

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

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

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

${\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 a\in [p]}$ ${\displaystyle h_{\mathrm {int} }}$ ${\displaystyle [p]\mapsto [m]}$

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

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 час                        

Этот скользящий хэш Рабина-Карпа основан на линейном конгруэнтном генераторе . ^[17] Вышеуказанный алгоритм также известен как мультипликативная хеш-функция . ^[18] На практике оператора 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}$

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

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

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

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-независимое хеширование  - семейство хэш-функций
• Прокатное хеширование  - хэш-функция, при которой входные данные хешируются в окне, которое перемещается по входным данным.Pages displaying wikidata descriptions as a fallback
• Табулационное хеширование  – хэш-функции, вычисляемые методом исключающего или
• Минимальная независимость  – метод интеллектуального анализа данныхPages displaying short descriptions of redirect targets
• Универсальная односторонняя хеш-функция  - тип универсальной хеш-функции в криптографии, предложенный в качестве альтернативы устойчивым к коллизиям хеш-функциям.Pages displaying wikidata descriptions as a fallback
• Последовательность с низким расхождением  - Тип математической последовательности
• Идеальное хеширование  – хэш-функция без каких-либо коллизий.Pages displaying short descriptions of redirect targets

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

1. Картер, Ларри; Вегман, Марк Н. (1979). «Универсальные классы хеш-функций». Журнал компьютерных и системных наук . 18 (2): 143–154. дои : 10.1016/0022-0000(79)90044-8 . Конференц-версия в STOC'77.
2. Милтерсен, Питер Бро. «Универсальное хеширование» (PDF) . Архивировано из оригинала (PDF) 24 мая 2011 года . Проверено 24 июня 2009 г.
3. Мотвани, Раджив; Рагхаван, Прабхакар (1995). Рандомизированные алгоритмы . Издательство Кембриджского университета. п. 221. ИСБН 0-521-47465-5.
4. Дэвид Вагнер, изд. «Достижения криптологии - КРИПТО 2008». п. 145.
5. Жан-Филипп Омассон, Вилли Мейер, Рафаэль Фан, Лука Хенцен. «Хеш-функция БЛЕЙК». 2014. с. 10.
6. Торуп, Миккель (2015). «Высокоскоростное хеширование целых и строк». arXiv : 1504.06804 [cs.DS].
7. Баран, Илья; Демейн, Эрик Д.; Патрашку, Михай (2008). «Подквадратичные алгоритмы для 3SUM» (PDF) . Алгоритмика . 50 (4): 584–596. дои : 10.1007/s00453-007-9036-3. S2CID  9855995.
8. Дитцфельбингер, Мартин; Хагеруп, Торбен; Катахайнен, Юрки; Пенттонен, Мартти (1997). «Надежный рандомизированный алгоритм решения задачи ближайшей пары» (Постскриптум) . Журнал алгоритмов . 25 (1): 19–51. дои : 10.1006/jagm.1997.0873 . Проверено 10 февраля 2011 г.
9. Торуп, Миккель (18 декабря 2009 г.). «Алгоритмы из учебника СОДА».
10. Вельфель, Филипп (1999). Эффективное сильно универсальное и оптимально универсальное хеширование . Математические основы информатики 1999. LNCS. Том. 1672. стр. 262–272. дои : 10.1007/3-540-48340-3_24.
11. Торуп, Миккель (2009). Хеширование строк для линейного зондирования . Учеб. 20-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA) . стр. 655–664. CiteSeerX 10.1.1.215.4253 . дои : 10.1137/1.9781611973068.72. ISBN  978-0-89871-680-1., раздел 5.3
12. Дитцфельбингер, Мартин; Гил, Джозеф; Матиас, Йоси; Пиппенджер, Николас (1992). Полиномиальные хеш-функции надежны (расширенное резюме) . Учеб. 19-й Международный коллоквиум по автоматам, языкам и программированию (ICALP) . стр. 235–246.
13. Блэк, Дж.; Халеви, С.; Кравчик, Х.; Кровец, Т. (1999). UMAC: Быстрая и безопасная аутентификация сообщений (PDF) . Достижения в криптологии (CRYPTO '99) ., Уравнение 1
14. Патрашку, Михай ; Торуп, Миккель (2011). Возможности простого хеширования таблиц . Материалы 43-го ежегодного симпозиума ACM по теории вычислений (STOC '11) . стр. 1–10. arXiv : 1011.5200 . дои : 10.1145/1993636.1993638. ISBN 9781450306911.
15. Касер, Оуэн; Лемир, Дэниел (2013). «Строго универсальное хеширование строк происходит быстро». Компьютерный журнал . Издательство Оксфордского университета. 57 (11): 1624–1638. arXiv : 1202.4961 . doi : 10.1093/comjnl/bxt070.
16. «Слайды курса еврейского университета» (PDF) .
17. Роберт Узгалис. «Библиотечные хэш-функции». 1996.
18. Канковск, Питер. «Хеш-функции: эмпирическое сравнение».
19. Йигит, Озан. «Строковые хэш-функции».
20. Керниган; Ричи (1988). «6» . Язык программирования C (2-е изд.). Прентис Холл. стр. 118. ISBN 0-13-110362-8.{{cite book}}: CS1 maint: multiple names: authors list (link)
21. «Строка (платформа Java SE 6)» . docs.oracle.com . Проверено 10 июня 2015 г.

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

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

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

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