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

Методика выбора хэш-функций

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

Введение

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

Несколько реализаций хэш-таблиц основаны на универсальном хэшировании. В таких приложениях обычно программное обеспечение выбирает новую хэш-функцию только после того, как замечает, что столкнулось «слишком много» ключей; до тех пор одна и та же хэш-функция продолжает использоваться снова и снова. (Некоторые схемы разрешения коллизий, такие как динамическое идеальное хэширование , выбирают новую хэш-функцию каждый раз, когда происходит столкновение. Другие схемы разрешения коллизий, такие как хэширование кукушки и хэширование с двумя вариантами , допускают несколько коллизий перед выбором новой хэш-функции). Обзор самых быстрых известных универсальных и строго универсальных хэш-функций для целых чисел, векторов и строк можно найти в. ^[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», то имеет либо все 1, либо все 0 в качестве своих битов высшего порядка M (в зависимости от того, больше или ). Предположим, что младший установленный бит из появляется в позиции . Поскольку является случайным нечетным целым числом, а нечетные целые числа имеют обратные в кольце , следует, что будет равномерно распределено среди -битных целых чисел с младшим установленным битом в позиции . Вероятность того, что эти биты все равны 0 или все равны 1, составляет, таким образом, не более . С другой стороны, если , то биты высшего порядка M из содержат как 0, так и 1, поэтому определенно, что . Наконец, если то бит из равен 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}}$.

Результат строго универсален по битам. Экспериментально было обнаружено, что он работает на 0,2 цикла ЦП на байт на последних процессорах 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 для ( uint i = 0 ; i < x . length ; ++ i ) h = (( h * a ) + x [ i ]) mod p return h                        

Этот хэш-функция Рабина-Карпа основана на линейном конгруэнтном генераторе . ^[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. Выбирается простое число , близкое к степени двойки, например, простое число Мерсенна . Это позволяет реализовать арифметику по модулю без деления (используя более быстрые операции, такие как сложение и сдвиги). Например, на современных архитектурах можно работать с , тогда как ' являются 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 short descriptions of redirect targets
• Табуляционное хеширование  – хеш-функции, вычисляемые методом исключающего или
• Минимальная независимость  – Метод интеллектуального анализа данных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. doi : 10.1016/0022-0000(79)90044-8 . Версия конференции в STOC'77.
2. Miltersen, Peter Bro. "Universal Hashing" (PDF) . Архивировано из оригинала (PDF) 24 мая 2011 г. . Получено 24 июня 2009 г. .
3. Мотвани, Раджив; Рагхаван, Прабхакар (1995). Рандомизированные алгоритмы . Cambridge University Press. стр. 221. ISBN 0-521-47465-5.
4. Дэвид Вагнер, редактор. «Достижения в криптологии - CRYPTO 2008». стр. 145.
5. Жан-Филипп Омассон, Вилли Майер, Рафаэль Фан, Лука Хензен. «Хэш-функция BLAKE». 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. doi :10.1006/jagm.1997.0873 . Получено 10 февраля 2011 г.
9. Торуп, Миккель (18 декабря 2009 г.). «Алгоритмы из учебника СОДА».
10. Вёльфель, Филипп (1999). Эффективное строго универсальное и оптимально универсальное хеширование . Математические основы компьютерной науки 1999. LNCS. Т. 1672. С. 262–272. doi :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. Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas (1992). Полиномиальные хэш-функции надежны (расширенный реферат) . Труды 19-го Международного коллоквиума по автоматам, языкам и программированию (ICALP) . стр. 235–246.
13. Блэк, Дж.; Халеви, С.; Кравчик, Х.; Кровец, Т. (1999). UMAC: Быстрая и безопасная аутентификация сообщений (PDF) . Достижения в криптологии (CRYPTO '99) ., Уравнение 1
14. Pătraşcu, Mihai ; Thorup, Mikkel (2011). The power of simple tabulation hashing . Труды 43-го ежегодного симпозиума ACM по теории вычислений (STOC '11) . стр. 1–10. arXiv : 1011.5200 . doi :10.1145/1993636.1993638. ISBN 9781450306911.
15. Kaser, Owen; Lemire, Daniel (2013). «Строго универсальное хеширование строк — это быстро». Computer Journal . 57 (11). Oxford University Press: 1624–1638. arXiv : 1202.4961 . doi :10.1093/comjnl/bxt070.
16. «Слайды курса Еврейского университета» (PDF) .
17. Роберт Узгалис. «Библиотечные хэш-функции». 1996.
18. Канковск, Питер. «Хэш-функции: эмпирическое сравнение».
19. Йигит, Озан. «Строковые хэш-функции».
20. Керниган; Ритчи (1988). "6" . Язык программирования C (2-е изд.). Prentice Hall. стр. 118. ISBN 0-13-110362-8.{{cite book}}: CS1 maint: multiple names: authors list (link)
21. "Строка (Java Platform SE 6)". docs.oracle.com . Получено 2015-06-10 .

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

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

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

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