Универсальное хеширование - Википедия - Universal hashing

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

Вступление

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

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

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

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

, когда выбирается случайным образом из семьи , разница равномерно распределен в .

Обратите внимание, что определение универсальности касается только того, , который считает столкновения. Свойство равномерной разницы сильнее.

(Точно так же универсальное семейство может быть универсальным XOR, если , Значение равномерно распределен в куда - побитовая операция исключающее ИЛИ. Это возможно только если это степень двойки.)

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

Еще одно свойство - однородность. Мы говорим, что семья однородна, если все хеш-значения одинаково вероятны: для любого значения хеш-функции . Универсальность не означает единообразия. Однако сильная универсальность предполагает единообразие.

Учитывая семейство со свойством равномерного расстояния, можно создать попарно независимое или строго универсальное хеш-семейство, добавив равномерно распределенную случайную константу со значениями в к хеш-функциям. (Аналогично, если является степенью двойки, мы можем добиться попарной независимости от универсального семейства хеш-кодов XOR, выполнив исключающую или с равномерно распределенной случайной константой.) Поскольку сдвиг на константу иногда не имеет значения в приложениях (например, в хеш-таблицах), тщательное различие между свойством равномерного расстояния и попарно независимым иногда не делается.[3]

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

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

Некоторые реализации хеш-таблиц основаны на универсальном хешировании. В таких приложениях обычно программное обеспечение выбирает новую хеш-функцию только после того, как замечает, что "слишком много" ключей столкнулись; до тех пор одна и та же хеш-функция продолжает использоваться снова и снова (некоторые схемы разрешения конфликтов, такие как динамическое идеальное хеширование, выбирайте новую хеш-функцию каждый раз, когда возникает конфликт. Другие схемы разрешения коллизий, такие как кукушка и Хеширование с двумя вариантами, разрешите несколько коллизий перед выбором новой хеш-функции). Обзор самых быстрых известных универсальных и сильно универсальных хеш-функций для целых чисел, векторов и строк можно найти в.[6]

Математические гарантии

Для любого фиксированного набора из ключи, использование универсального семейства гарантирует следующие свойства.

  1. Для любых фиксированных в , ожидаемое количество ключей в корзине является . При реализации хеш-таблиц цепочка, это число пропорционально ожидаемому времени выполнения операции с ключом (например, запрос, вставка или удаление).
  2. Ожидаемое количество пар ключей в с которые сталкиваются () ограничена сверху величиной , что в порядке . Когда количество ящиков, выбирается линейно по (т.е. определяется функцией в ) ожидаемое количество столкновений равно . При хешировании в бункеры, коллизий вообще нет с вероятностью не меньше половины.
  3. Ожидаемое количество ключей в ящиках не менее ключей в них ограничено сверху .[7] Таким образом, если емкость каждого бункера ограничена до трехкратного среднего размера () общее количество ключей в переполненных ячейках не превышает . Это справедливо только для хеш-семейства, вероятность столкновения которого ограничена сверху величиной . Если используется более слабое определение, ограничивая его , этот результат больше не соответствует действительности.[7]

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

Вторая и третья гарантия обычно используются вместе с перефразирование. Например, может быть подготовлен рандомизированный алгоритм для обработки некоторых количество столкновений. Если он наблюдает слишком много столкновений, он выбирает другое случайное из семьи и повторяется. Универсальность гарантирует, что количество повторений будет геометрическая случайная величина.

Конструкции

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

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

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

Оригинальное предложение Картера и Вегмана[1] было выбрать прайм и определить

куда случайно выбранные целые числа по модулю с . (Это единственная итерация линейный конгруэнтный генератор.)

Чтобы увидеть это универсальная семья, обратите внимание, что только когда

для некоторого целого числа между и . Если , их отличие, отличен от нуля и имеет обратный по модулю . Решение для дает

.

Есть возможные варианты для (поскольку исключено) и, варьируя в допустимом диапазоне, возможные ненулевые значения для правой части. Таким образом, вероятность столкновения равна

.

Другой способ увидеть универсальное семейство через понятие статистическое расстояние. Напишите разницу в качестве

.

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

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

только примерно универсальный: для всех .[1] Более того, этот анализ почти точен; Картер и Вегман [1] покажи это в любое время .

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

