Русская Википедия:Универсальное хеширование

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

Введение

Шаблон:Смотрите также

Впервые понятие универсального хеширования было введено в статье^[1] Картера и Шаблон:Нп4 в 1979 году.

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

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

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

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

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

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

Пусть <math>U</math> — множество ключей, <math>H</math> — конечное множество хеш-функций, отображающих <math>U</math> во множество <math>\left \{ 0,1,..,m-1 \right \}</math>. Возьмем произвольные <math>h \in H</math> и <math>x,y \in U</math> и определим функцию коллизий <math>\delta _h (x,y)</math>:

<math>\delta _h (x,y) = \begin{cases}

 1,  & \mbox{if }  x \ne y \mbox{ and } h(x) = h(y)\\
 0, & \mbox{otherwise}

\end{cases}</math>

Если <math>\delta _h (x,y) = 1</math>, то говорят, что имеет место коллизия. Можно определить функцию коллизии не для отдельных элементов <math>x,y,h</math>, а для целого множества элементов — для этого надо произвести сложение функций коллизий по всем элементам из множества. Например, если <math>H</math> — множество хеш-функций, <math>x \in U</math>, <math>S \subset U</math>, то для функции коллизии <math>\delta _H (x,S)</math> получим:

<math>\delta _H (x,S) = \sum_{h \in H} \sum_{y \in S} \delta _h (x,y)</math>

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

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

<math> \forall x, y \in U \longrightarrow \delta _H (x,S) = \frac{\left | H \right |}{m}.</math>

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

Определение. Семейство хеш-функций <math>H</math> называется универсальным^[3]Шаблон:Sfn, если

<math>\forall x, y \in U, ~ x\ne y: ~~ \Pr_{h\in H} [h(x) = h(y)] \le \frac{1}{m}</math>

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

Следующая теорема определяет нижнюю границу функции <math>\delta _h (x,y)</math> для произвольного семейства хеш-функций^[1].

Теорема 1.Для любого семейства(не обязательно универсального) хеш-функций <math>H</math> существуют <math>x,y \in U</math> такие, что

<math>\delta _H (x,S) > \frac{\left | H \right |}{m} - \frac{\left | H \right |}{\left | U \right |}</math>

Из теоремы 1 следует, что нижняя граница функции коллизии близка к <math>\frac{\left | H \right |}{m}</math> в случае, когда <math>\left | U \right | </math> много больше <math>m</math>. В действительности, часто так и бывает. Например, пусть компилятор ставит в соответствие тысяче переменных последовательности из семи английских букв. Тогда <math>m = 1000</math>, а <math>\left | U \right | = 26^7</math>

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

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

Пусть <math>H</math> — универсальное семейство хеш-функций, отображающих множество ключей <math>U</math> во множество <math>\left \{ 0,1,..,m-1 \right \}</math>. Пусть для организации хеш-таблицы с разрешением коллизий методом цепочек, то есть с помощью линейного списка, используется некоторая случайная функция <math>h \in H</math>. Если хеш-функция <math>h</math> отобразила в таблицу подмножество <math>S \subset U</math> ключей, то средняя длина связанных списков будет равна <math>1 + \delta _h (x,S)</math>. Следующая теорема дает оценку для функции коллизий в случае универсального семейства.

Теорема 2.^[1] Пусть <math>x</math> — произвольный элемент множества <math>U</math>, <math>S</math> — произвольное подмножество множества <math>U</math>. Пусть функция <math>h</math> случайно выбирается из универсального семейства хеш-функций <math>H</math>. Тогда имеет место следующая оценка:

<math>\delta _h (x,S) \leqslant \frac{\left | S \right |}{m} </math>

Этот результат можно использовать для вычисления ожидаемой производительности хеш-функции для последовательности из <math>R</math> запросов. Но сначала надо уточнить, что подразумевается под производительностью. Для этого нужно определить понятие стоимости — под стоимостью одного запроса к хеш-таблице по ключу <math>x</math> понимается число <math>1 + \delta _h (x,S) </math>, где <math>S</math> — множество ранее помещённых в таблицу ключей, а в самой хеш-таблице используется метод цепочек(то есть это число операций, необходимое для выполнения одного запроса). Стоимость <math>C(h,R)</math> хеш-функции <math>h</math> на последовательности запросов <math>R</math> есть сумма стоимостей отдельных запросов, идущих в последовательности, указанной в <math>R</math>. Стоимость, по сути, представляет количественную меру производительности.

