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

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

• 1 Введение
• 2 Математические гарантии
• 3 Конструкции
  • 3.1 Хеширование целых чисел
    • 3.1.1 Избегание модульной арифметики
  • 3.2 Хеширование векторов
  • 3.3 Хеширование строк
    • 3.3.1 Избегание модульной арифметики
• 4 См. Также
• 5 Ссылки
• 6 Дополнительная литература
• 7 Внешние ссылки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первоначальное предложение Картера и Вегмана было выбрать простое число $p\; \ge \; m\; \{\backslash \; displaystyle\; p\; \backslash \; geq\; m\}$и определить

$ha,\; b\; (x)\; =\; ((ax\; +\; b)\; mod\; p)\; mod\; m\; \{\backslash \; displaystyle\; h\_\; \{a,\; b\}\; (x)\; =\; ((ax\; +\; b)\; ~\; \{\backslash \; bmod\; \{~\}\}\; p)\; ~\; \{\backslash \; bmod\; \{~\}\}\; m\}$

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

Чтобы увидеть, что $H\; =\; \{ha,\; b\}\; \{\backslash \; displaystyle\; H\; =\; \backslash \; \{h\_\; \{a,\; b\; \}\; \backslash \}\}$- универсальное семейство, обратите внимание, что $h\; (x)\; =\; h\; (y)\; \{\backslash \; displaystyle\; h\; (x)\; =\; h\; (y)\}$имеет место только когда

$ax\; +\; b\; \equiv \; ay\; +\; b\; +\; i\; \cdot \; m\; (mod\; p)\; \{\backslash \; displaystyle\; ax\; +\; b\; \backslash \; Equiv\; ay\; +\; b\; +\; i\; \backslash \; cdot\; m\; \{\backslash \; pmod\; \{p\}\}\}$

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

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

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

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

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

$h\; (x)\; -\; h\; (y)\; \equiv \; (a\; (Икс\; -\; Y)\; по\; модулю\; р)\; (по\; модулю\; М)\; \{\backslash \; Displaystyle\; ч\; (х)\; -ч\; (у)\; \backslash \; эквив\; (а\; (ху)\; ~\; \{\backslash \; bmod\; \{~\}\}\; р)\; \{\backslash \; pmod\; \{m\}\}\}$.

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

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

$ha\; (x)\; =\; (ax\; mod\; p)\; mod\; m\; \{\backslash \; displaystyle\; h\_\; \{a\}\; (x)\; =\; (ax\; ~\; \{\backslash \; bmod\; \{~\}\; \}\; p)\; ~\; \{\backslash \; bmod\; \{~\}\}\; m\}$

является приблизительно универсальным: $Pr\; \{ha\; (x)\; =\; ha\; (y)\}\; \le \; 2\; /\; m\; \{\backslash \; displaystyle\; \backslash \; Pr\; \backslash \; \{h\_\; \{a\; \}\; (x)\; =\; h\_\; \{a\}\; (y)\; \backslash \}\; \backslash \; leq\; 2\; /\; m\}$для всех $x\; \ne \; y\; \{\backslash \; displaystyle\; x\; \backslash \; neq\; y\}$. Более того, этот анализ почти точен; Картер и Вегман показывают, что $Pr\; \{ha\; (1)\; =\; ha\; (m\; +\; 1)\}\; \ge \; 2\; /\; (m\; -\; 1)\; \{\backslash \; displaystyle\; \backslash \; Pr\; \backslash \; \{h\_\; \{a\}\; (1)\; =\; h\_\; \{a\}\; (\; m\; +\; 1)\; \backslash \}\; \backslash \; geq\; 2\; /\; (m-1)\}$всякий раз, когда $(p\; -\; 1)\; mod\; m\; =\; 1\; \{\backslash \; displaystyle\; (p-1)\; ~\; \{\backslash \; bmod\; \{~\}\; \}\; m\; =\; 1\}$.

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

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