Современное состояние хеширования целых чисел - многократно-сдвиг схема, описанная Dietzfelbinger et al. в 1997 г.[8] Избегая модульной арифметики, этот метод намного проще реализовать, а на практике он работает значительно быстрее (обычно как минимум в четыре раза).[9]). Схема предполагает, что количество ящиков является степенью двойки, . Позволять быть количеством бит в машинном слове. Затем хеш-функции параметризуются над нечетными положительными целыми числами. (это вписывается в слово биты). Оценить , умножить к по модулю а затем сохраните высокий порядок биты как хэш-код. В математической записи это

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

(size_t) (a * x) >> (ш-м)

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

Чтобы понять поведение хэш-функции, обратите внимание, что если и имеют те же самые старшие биты M, тогда имеет либо все единицы, либо все нули в качестве своих M бит наивысшего порядка (в зависимости от того, или же больше). Предположим, что младший бит набора появляется на позиции . С является случайным нечетным целым числом, а нечетные целые имеют обратные звенеть , следует, что будут равномерно распределены среди -битовые целые числа с младшим битом установленной позиции . Вероятность того, что все эти биты - это все 0 или все 1, поэтому не превышает .С другой стороны, если , то старшие M битов содержат как 0, так и 1, поэтому очевидно, что . Наконец, если затем укусил из равно 1 и если и только если биты также равны 1, что с вероятностью .

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

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

(size_t) (a * x + b) >> (ш-М)

куда является случайным нечетным положительным целым числом с и является случайным неотрицательным целым числом с . С этим выбором и , для всех .[10] Это немного отличается, но существенно от неправильного перевода в английской газете.[11]

Хеширование векторов

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

, где каждый выбирается независимо случайно.

Если является степенью двойки, можно заменить суммирование исключающим или.[12]

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

.

Число умножений можно уменьшить вдвое, что на практике дает примерно двукратное ускорение.[12] Инициализируйте хеш-функцию вектором случайных странный целые числа на бит каждый. Следующее семейство хешей является универсальным:[14]

.

Если операции с двойной точностью недоступны, можно интерпретировать ввод как вектор полуслов (-битовые целые числа). Затем алгоритм будет использовать умножения, где число полуслов в векторе. Таким образом, алгоритм работает со «скоростью» одно умножение на слово ввода.

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

Также возможна сильная универсальность на высокой скорости.[16] Инициализируйте хеш-функцию вектором случайных целых чисел на биты. Вычислить

.

Результат универсален на биты. Экспериментально было обнаружено, что он работает при 0,2 цикла ЦП на байт на последних процессорах Intel для .

Хеширование строк

Это относится к хешированию переменный размер вектор машинных слов. Если длина строки может быть ограничена небольшим числом, лучше всего использовать векторное решение сверху (концептуально дополняя вектор нулями до верхней границы). Требуемое пространство - это максимальная длина строки, но время для оценки это просто длина . Пока в строке запрещены нули, заполнение нулями можно игнорировать при оценке хэш-функции, не влияя на универсальность.[12] Обратите внимание: если в строке разрешены нули, то, возможно, лучше всего добавить фиктивный ненулевой символ (например, 1) ко всем строкам перед заполнением: это гарантирует, что универсальность не будет затронута.[16]

Теперь предположим, что мы хотим хешировать , где хорошая граница не известно априори. Универсальная семья, предложенная [13] лечит строку как коэффициенты многочлена по модулю большого простого числа. Если , позволять быть простым и определить:

, куда равномерно случайный и выбирается случайным образом из универсальной целочисленной области отображения семейства .

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

uint хэш(Нить Икс, int а, int п)	uint час = ПЕРВОНАЧАЛЬНЫЙ ЗНАЧЕНИЕ	за (uint я=0 ; я < Икс.длина ; ++я)		час = ((час*а) + Икс[я]) мод п	возвращаться час

Этот Катящийся хеш Рабина-Карпа основан на линейный конгруэнтный генератор.[18]Вышеупомянутый алгоритм также известен как Мультипликативная хеш-функция.[19] На практике мод оператор и параметр п можно полностью избежать, просто допустив переполнение целого числа, потому что это эквивалентно мод (Максимальное значение Int + 1) на многих языках программирования. В таблице ниже показаны значения, выбранные для инициализации. час и для некоторых популярных реализаций.

ВыполнениеПЕРВОНАЧАЛЬНЫЙ ЗНАЧЕНИЕа
Бернштейн хеш-функция djb2[20]538133
STLPort 4.6.205
Керниган и Ричи хеш-функция[21]031
java.lang.String.hashCode ()[22]031

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

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

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

