Универсальные классы хеш-функций

Ключевая идея заключается в том, что хеш-функция случайно выбирается не из набора всех возможных функций со значениями [0,n − 1], а из особого семейства функций. Каждая функция h в классе функций H отображает универсальное множество U на множество {0,1, …, n − 1}, а включаемые функции должны обладать двумя свойствами. Во-первых, они должны предоставлять гарантии из (13.22):

Для любой пары элементов u, v Ѯ U вероятность того, что для случайно выбранной функции h Ѯ H выполняется h(u) = h(v), не более 1/n.

Класс функций H называется универсальным, если для него выполняется первое свойство. Таким образом, (13.22) можно рассматривать как утверждение о том, что класс всех возможных функций, отображающих U на {0,1, ...,n−1}, является универсальным.

Однако для класса H также должно выполняться второе свойство. Сейчас мы его сформулируем неформально, а позднее приведем более точное определение.

Каждая функция h Ѯ H имеет компактное представление, и для заданных h Ѯ H

и u Ѯ U значение h(u) может быть вычислено эффективно.

Класс всех возможных функций этим свойством не обладает: фактически единственным способом представления произвольной функции из U в {0, 1, …, n − 1} является запись ее значений для каждого элемента U.

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

Если функция h выбирается случайным образом из универсального класса хеш-функций, то для любого множества SӨU, размер которого не превышает n, и любого u Ѯ U, ожидаемое количество элементов S, создающих коллизию с u, является константой.

Пусть H — универсальный класс хеш-функций, отображающих универсальное множество U на множество {0, 1, …, n − 1}, S — произвольное подмножество U размера не более n, а u — любой элемент U.

Определим X как случайную переменную, равную количеству элементов s Ѯ S, для которых h(s) = h(u), для случайно выбранной хеш-функции h Ѯ H. (Здесь S и u фиксированны, а случайность проявляется в выборе h Ѯ H). Тогда [X] ≤ 1.

Доказательство. Для элемента s Ѯ S определяется случайная переменная Xs, которая равна 1, если h(s) = h(u), или 0 в противном случае, так как класс функций универсален.