Изменения

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

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

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

|definition=

Такое множество называется '''универсальным''', если для каждой пары ключей <tex> k, l \in U </tex> количество хеш-функций <tex> h \in H </tex>, для которых <tex> h(k) = h(l) </tex> не превышает <tex> |H| / m </tex>.

}}

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