Теорема 3.^[1] Пусть <math>x</math> Пусть <math>R</math> — это последовательность из <math>r</math> запросов, содержащая <math>k</math> вставок. Пусть <math>H</math> — универсальное семейство хеш-функций. Тогда для случайно выбранной из <math>H</math> хеш-функции <math>h</math> справедливо неравенство:

<math>M[C(h,R)] \leqslant r(1+\frac{k}{m})</math>.

Довольно часто^[1] известно приближенное число ключей, которое необходимо хранить в хеш-таблице. Тогда, можно подобрать размер <math>m</math> хеш-таблицы таким образом, чтобы отношение <math>\frac{k}{m}</math> было приблизительно равно 1. Значит, согласно теореме 3, ожидаемая стоимость исполнения последовательности запросов <math>R</math> будет прямо пропорционально числу запросов <math>r</math>. Причём это справедливо для любой последовательности запросов <math>R</math>, а не для некоторой «средней» последовательности.

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

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

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

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

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

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

Выберем простое число <math>p</math> и рассмотрим поле <math>\mathbb {Z}_p = \left \{ 0,1, ...,p-1 \right \}</math> и его мультипликативную группу <math>\mathbb {Z} _p^* = \left \{ 1,..,p-1 \right \}</math>.

Теорема. Множество функций вида <math>H_{p,m} = \left \{ h_{a,b}: a \in \mathbb {Z} _p^*,b \in \mathbb {Z} _p \right \}</math>, где <math>h_{a,b}(x) = ((ax+b) \mod p) \mod m</math>, является универсальным (Это было показано в работе Картера и Вегмана^[1]).

Действительно, <math>h(x) = h(y)</math> только при

<math>ax+b \equiv ay + b + i\cdot m \pmod{p}, \; \forall i \in \left \{ 0,1, ..., p/m \right \}.</math>

Если <math> x \neq y </math>, то разность <math>x-y \neq 0</math> и может быть обращена по модулю <math>p</math>. Отсюда можно получить

<math>a \equiv i\cdot m \cdot (x-y)^{-1} \pmod{p}.</math>

Это уравнение имеет <math>p-1</math> решений, причем правая часть может принимать <math>\lfloor p/m \rfloor</math> значений. Таким образом, вероятность коллизий равна

<math>\lfloor p/m \rfloor / (p-1)</math>,

которая стремится к <math>1/m</math> при увеличении <math>p</math>. <math>\Box</math>

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

Пусть число <math>m</math> является простым. Пусть входные данные <math>x</math> представлены как последовательность <math>r+1</math> элементов, принадлежащих <math>\left \{ 0,1,..,p-1 \right \}</math>, то есть <math>x = \left \langle x_0, x_1, ..., x_r \right \rangle</math>.

Для всех последовательностей вида <math>a = \left \langle a_0, a_1, ..., a_r \right \rangle, a_i \in \mathbb {Z}_p, i = \overline{0,r}</math> рассмотрим функцию <math>h_a</math> вида

Положим, что <math>H = \bigcup_a h_a</math>

Видно, что <math>H</math> содержит <math>m^{r+1}</math>

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

Действительно, если <math>x = \left \langle x_0, x_1, ..., x_r \right \rangle, y = \left \langle y_0, y_1, ..., y_r \right \rangle</math>, причём <math>x_0 \neq y_0</math>, то <math>h_a(x) = h_a(y)</math> тогда и только тогда, когда

Поскольку <math>x_0 - y_0 \not\equiv 0 \mod m </math>, то <math>\forall \left \langle a_1, ..., a_r \right \rangle, \exists ! a_0 </math> при котором выполняется указанное уравнение. Количество таких последовательностей равно <math>m^r</math>, а значит и количество функций из <math>H</math>, не различающих <math>x</math> и <math>y</math> также равно <math>m^r</math>. Но <math>m^r = \frac{\left | H \right |}{m}</math>, откуда и следует универсальность. <math>\Box</math>

