В математике и вычислительной , универсальное хеширование (в рандомизированном алгоритме или структуре данных) относится к выбору хэш - функцию случайным образом из семейства хэш - функций с определенным математическим свойством (см определение ниже). Это гарантирует малое количество ожидаемых столкновений , даже если данные выбираются злоумышленником. Известно много универсальных семейств (для хеширования целых чисел, векторов, строк), и их вычисление часто бывает очень эффективным. Универсальное хеширование имеет множество применений в информатике, например, при реализации хеш-таблиц , рандомизированных алгоритмов и криптографии .
Введение [ править ]
Предположим, мы хотим отобразить ключи из некоторой вселенной в ячейки (помечены ). Алгоритму придется обрабатывать некоторый набор данных ключей, о котором заранее не известно. Обычно целью хеширования является получение небольшого количества коллизий (ключей из этой области в одном и том же бункере). Детерминированная хеш-функция не может предложить никаких гарантий в состязательной настройке, если размер больше, чем , поскольку злоумышленник может выбрать именно прообраз корзины. Это означает, что все ключи данных попадают в одну корзину, что делает хеширование бесполезным. Кроме того, детерминированная хеш-функция не позволяет перехешировать: иногда входные данные оказываются плохими для хеш-функции (например, слишком много коллизий), поэтому хочется изменить хеш-функцию.
Решение этих проблем состоит в том, чтобы случайным образом выбрать функцию из семейства хеш-функций. Семейство функций называется универсальным семейством, если ,.
Другими словами, любые два ключа вселенной сталкиваются с максимальной вероятностью, когда хеш-функция извлекается случайным образом из . Это именно та вероятность коллизии, которую мы ожидали бы, если бы хеш-функция назначила действительно случайные хэш-коды каждому ключу. Иногда определение смягчается, чтобы учесть вероятность столкновения . Эта концепция была введена Картером и Вегманом [1] в 1977 году и нашла многочисленные применения в информатике (см., Например, [2] ). Если у нас есть верхняя граница вероятности столкновения, мы говорим, что имеем почти универсальность.
Многие, но не все универсальные семейства обладают следующим более сильным свойством равномерной разности :
- , когда случайным образом выбирается из семейства , разница равномерно распределяется в .
Обратите внимание, что определение универсальности касается только того , учитываются ли столкновения. Свойство равномерной разницы сильнее.
(Точно так же универсальное семейство может быть универсальным XOR, если значение равномерно распределено, где - побитовая операция исключающая или. Это возможно только в случае степени двойки.)
Еще более сильное условие попарно независимость : у нас есть это свойство , когда у нас есть вероятность того, что будет хэш любой пары значений хеш - функции , как если бы они были совершенно случайным образом : . Попарную независимость иногда называют сильной универсальностью.
Еще одно свойство - однородность. Мы говорим, что семейство единообразно, если все значения хеш-функции одинаково вероятны: для любого значения хеш-функции . Универсальность не означает единообразия. Однако сильная универсальность предполагает единообразие.
Учитывая семейство со свойством равномерного расстояния, можно создать попарно независимое или строго универсальное хэш-семейство, добавив равномерно распределенную случайную константу со значениями в хеш-функции. (Точно так же, если это степень двойки, мы можем добиться попарной независимости от универсального семейства хешей XOR, выполнив исключающую или с равномерно распределенной случайной константой.) Поскольку сдвиг на константу иногда не имеет значения в приложениях (например, в хеш-таблицах) , иногда не делается тщательного различия между свойством равномерного расстояния и попарно независимым. [3]
Для некоторых приложений (например, хеш-таблиц) важно, чтобы наименее значимые биты хеш-значений также были универсальными. Когда семейство строго универсально, это гарантируется: если это строго универсальное семейство с , то семейство, состоящее из функций для всех , также является строго универсальным для . К сожалению, этого нельзя сказать о (просто) универсальных семьях. Например, семейство, состоящее из функции идентичности, явно универсально, но семейство, состоящее из функции, не может быть универсальным.
UMAC и Poly1305-AES, а также несколько других алгоритмов кода аутентификации сообщений основаны на универсальном хешировании. [4] [5] В таких приложениях программное обеспечение выбирает новую хеш-функцию для каждого сообщения на основе уникального одноразового номера для этого сообщения.
Несколько реализаций хэш-таблиц основаны на универсальном хешировании. В таких приложениях, как правило, программное обеспечение выбирает новую хеш-функцию только после того, как замечает, что «слишком много» ключей столкнулись; до тех пор одна и та же хеш-функция продолжает использоваться снова и снова. (Некоторые схемы разрешения коллизий, такие как динамическое идеальное хеширование , выбирают новую хэш-функцию каждый раз, когда есть коллизия. Другие схемы разрешения коллизий, такие как хеширование с кукушкой и хеширование с двумя вариантами , допускают некоторое количество коллизий перед выбором новой хеш-функции. ). Обзор самых быстрых известных универсальных и сильно универсальных хэш-функций для целых чисел, векторов и строк можно найти в [6].
Математические гарантии [ править ]
Для любого фиксированного набора из ключей, используя универсальное семейство гарантирует следующие свойства.
- Для любого фиксированного в , ожидаемое количество ключей в бункере есть . При реализации хэш-таблиц путем объединения это число пропорционально ожидаемому времени выполнения операции, связанной с ключом (например, запроса, вставки или удаления).
- Ожидаемое число пар ключей в с , сталкивающимся ( ) ограниченно сверху , которая имеет порядок . Когда количество бинов выбирается линейным по (т. Е. Определяется функцией в ), ожидаемое количество столкновений равно . При хешировании в бины вообще нет коллизий с вероятностью не менее половины.
- Ожидаемое количество ключей в ящиках с как минимум ключами в них ограничено сверху значением . [7] Таким образом, если емкость каждого бункера ограничена трехкратным средним размером ( ), общее количество ключей в переполненных бункерах не превышает максимального . Это справедливо только для семейства хешей, вероятность столкновения которого ограничена сверху значением . Если используется более слабое определение, ограничивающее его , этот результат перестает быть верным. [7]
Поскольку приведенные выше гарантии действуют для любого фиксированного набора , они остаются в силе, если набор данных выбран противником. Однако злоумышленник должен сделать этот выбор до (или независимо от) случайного выбора алгоритмом хэш-функции. Если злоумышленник может наблюдать случайный выбор алгоритма, случайность не имеет смысла, и ситуация аналогична детерминированному хешированию.
Вторая и третья гарантии обычно используются вместе с повторным хешированием . Например, может быть подготовлен рандомизированный алгоритм для обработки некоторого количества коллизий. Если он наблюдает слишком много столкновений, он выбирает другое случайное число из семейства и повторяет. Универсальность гарантирует, что количество повторений является геометрической случайной величиной .
Конструкции [ править ]
Поскольку любые компьютерные данные могут быть представлены как одно или несколько машинных слов, обычно требуются хэш-функции для трех типов доменов: машинные слова («целые числа»); векторы машинных слов фиксированной длины; и векторы переменной длины («строки»).
Хеширование целых чисел [ править ]
Этот раздел относится к случаю хеширования целых чисел, которые помещаются в машинные слова; таким образом, такие операции, как умножение, сложение, деление и т. д., являются дешевыми инструкциями машинного уровня. Пусть будет хэширована вселенная .
Первоначальное предложение Картера и Вегмана [1] заключалось в том, чтобы выбрать простое число и определить
где - случайно выбранные целые числа по модулю с . (Это единственная итерация линейного конгруэнтного генератора .)
Чтобы увидеть, что это универсальное семейство, обратите внимание, что это справедливо только тогда, когда
для некоторого целого числа между и . Если их разность отлична от нуля и имеет обратный модуль . Решение для урожайности
- .
Есть возможные варианты для (так как исключается) и, варьируя в допустимом диапазоне, возможные ненулевые значения с правой стороны. Таким образом, вероятность столкновения равна
- .
Еще один способ увидеть универсальную семью - использовать понятие статистического расстояния . Запишите разницу как
- .
Поскольку не равно нулю и равномерно распределен в , отсюда следует, что по модулю также равномерно распределен в . Таким образом, распределение почти равномерное с точностью до разницы в вероятности между выборками. В результате статистическое расстояние до однородного семейства составляет , которым можно пренебречь, когда .
Семейство более простых хеш-функций
только приблизительно универсален: для всех . [1] Более того, этот анализ почти точен; Картер и Вегман [1] показывают это в любое время .
Избегайте модульной арифметики [ править ]
Состояние искусства для хеширования целых чисел является множественно-сдвига схемы описывается Dietzfelbinger и соавт. в 1997 г. [8] За счет отказа от модульной арифметики этот метод намного проще реализовать, а также он работает значительно быстрее на практике (обычно как минимум в четыре раза [9] ). Схема предполагает, что количество ячеек является степенью двойки . Позвольте быть количество бит в машинном слове. Затем хеш-функции параметризуются для нечетных положительных целых чисел (которые умещаются в слове битов). Чтобы оценить , умножьте по модулю, а затем сохраните старшие биты в качестве хэш-кода. В математической записи это
и это может быть реализовано на C- подобных языках программирования с помощью
-
(size_t) (a*x) >> (w-M)
Эта схема не удовлетворяет свойству равномерной разности и является лишь почти универсальной ; для любого , .
Чтобы понять поведение хеш-функции, обратите внимание, что если и имеют одинаковые биты M самого высокого порядка, то в качестве битов M самого высокого порядка используются либо все единицы, либо все 0 (в зависимости от того, больше или больше). Предположим, что в позиции появляется младший бит набора . Поскольку это случайное нечетное целое число, а нечетные целые числа имеют обратные в кольце , из этого следует, что они будут равномерно распределены среди -битовых целых чисел с младшим битом набора на позиции . Таким образом, вероятность того, что все эти биты равны нулю или единице, не превышает максимального значения . С другой стороны, если , то старшие M битов содержат как 0, так и 1, поэтому очевидно, что . Наконец, если затем немного из 1 и тогда и только тогда , когда биты также 1, что происходит с вероятностью .
Этот анализ является точным, что можно показать на примере и . Чтобы получить действительно «универсальную» хеш-функцию, можно использовать схему умножения-сложения-сдвига.
который может быть реализован в C- подобных языках программирования с помощью
-
(size_t) (a*x+b) >> (w-M)
где - случайное нечетное положительное целое с и - случайное неотрицательное целое с . С этими выборами и , для всех . [10] Это немного, но существенно отличается от неправильного перевода в английской статье. [11]
Хеширование векторов [ править ]
В этом разделе рассматривается хеширование вектора машинных слов фиксированной длины. Интерпретируйте вход в качестве вектора из машинных слов (целых чисел из битов каждый). Если это универсальное семейство со свойством равномерной разности, следующее семейство (восходящее к Картеру и Вегману [1] ) также обладает свойством равномерной разности (и, следовательно, является универсальным):
- , где каждый выбирается независимо случайным образом.
Если - степень двойки, можно заменить суммирование исключающим или. [12]
На практике, если доступна арифметика с двойной точностью, она создается с помощью семейства хэш-функций с множественным сдвигом. [13] Инициализировать хеш-функцию вектором случайных нечетных целых чисел по битам в каждом. Тогда, если количество ящиков для :
- .
Число умножений можно уменьшить вдвое, что на практике дает примерно двукратное ускорение. [12] Инициализируйте хеш-функцию вектором случайных нечетных целых чисел по битам в каждом. Следующее семейство хешей является универсальным: [14]
- .
Если операции с двойной точностью недоступны, можно интерпретировать ввод как вектор полуслов ( -битовых целых чисел). Затем алгоритм будет использовать умножение, где было количество полуслов в векторе. Таким образом, алгоритм работает со «скоростью» одно умножение на слово ввода.
Та же самая схема может также использоваться для хеширования целых чисел, интерпретируя их биты как векторы байтов. В этом варианте векторный метод известен как хеширование таблиц и представляет собой практическую альтернативу универсальным схемам хеширования на основе умножения. [15]
Также возможна сильная универсальность на высокой скорости. [16] Инициализировать хеш-функцию вектором случайных целых чисел в битах. Вычислить
- .
Результат универсален для битов. Экспериментально было обнаружено, что он работает при 0,2 цикла ЦП на байт на последних процессорах Intel для .
Хеширование строк [ править ]
Это относится к хешированию вектора машинных слов переменного размера . Если длина строки может быть ограничена небольшим числом, лучше всего использовать векторное решение сверху (концептуально дополняя вектор нулями до верхней границы). Требуемое пространство - это максимальная длина строки, но время для оценки - это всего лишь длина . Пока нули в строке запрещены, заполнение нулями можно игнорировать при оценке хэш-функции, не влияя на универсальность. [12] Обратите внимание, что если в строке разрешены нули, то, возможно, лучше всего добавить фиктивный ненулевой символ (например, 1) ко всем строкам до заполнения: это гарантирует, что универсальность не будет нарушена. [16]
Теперь предположим, что мы хотим хешировать , когда хорошая оценка априори неизвестна. Универсальное семейство, предложенное в [13], рассматривает строку как коэффициенты многочлена по модулю большого простого числа. Если , позвольте быть простым и определить:
- , где равномерно случайна и выбирается случайным образом из целочисленной области универсального отображения семейства .
Используя свойства модульной арифметики, приведенное выше можно вычислить без получения больших чисел для больших строк следующим образом: [17]
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 час
Этот скользящий хеш Рабина-Карпа основан на линейном конгруэнтном генераторе . [18] Вышеупомянутый алгоритм также известен как мультипликативная хеш-функция . [19] На практике оператора mod и параметра p можно полностью избежать, просто разрешив целочисленное переполнение, потому что это эквивалентно mod ( Max-Int-Value + 1) во многих языках программирования. В таблице ниже показаны значения, выбранные для инициализации h и a для некоторых популярных реализаций.
Выполнение | ПЕРВОНАЧАЛЬНЫЙ ЗНАЧЕНИЕ | а |
---|---|---|
Бернштейн хэш - функция «ы djb2 [20] | 5381 | 33 |
STLPort 4.6.2 | 0 | 5 |
Хеш-функция Кернигана и Ричи [21] | 0 | 31 год |
java.lang.String.hashCode() [22] | 0 | 31 год |
Рассмотрим две строки и пусть будет длина более длинной; для анализа более короткая строка концептуально дополняется нулями до длины . Столкновение перед применением означает, что это корень многочлена с коэффициентами . Этот многочлен имеет не больше корней по модулю , поэтому вероятность столкновения не больше . Вероятность столкновения из-за случайности доводит общую вероятность столкновения до . Таким образом, если простое число достаточно велико по сравнению с длиной хешированных строк, семейство очень близко к универсальному (по статистической дистанции ).
Другие универсальные семейства хэш-функций, используемые для хеширования строк неизвестной длины в хеш-значения фиксированной длины, включают отпечаток Рабина и Бужаш .
Избегайте модульной арифметики [ править ]
Чтобы уменьшить вычислительные затраты модульной арифметики, на практике используются три приема: [12]
- Один выбирает простое число, близкое к степени двойки, например простое число Мерсенна . Это позволяет реализовать арифметику по модулю без деления (с использованием более быстрых операций, таких как сложение и сдвиги). Так , например, на современных архитектурах можно работать с , в то время как «s являются 32-разрядными значениями.
- К блокам можно применить векторное хеширование. Например, к каждому блоку из 16 слов строки применяется векторное хеширование, а к результатам применяется хеширование строки . Поскольку более медленное хеширование строки применяется к значительно меньшему вектору, это будет по существу так же быстро, как и хеширование вектора.
- В качестве делителя выбирается степень двойки, что позволяет реализовать арифметику по модулю без деления (с использованием более быстрых операций битовой маскировки ). Этот подход используется в семействе хэш-функций NH .
См. Также [ править ]
- K-независимое хеширование
- Скользящее хеширование
- Хеширование табуляции
- Мудрая независимость
- Универсальная односторонняя хеш-функция
- Последовательность с низким расхождением
- Идеальное хеширование
Ссылки [ править ]
- ^ a b c d e Картер, Ларри; Вегман, Марк Н. (1979). «Универсальные классы хэш-функций». Журнал компьютерных и системных наук . 18 (2): 143–154. DOI : 10.1016 / 0022-0000 (79) 90044-8 . Версия конференции в STOC'77.
- ^ Милтерсен, Питер Бро. «Универсальное хеширование» (PDF) . Архивировано из оригинального (PDF) 24 мая 2011 года . Проверено 24 июня 2009 года .
- ^ Мотвани, Раджив; Рагхаван, Прабхакар (1995). Рандомизированные алгоритмы . Издательство Кембриджского университета. п. 221. ISBN. 0-521-47465-5.
- ^ Дэвид Вагнер, изд. «Достижения в криптологии - CRYPTO 2008» . п. 145.
- ^ Жан-Филипп Аумассон, Вилли Мейер, Рафаэль Фан, Лука Хензен. «Хеш-функция BLAKE» . 2014. с. 10.
- ^ Thorup, Миккель (2015). «Высокоскоростное хеширование для целых чисел и строк». arXiv : 1504.06804 [ cs.DS ].
- ^ а б Баран, Илья; Demaine, Erik D .; Пэтрашку, Михай (2008). «Субквадратные алгоритмы для 3SUM» (PDF) . Алгоритмика . 50 (4): 584–596. DOI : 10.1007 / s00453-007-9036-3 .
- ^ Дицфельбингер, Мартин; Хагеруп, Торбен; Катаянен, Юрки; Пенттонен, Марти (1997). «Надежный рандомизированный алгоритм для задачи ближайшей пары» (Postscript) . Журнал алгоритмов . 25 (1): 19–51. DOI : 10.1006 / jagm.1997.0873 . Проверено 10 февраля 2011 года .
- ^ Thorup, Миккель . «Учебник алгоритмов в SODA» .
- ^ Woelfel, Philipp (2003). Über die Komplexität der Multiplikation in eingeschränkten Branchingprogrammmodellen (PDF) (Ph.D.). Universität Dortmund . Проверено 18 сентября 2012 года .
- ^ Woelfel, Philipp (1999). Эффективное строго универсальное и оптимально универсальное хеширование . Математические основы информатики 1999. LNCS. 1672 . С. 262–272. DOI : 10.1007 / 3-540-48340-3_24 .
- ^ a b c d Thorup, Миккель (2009). Хеширование строк для линейного зондирования . Proc. 20-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA) . С. 655–664. CiteSeerX 10.1.1.215.4253 . DOI : 10.1137 / 1.9781611973068.72 . , раздел 5.3
- ^ a b Дицфельбингер, Мартин; Гил, Джозеф; Матиас, Йосси; Пиппенгер, Николас (1992). Полиномиальные хеш-функции надежны (расширенное резюме) . Proc. 19-й Международный коллоквиум по автоматам, языкам и программированию (ICALP) . С. 235–246.
- ^ Black, J .; Halevi, S .; Krawczyk, H .; Кровец, Т. (1999). UMAC: быстрая и безопасная проверка подлинности сообщений (PDF) . Достижения в криптологии (CRYPTO '99) . , Уравнение 1
- ^ Пэтрашку, Михай ; Торуп, Миккель (2011). Возможности простого хеширования таблиц . Материалы 43-го ежегодного симпозиума ACM по теории вычислений (STOC '11) . С. 1–10. arXiv : 1011.5200 . DOI : 10.1145 / 1993636.1993638 .
- ^ а б Касер, Оуэн; Лемир, Даниэль (2013). «Сильно универсальное хеширование строк выполняется быстро». Компьютерный журнал . Издательство Оксфордского университета. 57 (11): 1624–1638. arXiv : 1202,4961 . DOI : 10.1093 / comjnl / bxt070 .
- ^ "Слайды курса еврейского университета" (PDF) .
- ^ Роберт Uzgalis. «Библиотека хеш-функций» . 1996 г.
- ^ Kankowsk, Питер. «Хеш-функции: эмпирическое сравнение» .
- ^ Йигит, Озан. «Строковые хеш-функции» .
- ^ Керниган; Ричи (1988). «6». Язык программирования C (2-е изд.). С. 118 . ISBN 0-13-110362-8.CS1 maint: multiple names: authors list (link)
- ^ «Строка (Java Platform SE 6)» . docs.oracle.com . Проверено 10 июня 2015 .
Дальнейшее чтение [ править ]
- Кнут, Дональд Эрвин (1998). Искусство программирования, Vol. III: Сортировка и поиск (3-е изд.). Чтение, месса; Лондон: Аддисон-Уэсли. ISBN 0-201-89685-0.
Внешние ссылки [ править ]
- Структуры открытых данных - Раздел 5.1.1 - Мультипликативное хеширование , Пэт Морин