$ha\; (x)\; =\; (a\; \cdot \; x\; mod\; 2\; w)\; div\; 2\; w\; -\; M\; \{\backslash \; displaystyle\; h\_\; \{a\}\; (x)\; =\; (a\; \backslash \; cdot\; x\; \backslash ,\; \backslash ,\; \{\backslash \; bmod\; \{\backslash ,\}\}\; 2\; ^\; \{w\})\; \backslash ,\; \backslash ,\; \backslash \; mathrm\; \{div\}\; \backslash ,\; \backslash ,\; 2\; ^\; \{wM\}\}$

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

$ha\; (x)\; =\; \{\backslash \; displaystyle\; h\_\; \{a\}\; (x)\; =\}$(size_t) (a * x)>>(wM)

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

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

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

$ha,\; b\; (x)\; =\; ((ax\; +\; b)\; mod\; 2\; w)\; div\; 2\; w\; -\; M\; \{\backslash \; displaystyle\; h\_\; \{\; a,\; b\}\; (x)\; =\; ((ax\; +\; b)\; \{\backslash \; bmod\; \{2\}\}\; ^\; \{w\})\; \backslash ,\; \backslash \; mathrm\; \{div\}\; \backslash ,\; 2\; ^\; \{wM\}\}$

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

$ha,\; b\; (x)\; =\; \{\backslash \; displaystyle\; h\_\; \{a,\; b\}\; (x)\; =\}$(size_t) (a * x + b)>>(wM)

где $a\; \{\backslash \; displaystyle\; a\}$- случайное нечетное положительное целое число с и $b\; \{\backslash \; displaystyle\; b\}$- случайное неотрицательное целое число с . С этими вариантами выбора $a\; \{\backslash \; displaystyle\; a\}$и $b\; \{\backslash \; displaystyle\; b\}$, $Pr\; \{ha,\; b\; (x)\; =\; ha,\; b\; (y)\}\; \le \; 1\; /\; m\; \{\backslash \; displaystyle\; \backslash \; Pr\; \backslash \; \{h\_\; \{a,\; b\}\; (x)\; =\; h\_\; \{a,\; b\}\; (y)\; \backslash \}\; \backslash \; leq\; 1\; /\; m\}$для всех $x\; \not\equiv \; y\; (по\; модулю\; 2\; вес)\; \{\backslash \; Displaystyle\; х\; \backslash \; не\; \backslash \; эквив\; у\; \{\backslash \; pmod\; \{2\; ^\; \{w\}\}\}\}$. Это немного отличается, но важно, от неправильного перевода в английской статье.

Хеширующие векторы

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

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

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

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

$га\; ¯\; (Икс\; ¯)\; знак\; равно\; ((\sum \; я\; =\; 0\; К\; -\; 1\; xi\; \cdot \; ai)\; mod\; 2\; 2\; w)\; div\; 2\; 2\; w\; -\; M\; \{\backslash \; displaystyle\; h\; \_\; \{\backslash \; bar\; \{a\}\}\; (\{\backslash \; bar\; \{x\}\})\; =\; \backslash \; left\; (\{\backslash \; big\; (\}\; \backslash \; sum\; \_\; \{i\; =\; 0\}\; ^\; \{k-1\}\; x\_\; \{i\}\; \backslash \; cdot\; a\_\; \{i\}\; \{\backslash \; big)\}\; ~\; \{\backslash \; bmod\; \{~\}\}\; 2\; ^\; \{2w\; \}\; \backslash \; right)\; \backslash ,\; \backslash ,\; \backslash \; mathrm\; \{div\}\; \backslash ,\; \backslash ,\; 2\; ^\; \{2w-M\}\}$.

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

