В математике и вычислительной , универсальное хеширование (в рандомизированном алгоритме или структуре данных) относится к выбору хэш - функцию случайным образом из семейства хэш - функций с определенным математическим свойством (см определение ниже). Это гарантирует небольшое количество ожидаемых коллизий , даже если данные выбираются злоумышленником. Известно много универсальных семейств (для хеширования целых чисел, векторов, строк), и их вычисление часто бывает очень эффективным. Универсальное хеширование имеет множество применений в информатике, например, при реализации хеш-таблиц , рандомизированных алгоритмов и криптографии .
Вступление
Предположим, мы хотим сопоставить ключи из какой-то вселенной в ящики (помечены ). Алгоритм должен будет обработать некоторый набор данных. из ключи, о которых заранее не известно. Обычно целью хеширования является получение небольшого количества коллизий (ключей отчто земля в том же мусорном ведре). Детерминированная хеш-функция не может предложить никаких гарантий в состязательной обстановке, если размер больше, чем , поскольку противник может выбрать быть точным прообразом мусорного ведра. Это означает, что все ключи данных попадают в одну и ту же корзину, что делает хеширование бесполезным. Более того, детерминированная хеш-функция не позволяет перехешировать : иногда входные данные оказываются плохими для хеш-функции (например, слишком много коллизий), поэтому хеш-функцию хотелось бы изменить.
Решение этих проблем состоит в том, чтобы случайным образом выбрать функцию из семейства хеш-функций. Семейство функцийназывается универсальной семьей, если,.
Другими словами, любые два ключа Вселенной сталкиваются с вероятностью не более когда хеш-функция выбирается случайным образом из . Это именно та вероятность столкновения, которую мы могли бы ожидать, если бы хеш-функция назначила действительно случайные хэш-коды каждому ключу. Иногда определение смягчается, чтобы допустить вероятность столкновения. Эта концепция была введена Картером и Вегманом [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 самого высокого порядка, тогда имеет либо все единицы, либо все 0 в качестве своих M бит наивысшего порядка (в зависимости от того, или же больше). Предположим, что младший бит набора появляется на позиции . Сявляется случайным нечетным целым числом, а нечетные целые числа имеют обратные в кольце , следует, что будут равномерно распределены среди -битовые целые числа с наименее значимым установленным битом в позиции . Вероятность того, что все эти биты - это все нули или все единицы, поэтому не более. С другой стороны, если, то старшие 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]
- Один выбирает премьер быть близким к степени двойки, такой как простое число Мерсенна . Это позволяет выполнять арифметические операции по модулюбыть реализованным без деления (с использованием более быстрых операций, таких как сложение и сдвиги). Например, на современных архитектурах можно работать с, пока - 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.
- ^ Торуп, Миккель (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, Mikkel . «Учебник алгоритмов в SODA» .
- ^ Вельфель, Филипп (2003). Über die Komplexität der Multiplikation in eingeschränkten Branchingprogrammmodellen (PDF) (Ph.D.). Universität Dortmund . Проверено 18 сентября 2012 года .
- ^ Вельфель, Филипп (1999). Эффективное строго универсальное и оптимально универсальное хеширование . Математические основы информатики 1999. LNCS. 1672 . С. 262–272. DOI : 10.1007 / 3-540-48340-3_24 .
- ^ а б в г Торуп, Миккель (2009). Хеширование строк для линейного зондирования . Proc. 20-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA) . С. 655–664. CiteSeerX 10.1.1.215.4253 . DOI : 10.1137 / 1.9781611973068.72 ., раздел 5.3
- ^ а б Дицфельбингер, Мартин; Гил, Джозеф; Матиас, Йосси; Пиппенгер, Николас (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 г.
- ^ Канковск, Питер. «Хеш-функции: эмпирическое сравнение» .
- ^ Йигит, Озан. «Строковые хеш-функции» .
- ^ Керниган; Ричи (1988). «6». Язык программирования C (2-е изд.). С. 118 . ISBN 0-13-110362-8.CS1 maint: несколько имен: список авторов ( ссылка )
- ^ «Строка (Java Platform SE 6)» . docs.oracle.com . Проверено 10 июня 2015 .
дальнейшее чтение
- Кнут, Дональд Эрвин (1998). Искусство программирования, Vol. III: Сортировка и поиск (3-е изд.). Чтение, месса; Лондон: Аддисон-Уэсли. ISBN 0-201-89685-0.
Внешние ссылки
- Структуры открытых данных - Раздел 5.1.1 - Мультипликативное хеширование , Пэт Морин