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

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

Фон

Смотрите также: Хеш-функция

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

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

Часто бывает неудобно достичь идеальной совместной вероятности ${\displaystyle m^{-k}}$ из-за проблем с округлением. Следующий,^[3] можно определить ${\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}}$

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

Методы

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

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

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

Основная статья: Хеширование табуляции

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

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

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

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

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

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

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

1. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN  0-262-03384-4.
2. Вегман, Марк Н.; Картер, Дж. Лоуренс (1981). «Новые хеш-функции и их использование при аутентификации и установлении равенства» (PDF). Журнал компьютерных и системных наук. 22 (3): 265–279. Дои:10.1016/0022-0000(81)90033-7. Версия конференции в FOCS'79. Получено 9 февраля 2011.
3. Сигел, Алан (2004). «Об универсальных классах чрезвычайно случайных хэш-функций с постоянным временем и их компромиссе во времени и пространстве» (PDF). SIAM Журнал по вычислениям. 33 (3): 505–543. Дои:10.1137 / S0097539701386216. Версия конференции в FOCS'89.
4. Пэтрашку, Михай; Торуп, Миккель (2012), «Сила простого хеширования таблиц», Журнал ACM, 59 (3): Ст. 14, arXiv:1011.5200, Дои:10.1145/2220357.2220361, МИСТЕР  2946218.
5. Сигел, Алан (2004), "Об универсальных классах чрезвычайно случайных хэш-функций с постоянным временем", SIAM Журнал по вычислениям, 33 (3): 505–543, Дои:10.1137 / S0097539701386216, МИСТЕР  2066640.
6. Торуп, М. (2013), «Простое табулирование, быстрое расширение, двойное табулирование и высокая независимость», Материалы 54-го ежегодного симпозиума IEEE по основам информатики (FOCS 2013), стр. 90–99, arXiv:1311.3121, Дои:10.1109 / FOCS.2013.18, ISBN  978-0-7695-5135-7, МИСТЕР  3246210.
7. Брэдфорд, Филип Дж .; Катехакис, Майкл Н. (2007), «Вероятностное исследование комбинаторных расширителей и хеширования» (PDF), SIAM Журнал по вычислениям, 37 (1): 83–111, Дои:10.1137 / S009753970444630X, МИСТЕР  2306284, заархивировано из оригинал (PDF) на 2016-01-25, получено 2016-01-19.
8. Паг, Анна; Паг, Расмус; Ружич, Милан (2009), «Линейное зондирование с постоянной независимостью», SIAM Журнал по вычислениям, 39 (3): 1107–1120, arXiv:cs / 0612055, Дои:10.1137/070702278, МИСТЕР  2538852
9. Пэтрашку, Михай; Торуп, Миккель (2010), "На k-независимость, требуемая линейным зондированием и минимальной независимостью » (PDF), Автоматы, языки и программирование, 37-й международный коллоквиум, ICALP 2010, Бордо, Франция, 6-10 июля 2010 г., Материалы, часть I, Конспект лекций по информатике, 6198, Springer, стр. 715–726, arXiv:1302.5127, Дои:10.1007/978-3-642-14165-2_60, ISBN  978-3-642-14164-5

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

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