$ha\; ¯\; (x\; ¯)\; =\; ((\sum \; i\; =\; 0\; \lceil \; k\; /\; 2\; \rceil \; (x\; 2\; i\; +\; a\; 2\; i)\; \cdot \; (x\; 2\; i\; +\; 1\; +\; a\; 2\; i\; +\; 1))\; mod\; 2\; 2\; вес)\; div\; 2\; 2\; вес\; -\; M\; \{\backslash \; displaystyle\; h\; \_\; \{\backslash \; bar\; \{a\}\}\; (\{\backslash \; bar\; \{x\}\})\; =\; \backslash \; left\; (\{\backslash \; Big\; (\}\; \backslash \; sum\; \_\; \{i\; =\; 0\})\; ^\; \{\backslash \; lceil\; k\; /\; 2\; \backslash \; rceil\}\; (x\_\; \{2i\}\; +\; a\_\; \{2i\})\; \backslash \; cdot\; (x\_\; \{2i\; +\; 1\}\; +\; a\_\; \{2i\; +\; 1\})\; \{\backslash \; Big)\}\; \{\backslash \; bmod\; \{~\}\}\; 2\; ^\; \{2w\}\; \backslash \; right)\; \backslash ,\; \backslash ,\; \backslash \; mathrm\; \{div\}\; \backslash ,\; \backslash ,\; 2\; ^\; \{2w-M\}\}$.

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

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

Также возможна сильная универсальность при высокой скорости. Инициализируйте хеш-функцию вектором $a\; ¯\; =\; (a\; 0,\dots ,\; ak)\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{a\}\}\; =\; (a\_\; \{0\},\; \backslash \; dots,\; a\_\; \{k\})\}$случайных целых чисел в $2\; w\; \{\backslash \; displaystyle\; 2w\}$битах. Вычислить

$ха\; ¯\; (x\; ¯)\; strong\; =\; (a\; 0\; +\; \sum \; i\; =\; 0\; k\; -\; 1\; ai\; +\; 1\; xi\; mod\; 2\; 2\; w)\; div\; 2\; w\; \{\backslash \; displaystyle\; h\; \_\; \{\backslash \; bar\; \{a\}\}\; (\{\backslash \; bar\; \{x\}\})\; ^\; \{\backslash \; mathrm\; \{strong\}\}\; =\; (a\_\; \{0\}\; +\; \backslash \; sum\; \_\; \{i\; =\; 0\}\; ^\; \{k-1\}\; a\_\; \{i\; +\; 1\}\; x\_\; \{i\}\; \{\backslash \; bmod\; \{~\}\; \}\; 2\; ^\; \{2w\})\; \backslash ,\; \backslash ,\; \backslash \; mathrm\; \{div\}\; \backslash ,\; \backslash ,\; 2\; ^\; \{w\}\}$.

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

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

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

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

$ha\; (x\; ¯)\; =\; намек\; ((\sum \; i\; =\; 0\; \ell \; xi\; \cdot \; a\; \ell \; -\; i)\; mod\; p)\; \{\backslash \; displaystyle\; h\_\; \{a\}\; (\{\backslash \; bar\; \{x\}\})\; =\; h\; \_\; \{\backslash \; mathrm\; \{int\}\}\; \backslash \; left\; (\{\backslash \; big\; (\}\; \backslash \; sum\; \_\; \{i\; =\; 0\}\; ^\; \{\backslash \; ell\}\; x\_\; \{i\}\; \backslash \; cdot\; a\; ^\; \{\backslash \; ell\; -i\}\; \{\backslash \; big)\}\; \{\backslash \; bmod\; \{~\}\}\; p\; \backslash \; right)\}$, где $a\; \in \; [p]\; \{\backslash \; displaystyle\; a\; \backslash \; in\; [p]\}$является равномерно случайным, а $подсказка\; \{\backslash \; displaystyle\; h\; \_\; \{\backslash \; mathrm\; \{int\}\}\}$выбирается случайным образом из целочисленной области универсального сопоставления семейств $[p]\; m\; [m\; ]\; \{\backslash \; displaystyle\; [p]\; \backslash \; mapsto\; [m]\}$.

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

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

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

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

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

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

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

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

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

