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

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

Качественная хеш-функция удовлетворяет (приближенно) условию простого равномерного хеширования: для каждого ключа, независимо от хеширования других ключей, равновероятно помещение его в любую из [math] m [/math] ячеек. Но это условие обычно невозможно проверить, так как распределение вероятностей, с которыми поступают входные данные, как правило, неизвестно. К тому же, вставляемые ключи могут и не быть независимыми. Если злой человек будет умышленно выбирать ключи для хеширования при помощи конкретной хеш-функции, то может получится так, что все ключи будут записанны в одну и ту же ячейку таблицы, что приведет к среднему времени выборки [math] \theta(n) [/math]. Таким образом, любая фиксированная хеш-функция становится уязвимой. И единственный эффективный выход из данной ситуации - случайный выбор хеш-функции. Такой подход называется универсальным хешированием. Он гарантирует хорошую производительность в среднем, вне зависимости от данных, выбранных злым человеком.

Определение:

Пусть [math] H [/math] — конечное множество хеш-функций, которые отображают пространство ключей [math]\ U [/math] в диапазон [math] \{0, 1, 2, .. , m - 1\} [/math]. Такое множество называется универсальным, если для каждой пары ключей [math] k, l \in U [/math] количество хеш-функций [math] h \in H [/math], для которых [math] h(k) = h(l) [/math] не превышает [math] |H| / m [/math].

Иными словами, при случайном выборе хеш-функции из [math] H [/math] вероятность коллизии между различными ключами [math] k, l [/math] не превышает вероятности совпадения двух случайным образом выбранных хеш-значений из множества [math] \{0, 1, 2, .. , m - 1\} [/math], которая равна [math] 1/m [/math]

Источники

• Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ, 2-е изд