Чтобы уменьшить вычислительные затраты модульной арифметики, на практике используются три приема:[12]

  1. Один выбирает премьер быть близким к степени двойки, например Мерсенн прайм. Это позволяет выполнять арифметические операции по модулю быть реализовано без деления (с использованием более быстрых операций, таких как сложение и сдвиги). Например, на современных архитектурах можно работать с , пока - 32-битные значения.
  2. К блокам можно применить векторное хеширование. Например, к каждому блоку из 16 слов строки применяется векторное хеширование, а к полученные результаты. Поскольку более медленное хеширование строки применяется к значительно меньшему вектору, это будет по существу так же быстро, как и хеширование вектора.
  3. В качестве делителя выбирается степень двойки, что позволяет выполнять арифметические операции по модулю быть реализовано без разделения (с использованием более быстрых операций битовая маскировка ). В Семейство хэш-функций NH использует этот подход.

Смотрите также

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

  1. ^ а б c d е Картер, Ларри; Вегман, Марк Н. (1979). «Универсальные классы хэш-функций». Журнал компьютерных и системных наук. 18 (2): 143–154. Дои: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.p. 10.
  6. ^ Торуп, Миккель (2015). «Высокоскоростное хеширование для целых чисел и строк». arXiv:1504.06804 [cs.DS ].
  7. ^ а б Баран, Илья; Demaine, Erik D .; Пэтрашку, Михай (2008). «Субквадратные алгоритмы для 3SUM» (PDF). Алгоритмика. 50 (4): 584–596. Дои:10.1007 / s00453-007-9036-3.
  8. ^ Дицфельбингер, Мартин; Хагеруп, Торбен; Катаянен, Юрки; Пенттонен, Марти (1997). «Надежный рандомизированный алгоритм для задачи ближайшей пары» (Постскриптум). Журнал алгоритмов. 25 (1): 19–51. Дои:10.1006 / jagm.1997.0873. Получено 10 февраля 2011.
  9. ^ Торуп, Миккель. «Учебник алгоритмов в SODA».
  10. ^ Вельфель, Филипп (2003). Über die Komplexität der Multiplikation in eingeschränkten Branchingprogrammmodellen (PDF) (Кандидат наук.). Universität Dortmund. Получено 18 сентября 2012.
  11. ^ Вельфель, Филипп (1999). Эффективное строго универсальное и оптимально универсальное хеширование. Математические основы информатики 1999. LNCS. 1672. С. 262–272. Дои:10.1007/3-540-48340-3_24.
  12. ^ а б c d Торуп, Миккель (2009). Хеширование строк для линейного зондирования. Proc. 20-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA). С. 655–664. CiteSeerX  10.1.1.215.4253. Дои:10.1137/1.9781611973068.72., раздел 5.3
  13. ^ а б Дицфельбингер, Мартин; Гил, Джозеф; Матиас, Йосси; Пиппенгер, Николас (1992). Полиномиальные хеш-функции надежны (расширенная аннотация). Proc. 19-й Международный коллоквиум по автоматам, языкам и программированию (ICALP). С. 235–246.
  14. ^ Black, J .; Halevi, S .; Krawczyk, H .; Кровец, Т. (1999). UMAC: быстрая и безопасная проверка подлинности сообщений (PDF). Достижения в криптологии (CRYPTO '99)., Уравнение 1
  15. ^ Пэтрашку, Михай; Торуп, Миккель (2011). Возможности простого хеширования таблиц. Материалы 43-го ежегодного симпозиума ACM по теории вычислений (STOC '11). С. 1–10. arXiv:1011.5200. Дои:10.1145/1993636.1993638.
  16. ^ а б Касер, Оуэн; Лемир, Даниэль (2013). «Сильно универсальное хеширование строк выполняется быстро». Компьютерный журнал. Издательство Оксфордского университета. 57 (11): 1624–1638. arXiv:1202.4961. Дои:10.1093 / comjnl / bxt070.
  17. ^ "Слайды курса еврейского университета" (PDF).
  18. ^ Роберт Узгалис.«Библиотека хэш-функций».1996.
  19. ^ Канковск, Питер. «Хеш-функции: эмпирическое сравнение».
  20. ^ Йигит, Озан. «Строковые хеш-функции».
  21. ^ Керниган; Ричи (1988). «6». Язык программирования C (2-е изд.). стр.118. ISBN  0-13-110362-8.CS1 maint: несколько имен: список авторов (связь)
  22. ^ «Строка (Java Platform SE 6)». docs.oracle.com. Получено 2015-06-10.

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

внешняя ссылка