Изменения
Отмена правки 32172 участника 217.66.152.89 (обсуждение)
{{Теорема
|statement=
Если <tex>n</tex> ключей сохраняются в хеш-таблице размером <tex>m=n^2</tex> c использованием хеш-функции <tex>h</tex>, случайно выбраннойверсальное_семейство_хешвыбранной из [[Универсальное_семейство_хеш-функций | универсального множества хеш-функций]], то вероятность возникновения коллизий не превышает <tex dpi="180">{1 \over 2}</tex>.
|proof=
Всего имеется <tex>\dbinom{n}{2}</tex> пар ключей, которые могут вызвать коллизию. Если хеш-функция выбрана случайным образом из [[Универсальное_семейство_хеш-функций | универсального семейства хеш-функций]] <tex>H</tex>, то для каждой пары вероятность возникновения коллизии равна <tex dpi="180">{1 \over m}</tex>. Пусть <tex>X</tex> {{---}} [[Дискретная_случайная_величина |случайная величина]], которая подсчитывает количество коллизий. Если <tex>m = n^2</tex>, то [[Математическое_ожидание_случайной_величины | математическое ожидание]] числа коллизий равно
