Универсальное хеширование

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Универса́льное хеши́рование (англ. Universal hashing) — это вид хеширования, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму[1][2]. . Такой подход обеспечивает равномерное хеширование: для очередного ключа вероятности помещения его в любую ячейку совпадают. Известно несколько семейств универсальных хеш-функций, которые имеют многочисленные применения в информатике, в частности в хеш-таблицах, вероятностных алгоритмах и криптографии.

Введение[править | править вики-текст]

Впервые понятие универсального хеширования было введено в статье [1] Картера и Вегманаruen в 1977 году.

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

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

Используя универсальное хеширование, авторы хотели[1]:

  1. Избавиться от необходимости предполагать вид входных данных.
  2. Устранить зависимость времени работы хеширования от вида входных данных.
  3. Добиться уменьшения числа коллизий.

В работе[1] Вегмана и Картера универсальное хеширование было применено для построения хеш-таблицы, хотя позднее универсальное хеширование получило применение и в других областях(см. #Применение).

Определение универсального семейства хеш-функций[править | править вики-текст]

Пусть  — множество ключей,  — конечное множество хеш-функций, отображающих во множество . Возьмем произвольные и и определим функцию коллизий :

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

Причем порядок суммирования не имеет значения.

Определение.Семейство хеш-функций называется универсальным[1], если

Можно дать другое определение, эквивалентное данному.

Определение. Семейство хеш-функций называется универсальным[3][4], если

Свойства универсального семейства хеш-функций в случае его применения к хеш-таблицам[править | править вики-текст]

Следующая теорема определяет нижнюю границу функции для произвольного семейства хеш-функций[1].

Теорема 1.Для любого семейства(не обязательно универсального) хеш-функций существуют такие, что

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

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

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

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

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

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

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

.

Довольно часто[1] известно приближенное число ключей, которое необходимо хранить в хеш-таблице. Тогда, можно подобрать размер хеш-таблицы таким образом, чтобы отношение было приблизительно равно 1. Значит, согласно теореме 3, ожидаемая стоимость исполнения последовательности запросов будет прямо пропорционально числу запросов . Причем это справедливо для любой последовательности запросов , а не для некоторой "средней" последовательности.

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

В случае с хеш-таблицами частая смена хеш-функций ведет к большим накладным расходам. Например, если хеш-таблица имеет очень большие размеры, то при смене хеш-функции потребуется перемещение большого объема данных. Существует несколько стратегий выбора хеш-функции. Наиболее простая стратегия состоит в том, чтобы в начале работы случайно выбрать хеш-функцию и не менять её вплоть до конца работы. Однако в этом случае производительность хеш-функции оказывается значительно ниже ожидаемой[1]. Другая стратегия состоит в том, чтобы время от времени подсчитывать число коллизий и менять хеш-функцию, если это число значительно превышает ожидаемое. Такой подход обеспечивает хорошую производительность, при условии, что хеш-функция выбирается случайно.

Построение универсального семейства хеш-функций[править | править вики-текст]

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

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

Хеширование чисел[править | править вики-текст]

Выберем простое число и рассмотрим поля и .

Теорема. Множество функций вида , где , является универсальным ( Это было показано в работе Картера и Вегмана[1]).

Действительно, только при

Если , то разность и может быть обращена по модулю . Отсюда можно получить

Это уравнение имеет решений, причем правая часть может принимать значений. Таким образом, вероятность коллизий равна

,

которая стремится к при увеличении .

Хеширование векторов[править | править вики-текст]

Пусть число является простым. Пусть входные данные представлены как последовательность элементов, принадлежащих , то есть .

Для всех последовательностей вида рассмотрим функцию вида

Положим, что

Видно, что содержит

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

Действительно, если , причем , то тогда и только тогда, когда

Поскольку , то при котором выполняется указанное уравнение. Количество таких последовательностей равно , а значит и количество функций из , не различающих и также равно . Но , откуда и следует универсальность.

Это семейство функций можно обобщить[5]. Рассмотрим семейство функций и для вектора рассмотрим хеш-функцию

, где

Тогда совокупность таких функций также будет являться универсальным семейством.

Хеширование строк[править | править вики-текст]

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

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

Тогда для векторов переменной длины универсальная хеш-функция может быть определена следующим образом:

где

является универсальной хеш-функцией для числовых аргументов.

Применение[править | править вики-текст]

Коды аутентификации сообщений UMAC, Poly1305-AESruen и некоторые другие основаны на использовании универсального хеширования[7][8] [9]. В этих кодах для каждого сообщения выбирается своя хеш-функция в зависимости от его одноразового уникального номера.

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

Теоретическая значимость универсального хеширования состоит в том, что оно дает "хорошую" границу для средней производительности алгоритмов, использующих хеширование. Например, универсальное хеширование было применено в алгоритмах, представленных в работах[11][12][13].

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

Более того, одним из наиболее важных приложений универсального хеширования является скоординированная выборка[2].

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 (1979) «Universal Classes of Hash Functions». Journal of Computer and System Sciences 18 (2): 143–154. DOI:10.1016/0022-0000(79)90044-8. Conference version in STOC'77.
  2. 1 2 Thorup, Mikkel, Speed Hashing for Integers and Strings, Cornell University Library, July 15, 2014
  3. Randomized Algorithms. — Cambridge University Press, 1995. — P. 216-17. — ISBN 0-521-47465-5.
  4. Cormen, 2001, pp. 234-235.
  5. 1 2 Thorup, Mikkel (2009). "String hashing for linear probing".: Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), 655–664. DOI:10.1137/1.9781611973068.72. , section 5.3
  6. Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas(1992). "Polynomial Hash Functions Are Reliable (Extended Abstract)". Proc. 19th International Colloquium on Automata, Languages and Programming (ICALP). pp. 235–246
  7. David Wagner, ed. «Advances in Cryptology — CRYPTO 2008». p. 145.
  8. Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. «The Hash Function BLAKE». 2014. p. 10.
  9. * M. Wegman and L. Carter, «New hash functions and their use in authentication and set equality», Journal of Computer and System Sciences, 22 (1981), pp. 265-279.
  10. Knuth, 2007.
  11. M. 0. RABIN, Probabilistic algorithms, in “Proceedings of Symposium on New Directions and Recent Results in Algorithms and Complexity” (J. F. Traub, Ed.), pp. 21-39, Academic Press, New York, 1976.
  12. . GOTO AND Y. KANADA, Hashing lemmas on time complexities with applications to formula manipulation, in “Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation,” Yorktown Heights, N. Y., pp. 149-153.
  13. . GUSTAVSON AND D. Y. Y. YUN, Arithmetic complexity of unordered or sparse polynomials, in “Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation,” Yorktown Heights, N. Y., pp. 154-159.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]