1. ^ Картер, Ларри; Вегман, Марк Н. (1979). «Универсальные классы хеш-функций». Журнал компьютерных и системных наук. 18 (2): 143–154. DOI : 10.1016 / 0022-0000 (79) 90044-8. Версия для конференции в STOC'77.
2. ^Милтерсен, Питер Бро. «Универсальное хеширование» (PDF). Архивировано из оригинала (PDF) 24 мая 2011 г. Дата обращения 24 июня 2009 г.
3. ^Мотвани, Раджив; Рагхаван, Прабхакар (1995). Рандомизированные алгоритмы. Издательство Кембриджского университета. п. 221. ISBN 0-521-47465-5.
4. ^Давид Вагнер, изд. «Достижения в криптологии - CRYPTO 2008». п. 145.
5. ^Жан-Филипп Аумассон, Вилли Мейер, Рафаэль Фан, Лука Хензен. «Хеш-функция BLAKE». 2014. с. 10.
6. ^Thorup, Mikkel (2015). «Высокоскоростное хеширование для целых чисел и строк». arXiv : 1504.06804 [cs.DS ].
7. ^ Баран, Илья; Demaine, Erik D.; Пэтрашку, Михай (2008). «Субквадратные алгоритмы для 3SUM» (PDF). Алгоритмика. 50 (4): 584–596. doi : 10.1007 / s00453-007-9036-3.
8. ^Дицфельбингер, Мартин; Хагеруп, Торбен; Катаянен, Юрки; Пенттонен, Марти (1997). «Надежный рандомизированный алгоритм для задачи ближайшей пары» (Postscript). Журнал алгоритмов. 25 (1): 19–51. doi : 10.1006 / jagm.1997.0873. Проверено 10 февраля 2011 г.
9. ^Thorup, Mikkel. «Алгоритмы учебников в SODA».
10. ^Вельфель, Филипп (2003). Über die Komplexität der Multiplikation in eingeschränkten Branchingprogrammmodellen (PDF) (Ph.D.). Universität Dortmund. Проверено 18 сентября 2012 г.
11. ^Вельфель, Филипп (1999). Эффективное строго универсальное и оптимально универсальное хеширование. Математические основы информатики 1999. LNCS. 1672 . С. 262–272. doi : 10.1007 / 3-540-48340-3_24.
12. ^ Thorup, Mikkel (2009). Хеширование строк для линейного зондирования. Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 655–664. CiteSeerX 10.1.1.215.4253. doi :10.1137/1.9781611973068.72., section 5.3
13. ^ Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas (1992). Polynomial Hash Functions Are Reliable (Extended Abstract). Proc. 19th International Colloquium on Automata, Languages and Programming (ICALP). pp. 235–246.
14. ^Black, J.; Halevi, S.; Krawczyk, H.; Krovetz, T. (1999). UMAC: Fast and Secure Message Authentication (PDF). Advances in Cryptology (CRYPTO '99)., Equation 1
15. ^Pătraşcu, Mihai ; Thorup, Mikkel (2011). The power of simple tabulation hashing. Proceedings of the 43rd annual ACM Symposium on Theory of Computing (STOC '11). pp. 1–10. arXiv :1011.5200. doi :10.1145/1993636.1993638.
16. ^ Kaser, Owen; Lemire, Daniel (2013). "Strongly universal string hashing is fast". Computer Journal. Издательство Оксфордского университета. 57(11): 1624–1638. arXiv :1202.4961. doi :10.1093/comjnl/bxt070.
17. ^"Hebrew University Course Slides" (PDF).
18. ^Robert Uzgalis. "Library Hash Functions". 1996.
19. ^Kankowsk, Peter. "Hash functions: An empirical comparison".
20. ^Yigit, Ozan. "String hash functions".
21. ^Kernighan; Ritchie (1988). "6". The C Programming Language (2nd ed.). pp. 118. ISBN 0-13-110362-8.CS1 maint: multiple names: authors list (link )
22. ^"String (Java Platform SE 6)". docs.oracle.com. Retrieved 2015-06-10.

• Knuth, Donald Ervin (1998). The Art of Computer Programming, Vol. III: Sorting and Searching (3rd ed.). Reading, Mass; London: Addison-Wesley. ISBN 0-201-89685-0.

• Open Data Structures - Section 5.1.1 - Multiplicative Hashing, Pat Morin