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

Если недоброжелатель будет специально подбирать данные для хеширова­ния, то (зная функцию h) он может устроить так, что все п ключей будут соответствовать одной позиции в таблице, в результате чего время поиска будет равно (n). Любая фиксированная хеш-функция может быть дискредитирована таким образом. Единственный выход из положения – выбирать хеш-функцию случайным образом, не зависящим от того, какие именно данные вы хешируете. Такой подход называется универсальным хешированием (universal hashing). Что бы ни предпринимал ваш недоброжелатель, если он не имеет информации о выбранной хеш-функции, среднее время поиска останется хорошим.

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

Пусть Н – конечное семейство функций, отображающих данное множество U (множество всевозможных ключей) во множество (0,1,... ,m – 1} (множество хеш-значений). Это семейство называется универсальным (universal), если для любых двух ключей х,у  U число функций h  H, для которых h(x) = h(y), равно |H| / т. Иными словами, при случайном выборе хеш-функции вероятность коллизии между двумя данными ключами должна равняться вероятности совпадения двух случайно выбранных хеш-значений (которая равна 1 /m).

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

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

Доказательство. Математическое ожидание числа коллизий данного ключа с данным ключом у равно 1 / m по определению универсального семейства, поскольку всего имеется n – 1 ключей, отличных от х, математическое ожидание числа коллизий с каким-нибудь из этих ключей равно (п – 1) / m, что меньше единицы, поскольку n  m.

Как же построить универсальное семейство? Нам поможет в этом элементарная теория чисел. Число m (количество хеш-значений) выберем простым. Будем считать, что каждый ключ представляет собой последовательность r + 1 «байтов» (байт, или символ, – это просто двоичное число с ограниченным числом разрядов; мы будем считать, что максимальное значение байта меньше r. Для каждой последовательности а = a₀,a₁,...,а_г, элементы которой являются вычетами по модулю m (то есть принадлежат множеству {0,1,...,m – 1} - рассмотрим функцию h_a, заданную формулой

(4.2)

где ключ х есть последовательность байтов x₀, x₁, ... ,x_r. Положим

(4.3)

Очевидно, множество H содержит m^r+1 элементов.

Теорема 4.4. Семейство функций H, определённое формулами (4.2) и (4.3) является универсальным семейством хеш-функций.

Доказательство. Пусть х = х₀,х₁,…,х_r и у = у₀,y₁,...,y_r – два различных ключа;

не ограничивая общности, можно считать, что x₀ ≠ y₀. Если а = а₀, a₁,...,а_г, то h_a(x) = h_a(y) тогда и только тогда, когда

Поскольку x₀ – y₀ ≠ 0 (mod m), для каждой последовательности а₁,...,а_r существует

и единственно значение а₀, при котором это равенство выполнено. Количество таких последовательностей равно т^r, и таково же, стало быть, количество функций из H, не различающих ключи х и у. Поскольку т^r = |Н| / т, всё доказано.

Справедливой будет следующая интерпретация: ненулевой линейный функционал h → h(x – у) с равной вероятностью принимает любое из т своих значений, в том числе 0.