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

Материал из Поле цифровой дидактики

Универса́льное хеши́рование (Шаблон:Lang-en) — это вид хеширования, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму<ref name=CW79> {{#if:Carter, Larry; Шаблон:Нп3|Carter, Larry; Шаблон:Нп3  }}{{#if: 

 | [{{{ссылка}}} Universal Classes of Hash Functions]
 | Universal Classes of Hash Functions

}}{{#if:en 

 | {{#ifexist: Шаблон:ref-en
     | Шаблон:Ref-en
     |  (en)
   }}

}}{{#if:| = {{{оригинал}}} }}{{#switch:{{#if:|а}}{{#if:Шаблон:Нп3|и}} 

 |аи= // {{{автор издания}}} Шаблон:Нп3
 |а= // {{{автор издания}}}
 |и= // Шаблон:Нп3

}}{{#if:journal| : journal }}{{#if:| / {{{ответственный}}} }}.{{#switch:{{#if:|м}}{{#if:|и}}{{#if:1979|г}} 

 |миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}, 1979.
 |ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}.
 |мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 1979.
 |иг= — {{{издательство}}}, 1979.
 |м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
 |и= — {{{издательство}}}.
 |г= — 1979.

}}{{#if:| — В. {{{выпуск}}}.

}}{{#if:| — Vol. {{{volume}}}. }}{{#if:| — Band {{{band}}}. }}{{#if:18| — Т. 18.

}}{{#if:2| — № 2.

}}{{#if:143—154| — С. 143—154. }}{{#if:| — P. {{{pages}}}. }}{{#if: | — S.</nowiki> {{{seite}}}.

}}{{#if:| — ISBN {{{isbn}}}. }}{{#if:| — ISSN Шаблон:ISSN search link. }}{{#if:10.1016/0022-0000(79)90044-8| — Шаблон:DOI }}{{#if:| — Шаблон:Bibcode }}{{#if:| — Шаблон:Arxiv }}{{#if: | — PMID {{{pmid}}}. }}{{#if: 

 |  [{{{archiveurl}}} Архивировано] из первоисточника {{#iferror: {{#time: j xg Y | {{{archivedate}}}}} | {{{archivedate}}}}}.

}}{{#if:

|

Этот шаблон использует устаревший параметр «название». Пожалуйста, отредактируйте эту статью, заменив «название» на «заглавие».

}}{{#if:

|

Этот шаблон использует устаревший параметр «город». Пожалуйста, отредактируйте эту статью, заменив «город» на «место».

}}</ref><ref name=Mikkel>Thorup, Mikkel, Speed Hashing for Integers and StringsШаблон:Недоступная ссылка, Cornell University Library, July 15, 2014</ref>. Такой подход обеспечивает равномерное хеширование: для очередного ключа вероятности помещения его в любую ячейку совпадают. Известно несколько семейств универсальных хеш-функций, которые имеют многочисленные применения в информатике, в частности в хеш-таблицах, вероятностных алгоритмах и криптографии.

Введение

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

Впервые понятие универсального хеширования было введено в статье<ref name=CW79/> Картера и Шаблон:Нп4 в 1979 году.

Изначально универсальное хеширование было разработано как независящий от входных данных алгоритм, работающий в среднем за линейное время и предназначенный для хранения и извлечения ключей из хеш-таблицы. Под независимостью от входных данных подразумевается следующее: для любой последовательности входных данных соответствующие хеш-значения элементов последовательности будут равномерно распределены по хеш-таблице. При выполнении этого условия среднее время работы алгоритма для любых данных оказывается сравнимым со временем работы хеш-функции, используемой для распределения заранее известных данных<ref name=CW79/>.

Созданный алгоритм универсального хеширования представлял собой случайный выбор хеш-функции из некоторого набора хеш-функций(называемого универсальным семейством хеш-функций), обладающих определёнными свойствами. Авторами было показано, что в случае универсального хеширования число обращений к хеш-таблице (в среднем по всем функциям из семейства) для произвольных входных данных оказывается очень близким теоретическому минимуму для случая фиксированной хеш-функции со случайно распределёнными входными данными<ref name=CW79/>.

Используя универсальное хеширование, авторы хотели<ref name=CW79/>:

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

В работе<ref name=CW79/> Вегмана и Картера универсальное хеширование было применено для построения хеш-таблицы, хотя позднее универсальное хеширование получило применение и в других областях(см. #Применение).

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

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

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

[math]\displaystyle{ \delta _H (x,S) = \sum_{h \in H} \sum_{y \in S} \delta _h (x,y) }[/math]

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

Определение. Семейство хеш-функций [math]\displaystyle{ H }[/math] называется универсальным<ref name=CW79/>, если

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

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

Определение. Семейство хеш-функций [math]\displaystyle{ H }[/math] называется универсальным<ref> {{#if:Motwani, Rajeev; Raghavan, Prabhakar|Motwani, Rajeev; Raghavan, Prabhakar }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Randomized Algorithms]]|{{#if:|[{{{ссылка}}} Randomized Algorithms]|Randomized Algorithms}}}}{{#if:| = {{{оригинал}}} }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Randomized Algorithms|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — {{{издание}}}.}}{{#switch:{{#if:|м}}{{#if:Cambridge University Press|и}}{{#if:1995|г}} 

 |миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: Cambridge University Press, 1995.
 |ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: Cambridge University Press.
 |мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 1995.
 |иг= — Cambridge University Press, 1995.
 |м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
 |и= — Cambridge University Press.
 |г= — 1995.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:216—217| — С. 216—217.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:0-521-47465-5| — ISBN 0-521-47465-5}} </ref>{{#if: | }}<ref name="{{#if: | | _2713df985c3a53e5 }}" group="{{#if: | }}">Шаблон:Sfn-текст.</ref>{{#if: | }}, если

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

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

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

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

[math]\displaystyle{ \delta _H (x,S) \gt \frac{\left | H \right |}{m} - \frac{\left | H \right |}{\left | U \right |} }[/math]

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

Для универсального семейства хеш-функций это означает, что верхняя и нижняя границы функции коллизии довольно близки<ref name=CW79/>.

В статье<ref name=CW79/> универсальное хеширование применялось для организации хеш-таблиц с разрешением коллизий методом цепочек. Ниже изложены теоремы, дающие некоторые оценки значений функции коллизии и производительности хеширования в случае организации хеш-таблицы с разрешением коллизий методом цепочек.

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

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

[math]\displaystyle{ \delta _h (x,S) \leqslant \frac{\left | S \right |}{m} }[/math]

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

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

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

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

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

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

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

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

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

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

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

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

Действительно, [math]\displaystyle{ h(x) = h(y) }[/math] только при

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

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

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

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

[math]\displaystyle{ \lfloor p/m \rfloor / (p-1) }[/math],

которая стремится к [math]\displaystyle{ 1/m }[/math] при увеличении [math]\displaystyle{ p }[/math]. [math]\displaystyle{ \Box }[/math]

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

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

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

[math]\displaystyle{ h_a(x) =\sum^{r}_{i=0} {a_ix_i} \mod m }[/math]

Положим, что [math]\displaystyle{ H = \bigcup_a h_a }[/math]

Видно, что [math]\displaystyle{ H }[/math] содержит [math]\displaystyle{ m^{r+1} }[/math]

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

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

[math]\displaystyle{ a_0(x_0 - y_0) = - \sum^{r}_{i=1} {a_i(x_i - y_i)} \mod m }[/math]

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

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

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

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

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

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

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

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

[math]\displaystyle{ 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]\displaystyle{ h_{a}^\mathrm{int}:\left \{ 0,1,..,p-1 \right \} \rightarrow\left \{ 0,1,..,m-1 \right \} }[/math]

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

Применение

Коды аутентификации сообщений UMAC, Шаблон:Нп4 и некоторые другие основаны на использовании универсального хеширования<ref>* David Wagner, ed. «Advances in Cryptology — CRYPTO 2008» Шаблон:Wayback. p. 145.</ref><ref>* Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. «The Hash Function BLAKE» Шаблон:Wayback. 2014. p. 10.</ref><ref>* 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.</ref>. В этих кодах для каждого сообщения выбирается своя хеш-функция в зависимости от его одноразового уникального номера.

Универсальное семейство хеш-функций может быть использовано в том случае, когда требуется наличие большого числа «хороших» хеш-функций. Программисты часто тратят много времени, проводя анализ работы хеш-функций на различных данных и пытаясь выбрать подходящую{{#if: | }}<ref name="{{#if: | | _6af8d9ad022bab44 }}" group="{{#if: | }}">Шаблон:Sfn-текст.</ref>{{#if: | }}. Время поиска можно уменьшить, взяв универсальное семейство хеш-функций и выбрав случайно несколько функций из этого семейства<ref name=CW79/>.

Теоретическая значимость универсального хеширования состоит в том, что оно даёт «хорошую» границу для средней производительности алгоритмов, использующих хеширование. Например, универсальное хеширование было применено в алгоритмах, представленных в работах <ref>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.</ref> <ref>.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.</ref> <ref>.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.</ref>.

В теоретической криптографии было показано, что с помощью универсальных хеш-функций можно построить систему аутентификации с предельно достижимой секретностью<ref name=CW79/>. Примером универсальной хеш-функцией с доказанной криптографической стойкостью является хеш-функция SWIFFT.

Более того, одним из наиболее важных приложений универсального хеширования является скоординированная выборка<ref name=Mikkel/>.

См. также

Примечания

1 }} 
       | {{#switch: 2
         | узкие = columns reflist-narrow
         | широкие = columns reflist-wide
         | #default = columns
         }}
       | {{#switch: 2
         | 1 = 
         | 2 | 3 = columns
         | #default = columns reflist-narrow
         }}
       }}
     | columns
     }}
   }}" style="{{#if: 
   | column-width:{{{colwidth}}};
   | {{#if: 2
     | {{#iferror: {{#ifexpr: 2 > 1 }}
       | {{#switch: 2
         | узкие | широкие = 
         | #default = column-width:2;
         }}
       }}
     }}
   }} list-style-type: {{#switch: 
   | upper-alpha
   | upper-roman
   | lower-alpha
   | lower-greek
   | lower-roman = {{{group}}}
   | #default = decimal
   }};">

