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

Переходим к созданию универсального класса хеш-функций. В качестве размера хеш-таблицы H будет использоваться простое число p ≈ n.

Чтобы иметь возможность использовать целочисленную арифметику при создании хеш-функций, универсальное множество будет определяться векторами вида x = (x1,x2,... xr) для некоторого целого r, где 0 ≤ xi < p для каждого i.

Например, можно сначала идентифицировать U целыми числами из диапазона [0,N−1] для некоторого N, а затем воспользоваться смежными блоками из   битов u для определения соответствующих координат xi. Если U Ӭ [0, N − 1], то необходимое количество координат составит r ≈ log N/\log n.

Пусть A — множество всех векторов вида a = (a1, ..., ar), где ai — целое число из диапазона [0, p − 1] для каждого i = 1, …, r. Для каждого a Ѯ A определяется линейная функция .

Случайная реализация словарей завершена. Семейство хеш-функций определяется в виде H = {ha : a Ѯ A}. Чтобы выполнить операцию MakeDictionary, мы выбираем случайную хеш-функцию из H; иначе говоря, выбирается случайный вектор из A (случайным равномерным выбором каждой координаты), и формируется функция ha.

Затем результат используется как хеш-функция для реализации операций Insert, Delete и Lookup. Семейство H = {ha : a Ѯ A} удовлетворяет формальному определению второго свойства: оно имеет компактное представление, так как простым выбором и сохранением случайного a Ѯ A мы можем вычислить ha(u) для всех элементов u Ѯ U.

Следовательно, чтобы показать, что H ведет к эффективной реализации словарей на базе хеширования, достаточно показать, что H — универсальное семейство хеш-функций.