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

Семейство хэш-функций

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

Фон

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

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

Определения

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

${\displaystyle \Pr _{h\in H}\left[h(x_{1})=y_{1}\land \cdots \land h(x_{k})=y_{k}\right]=m^{-k}}$

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

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

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

${\displaystyle \forall }$отчетливый и , ${\displaystyle (x_{1},\dots ,x_{k})\in U^{k}}$ ${\displaystyle \forall (y_{1},\dots ,y_{k})\in [m]^{k}}$ ${\displaystyle ~~\Pr _{h\in H}\left[h(x_{1})=y_{1}\land \cdots \land h(x_{k})=y_{k}\right]\leq \mu /m^{k}}$

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

Методы

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

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

В общем случае многочлен может быть оценен в любом конечном поле . Помимо полей по модулю простого числа, популярным выбором является поле размера , которое поддерживает быструю конечную полевую арифметику на современных компьютерах. Такой подход использовали Дэниел Лемир и Оуэн Касер для CLHash. ^[4] ${\displaystyle 2^{n}}$

Табулирование хеширования

Табуляция хеширования — это метод сопоставления ключей с хэш-значениями путем разбиения каждого ключа на байты , использования каждого байта в качестве индекса в таблице случайных чисел (с другой таблицей для каждой позиции байта) и объединения результатов этих табличных поисков с помощью побитовой операции исключающего или . Таким образом, он требует большей случайности при своей инициализации, чем полиномиальный метод, но избегает возможно медленных операций умножения. Он является 3-независимым, но не 4-независимым. ^[5] Разновидности табуляции хеширования могут достигать более высоких степеней независимости, выполняя табличные поиски на основе перекрывающихся комбинаций битов из входного ключа или применяя простое табуляционное хеширование итеративно. ^{[6] [7]}

Независимость, необходимая для различных типов разрешения коллизий

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

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

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

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

Для хеширования Cuckoo требуемая k-независимость неизвестна по состоянию на 2021 год. В 2009 году было показано ^[11] , что достаточно -независимости, и требуется как минимум 6-независимость . Другой подход заключается в использовании хеширования Tabulation , которое не является 6-независимым, но, как было показано в 2012 году ^[12] , имеет другие свойства, достаточные для хеширования Cuckoo. Третий подход с 2014 года ^[13] заключается в небольшой модификации хеш-таблицы cuckoo с так называемым stash, что позволяет использовать не более 2-независимых хеш-функций. ${\displaystyle O(\log n)}$

Другие приложения

Кейн , Нельсон и Дэвид Вудрафф улучшили алгоритм Флажоле–Мартина для задачи об отдельных элементах в 2010 году. ^[14] Чтобы дать приближение к правильному ответу, им нужна -независимая хеш-функция. ${\displaystyle \varepsilon }$ ${\displaystyle {\tfrac {\log 1/\varepsilon }{\log \log 1/\varepsilon }}}$

Алгоритм Count Sketch для снижения размерности требует двух хеш-функций: одну 2-независимую и одну 4-независимую .

Алгоритм Карлоффа–Цвика для задачи MAX-3SAT может быть реализован с тремя независимыми случайными величинами.

Алгоритм MinHash может быть реализован с использованием -независимой хеш-функции, как это доказал Петр Индик в 1999 году ^[15] ${\displaystyle \log {\tfrac {1}{\epsilon }}}$

Ссылки

1. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4.
2. Wegman, Mark N. ; Carter, J. Lawrence (1981). "New hash functions and their use in authentication and set equal" (PDF) . Journal of Computer and System Sciences . 22 (3): 265–279. doi : 10.1016/0022-0000(81)90033-7 . Версия конференции в FOCS'79 . Получено 9 февраля 2011 г. .
3. Siegel, Alan (2004). «Об универсальных классах чрезвычайно случайных хэш-функций с постоянным временем и их компромиссе между временем и пространством» (PDF) . SIAM Journal on Computing . 33 (3): 505–543. doi :10.1137/S0097539701386216. Версия конференции в FOCS'89.
4. Лемир, Дэниел и Оуэн Кейзер. «Более быстрое 64-битное универсальное хеширование с использованием умножений без переноса». Журнал криптографической инженерии 6.3 (2016): 171-185.
5. Пэтрашку, Михай ; Торуп, Миккель (2012), «Мощь простого табуляционного хеширования», Журнал ACM , 59 (3): Статья 14, arXiv : 1011.5200 , doi : 10.1145/2220357.2220361, MR  2946218
6. Siegel, Alan (2004), «Об универсальных классах чрезвычайно случайных хэш-функций постоянного времени» (PDF) , SIAM Journal on Computing , 33 (3): 505–543, doi :10.1137/S0097539701386216, MR  2066640, S2CID  1742179, заархивировано из оригинала (PDF) 2019-02-17
7. Торуп, М. (2013), «Простая табуляция, быстрые расширители, двойная табуляция и высокая независимость», Труды 54-го ежегодного симпозиума IEEE по основам компьютерной науки (FOCS 2013) , стр. 90–99, arXiv : 1311.3121 , doi : 10.1109/FOCS.2013.18, ISBN 978-0-7695-5135-7, МР  3246210
8. Брэдфорд, Филлип Г.; Катехакис, Майкл Н. (2007), «Вероятностное исследование комбинаторных расширителей и хеширования» (PDF) , SIAM Journal on Computing , 37 (1): 83–111, doi :10.1137/S009753970444630X, MR  2306284, заархивировано из оригинала (PDF) 25.01.2016 , извлечено 19.01.2016
9. Паг, Анна; Паг, Расмус ; Ружич, Милан (2009), «Линейное зондирование с постоянной независимостью», SIAM Journal on Computing , 39 (3): 1107–1120, arXiv : cs/0612055 , doi :10.1137/070702278, MR  2538852
10. Pătraşcu, Mihai ; Thorup, Mikkel (2010), "On the k-independence required by linear probeing and minwise independent" (PDF) , Automata, Languages ​​and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I , Lecture Notes in Computer Science , vol. 6198, Springer, pp. 715–726, arXiv : 1302.5127 , doi :10.1007/978-3-642-14165-2_60, ISBN 978-3-642-14164-5
11. Коэн, Джеффри С. и Дэниел М. Кейн. «Границы независимости, необходимые для хеширования кукушки». Труды ACM по алгоритмам (2009).
12. Патрашку, Михай и Миккель Торуп. «Мощь простого табуляционного хеширования». Журнал ACM (JACM) 59.3 (2012): 1-50.
13. Аумюллер, Мартин, Мартин Дицфельбингер и Филипп Вёльфель. «Явные и эффективные семейства хэшей достаточны для хэширования кукушки с помощью тайника». Algorithmica 70.3 (2014): 428-456.
14. Кейн, Дэниел М., Джелани Нельсон и Дэвид П. Вудрафф. «Оптимальный алгоритм для проблемы отдельных элементов». Труды двадцать девятого симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных. 2010.
15. Индик, Петр. «Небольшое приблизительно минимально независимое семейство хэш-функций». Журнал алгоритмов 38.1 (2001): 84-90.

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

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