k-независимое хеширование - k-independent hashing

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

• 1 Предпосылки
• 2 Определения
• 3 Методы
  • 3.1 Полиномы со случайными коэффициентами
  • 3.2 Хеширование таблиц
• 4 Независимость, необходимая для различных методов хеширования
• 5 Ссылки
• 6 Дополнительная литература

Целью хеширования обычно является отображение ключей из некоторого большого домена (юниверса) $U\; \{\backslash \; displaystyle\; U\}$в меньший диапазон, например, $m\; \{\backslash \; displaystyle\; m\}$ящики (с меткой $[m]\; =\; \{0,\dots ,\; m\; -\; 1\}\; \{\backslash \; displaystyle\; [m]\; =\; \backslash \; \{0,\; \backslash \; dots,\; м-1\; \backslash \}\}$). При анализе рандомизированных алгоритмов и структур данных часто желательно, чтобы хеш-коды различных ключей «вели себя случайным образом». Например, если хэш-код каждого ключа был независимым случайным выбором в $[m]\; \{\backslash \; displaystyle\; [m]\}$, количество ключей на ячейку можно было бы проанализировать с помощью Граница Чернова. Детерминированная хеш-функция не может предложить такую ​​гарантию в условиях состязания, поскольку злоумышленник может выбрать ключи, которые будут точно прообразом бункера. Кроме того, детерминированная хеш-функция не позволяет перехешировать: иногда входные данные оказываются плохими для хеш-функции (например, слишком много коллизий), поэтому хотелось бы изменить хеш-функцию.

Решение этих проблем заключается в случайном выборе функции из большого семейства хеш-функций. Случайность при выборе хэш-функции может использоваться для гарантии некоторого желаемого случайного поведения хэш-кодов любых интересующих ключей. Первым определением в этих строках было универсальное хеширование, которое гарантирует низкую вероятность конфликта для любых двух назначенных ключей. Концепция $k\; \{\backslash \; displaystyle\; k\}$-независимого хеширования, введенная Вегманом и Картером в 1981 году, усиливает гарантии случайного поведения семейств назначенных ключей и добавляет гарантию равномерного распределения хэш-кодов.

Самое строгое определение, введенное Вегманом и Картером под названием «строго универсальное $k\; \{\backslash \; displaystyle\; \_\; \{k\}\}$семейство хешей», следующее. Семейство хеш-функций $H\; =\; \{h:\; U\; \to \; [m]\}\; \{\backslash \; displaystyle\; H\; =\; \backslash \; \{h:\; U\; \backslash \; to\; [m]\; \backslash \}\}$равно $k\; \{\backslash \; displaystyle\; k\}$-независимо, если для любого $k\; \{\backslash \; displaystyle\; k\}$отдельные ключи $(x\; 1,\dots ,\; xk)\; \in \; U\; k\; \{\backslash \; displaystyle\; (x\_\; \{1\},\; \backslash \; dots,\; x\_\; \{k\})\; \backslash \; in\; U\; ^\; \{k\}\}$и любые хэш-коды $k\; \{\backslash \; displaystyle\; k\}$(не обязательно отдельные) $(y\; 1,\dots ,\; yk)\; \in \; [m]\; k\; \{\backslash \; displaystyle\; (y\_\; \{1\},\; \backslash \; dots,\; y\_\; \{k\})\; \backslash \; in\; [m]\; ^\; \{k\}\}$, мы имеем:

$Pr\; h\; \in \; H\; [час\; (x\; 1)\; =\; y\; 1\; \wedge \; \cdots \; \wedge \; час\; (xk)\; =\; yk]\; =\; m\; -\; k\; \{\backslash \; displaystyle\; \backslash \; Pr\; \_\; \{h\; \backslash \; in\; H\}\; \backslash \; left\; [h\; (\; x\_\; \{1\})\; =\; y\_\; \{1\}\; \backslash \; land\; \backslash \; cdots\; \backslash \; land\; h\; (x\_\; \{k\})\; =\; y\_\; \{k\}\; \backslash \; right]\; =\; m\; ^\; \{-\; k\}\}$

Это определение эквивалентно следующим двум условия:

1. для любого фиксированного $x\; \in \; U\; \{\backslash \; displaystyle\; x\; \backslash \; in\; U\}$, поскольку $h\; \{\backslash \; displaystyle\; h\}$выбирается случайным образом из $H\; \{\backslash \; displaystyle\; H\}$, $h\; (x)\; \{\backslash \; displaystyle\; h\; (x)\}$равномерно распределен в $[m]\; \{\backslash \; displaystyle\; [m]\}$.
2. для любые фиксированные отдельные ключи $x\; 1,\dots ,\; xk\; \in \; U\; \{\backslash \; displaysty\; le\; x\_\; \{1\},\; \backslash \; dots,\; x\_\; \{k\}\; \backslash \; in\; U\}$, поскольку $h\; \{\backslash \; displaystyle\; h\}$извлекается случайным образом из $H\; \{\backslash \; displaystyle\; H\}$, $h\; (x\; 1),\dots ,\; h\; (xk)\; \{\backslash \; displaystyle\; h\; (x\_\; \{1\}),\; \backslash \; dots,\; h\; (x\_\; \{k\})\}$- независимые случайные величины.

Часто бывает неудобно достичь идеальной совместной вероятности $m\; -\; k\; \{\backslash \; displaystyle\; m\; ^\; \{-\; k\}\}$из-за проблем с округлением. Далее можно определить $(\mu ,\; k)\; \{\backslash \; displaystyle\; (\backslash \; mu,\; k)\}$-независимое семейство, чтобы удовлетворить:

$\forall \; \{\backslash \; displaystyle\; \backslash \; forall\}$различные $(x\; 1,\dots ,\; xk)\; \in \; U\; k\; \{\backslash \; displaystyle\; (x\_\; \{1\},\; \backslash \; dots,\; x\_\; \{k\})\; \backslash \; in\; U\; ^\; \{k\}\}$и $\forall \; (y\; 1,\dots ,\; yk)\; \in \; [м]\; к\; \{\backslash \; displaystyle\; \backslash \; forall\; (y\_\; \{1\},\; \backslash \; dots,\; y\_\; \{k\})\; \backslash \; in\; [m]\; ^\; \{k\}\}$, $Pr\; h\; \in \; ЧАС\; [час\; (Икс\; 1)\; знак\; равно\; Y\; 1\; \wedge \; \cdots \; \wedge \; час\; (xk)\; =\; yk]\; \le \; \mu \; /\; mk\; \{\backslash \; displaystyle\; ~~\; \backslash \; Pr\; \_\; \{h\; \backslash \; in\; H\}\; \backslash \; left\; [h\; (x\_\; \{1\})\; =\; y\_\; \{1\}\; \backslash \; land\; \backslash \; cdots\; \backslash \; land\; h\; (x\_\; \{k\})\; =\; y\_\; \{k\}\; \backslash \; right]\; \backslash \; leq\; \backslash \; mu\; /\; m\; ^\; \{k\}\}$

Обратите внимание на это, даже если $\mu \; \{\backslash \; displaystyle\; \backslash \; mu\}$близко к 1, $h\; (xi)\; \{\backslash \; displaystyle\; h\; (x\_\; \{i\})\}$больше не являются независимыми случайными величинами, которые часто являются проблема анализа рандомизированных алгоритмов. Следовательно, более распространенной альтернативой решению проблем округления является доказательство того, что семейство хешей близко на статистическом расстоянии к $k\; \{\backslash \; displaystyle\; k\}$-независимому семейству, который позволяет черным ящиком использовать свойства независимости.

Полиномы со случайными коэффициентами

Первоначальный метод построения k-независимых хеш-функций, предложенный Картером и Вегманом, заключался в выборе большого простого числа p, выборе k случайных чисел по модулю p, и использовать эти числа как коэффициенты полинома степени k - 1, значения которого по модулю p используются в качестве значения хеш-функции. Все полиномы заданной степени по модулю p равновероятны, и любой многочлен однозначно определяется любым набором пар аргумент-значение с различными аргументами, из чего следует, что любой набор из k различных аргументов с одинаковой вероятностью будет отображен к любому k-кортежу хеш-значений.

Хеширование табуляции

Хеширование табуляции - это метод сопоставления ключей с хеш-значениями путем разделения каждого ключа на байты с использованием каждого байта в качестве индекса в таблицу случайных чисел (с другой таблицей для каждой позиции байта) и объединение результатов этих поисков в таблице с помощью побитовой операции исключающее или. Таким образом, он требует большей случайности при инициализации, чем полиномиальный метод, но позволяет избежать, возможно, медленных операций умножения. Он 3-независимый, но не 4-независимый. Варианты хеширования табуляции позволяют достичь более высокой степени независимости, выполняя поиск в таблице на основе перекрывающихся комбинаций битов входного ключа или итеративно применяя простое хеширование табуляции.

Понятие k-независимости можно использовать для различения различных методов хеширования в соответствии с уровнем независимости, необходимым для обеспечения постоянного ожидаемого времени на операцию.

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

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

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

• Мотвани, Раджив; Рагхаван, Прабхакар (1995). Рандомизированные алгоритмы. Издательство Кембриджского университета. п. 221. ISBN 978-0-521-47465-8.