Это семейство функций можно обобщить^[4]. Рассмотрим семейство функций <math>H_{p,m} = \left \{ h_{a,b}: a \in \mathbb {Z} _p^*,b \in \mathbb {Z} _p \right \}</math> и для вектора <math>x = \left \langle x_0, x_1, ..., x_r \right \rangle</math> рассмотрим хеш-функцию

<math>h(\bar{x}) = \left( \sum_{i=0}^{k-1} h_i(x_i) \right)\,\bmod~m</math>, где <math>h_i \in H</math>

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

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

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

Теперь предположим, что нельзя заранее подобрать число <math>L</math>, ограничивающее длину всех векторов. Тогда можно предложить такой подход^[5] : пусть имеется входной вектор <math>\bar{x} = (x_0,\dots, x_\ell), \forall x_i \in \left \{ 0, 1, ..., u-1 \right \}</math>. Положим, что <math>p \ge \max \{ u, m \}</math> и будем рассматривать компоненты вектора как коэффициенты многочлена: <math>x_l \cdot a^l + x_{l-1} \cdot a^{l-1} + ... x_{1} \cdot a^{1} + x_{0} \cdot a^{0},</math> где <math>a \in \left \{ 0, 1, ..., p-1 \right \}</math>.

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

<math>h_a(\bar{x}) = h_{a}^\mathrm{int} \left( \big(\sum_{i=0}^\ell x_i\cdot a^i \big) \bmod ~p \right),</math>

где

<math>h_{a}^\mathrm{int}:\left \{ 0,1,..,p-1 \right \} \rightarrow\left \{ 0,1,..,m-1 \right \}</math>

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

Применение

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

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

Теоретическая значимость универсального хеширования состоит в том, что оно даёт «хорошую» границу для средней производительности алгоритмов, использующих хеширование. Например, универсальное хеширование было применено в алгоритмах, представленных в работах ^[9] ^[10] ^[11].

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

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

См. также

MAC
UMAC

Примечания

Шаблон:Примечания

Литература

Ссылки

Внешние ссылки

↑ ^1,00 ^1,01 ^1,02 ^1,03 ^1,04 ^1,05 ^1,06 ^1,07 ^1,08 ^1,09 ^1,10 ^1,11 ^1,12 ^1,13 ^1,14 ^1,15 ^1,16 ^1,17 Шаблон:Статья
↑ ^2,0 ^2,1 Thorup, Mikkel, Speed Hashing for Integers and Strings Шаблон:Недоступная ссылка, Cornell University Library, July 15, 2014
↑ Шаблон:Книга
↑ ^4,0 ^4,1 Шаблон:Cite conference, section 5.3
↑ 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
↑ * David Wagner, ed. «Advances in Cryptology — CRYPTO 2008» Шаблон:Wayback. p. 145.
↑ * Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. «The Hash Function BLAKE» Шаблон:Wayback. 2014. p. 10.
↑ * 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.
↑ 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.
↑ .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.
↑ .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.

Шаблон:Выбор языка

[CW79-1] 1,00 ^1,01 ^1,02 ^1,03 ^1,04 ^1,05 ^1,06 ^1,07 ^1,08 ^1,09 ^1,10 ^1,11 ^1,12 ^1,13 ^1,14 ^1,15 ^1,16 ^1,17 Шаблон:Статья

[Mikkel-2] 2,0 ^2,1 Thorup, Mikkel, Speed Hashing for Integers and Strings Шаблон:Недоступная ссылка, Cornell University Library, July 15, 2014

[3] Шаблон:Книга

[thorup09-4] 4,0 ^4,1 Шаблон:Cite conference, section 5.3

[DGMP-5] 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

[6] * David Wagner, ed. «Advances in Cryptology — CRYPTO 2008» Шаблон:Wayback. p. 145.

[7] * Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. «The Hash Function BLAKE» Шаблон:Wayback. 2014. p. 10.

[8] * 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.

[9] 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.

[10] .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.

[11] .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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.