<references group="" responsive="{{#if: 

 | 0
 | {{#if: 2
   | {{#iferror: {{#expr: 2 > 1 }}
     | {{#switch: 2
       | узкие | широкие = 1
       | #default = 0
       }}
     | {{#switch: 2
       | 1 = 0
       | #default = 1
       }}
     }}
   | 1
   }}
}}"></references>

Ошибка скрипта: Модуля «Check for unknown parameters» не существует.

Литература

  • {{#if:Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.|Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Алгоритмы: построение и анализ]]|{{#if:https://books.google.ru/books?id=NLngYyWFl_YC%7CАлгоритмы: построение и анализ|Алгоритмы: построение и анализ}}}}{{#if:Introduction to algorithms| = Introduction to algorithms }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Алгоритмы: построение и анализ|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:2-е изд| — 2-е изд.}}{{#switch:{{#if:USA|м}}{{#if:MIT Press|и}}{{#if:2001|г}}
 |миг= — {{#if:USA|{{#switch:USA|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:USA|USA}} }}: MIT Press, 2001.
 |ми= — {{#if:USA|{{#switch:USA|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:USA|USA}} }}: MIT Press.
 |мг= — {{#if:USA|{{#switch:USA|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:USA|USA}} }}, 2001.
 |иг= — MIT Press, 2001.
 |м= — {{#if:USA|{{#switch:USA|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:USA|USA.}} }}
 |и= — MIT Press.
 |г= — 2001.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:234—237| — С. 234—237.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:1180| — 1180 с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:9780262032933| — ISBN 9780262032933}}

  • {{#if:Дональд Кнут|Дональд Кнут }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Искусство программирования, том 3. Сортировка и поиск]]|{{#if:|[ Искусство программирования, том 3. Сортировка и поиск]|Искусство программирования, том 3. Сортировка и поиск}}}}{{#if:The Art of Computer Programming, vol.3. Sorting and Searching| = The Art of Computer Programming, vol.3. Sorting and Searching }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Искусство программирования, том 3. Сортировка и поиск|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:2-е изд| — 2-е изд.}}{{#switch:{{#if:Шаблон:М.|м}}{{#if:Вильямс|и}}{{#if:2007|г}}
 |миг= — {{#if:Шаблон:М.|{{#switch:Шаблон:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ Шаблон:М. }}|Шаблон:М.}} }}: Вильямс, 2007.
 |ми= — {{#if:Шаблон:М.|{{#switch:Шаблон:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ Шаблон:М. }}|Шаблон:М.}} }}: Вильямс.
 |мг= — {{#if:Шаблон:М.|{{#switch:Шаблон:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ Шаблон:М. }}|Шаблон:М.}} }}, 2007.
 |иг= — Вильямс, 2007.
 |м= — {{#if:Шаблон:М.|{{#switch:Шаблон:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ Шаблон:М. }}|Шаблон:М..}} }}
 |и= — Вильямс.
 |г= — 2007.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:508—513, 557| — С. 508—513, 557.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:824| — 824 с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:0-201-89685-0| — ISBN 0-201-89685-0}}

  • {{#if:Michael Luby|Michael Luby }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Pseudorandomness and Cryptographic Applications]]|{{#if:|[{{{ссылка}}} Pseudorandomness and Cryptographic Applications]|Pseudorandomness and Cryptographic Applications}}}}{{#if:| = {{{оригинал}}} }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Pseudorandomness and Cryptographic Applications|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — {{{издание}}}.}}{{#switch:{{#if:USA|м}}{{#if:Princeton University Press|и}}{{#if:1996|г}}
 |миг= — {{#if:USA|{{#switch:USA|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:USA|USA}} }}: Princeton University Press, 1996.
 |ми= — {{#if:USA|{{#switch:USA|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:USA|USA}} }}: Princeton University Press.
 |мг= — {{#if:USA|{{#switch:USA|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:USA|USA}} }}, 1996.
 |иг= — Princeton University Press, 1996.
 |м= — {{#if:USA|{{#switch:USA|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:USA|USA.}} }}
 |и= — Princeton University Press.
 |г= — 1996.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:153—163| — С. 153—163.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:248| — 248 с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:0691025460| — ISBN 0691025460}}

Ссылки

Шаблон:Внешние ссылки

Источник — http://digida.mgpu.ru/index.php?title=Универсальное_хеширование&oldid=4663