Универсальное семейство хеш-функций — различия между версиями

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

Версия 09:59, 15 июня 2011

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

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