418
правок
Изменения
м
}}Как видно вероятность возникновения коллизий
→Метод №1
{{Теорема
|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> пар ключей, которые могут вызвать коллизию. Если хеш-функция выбрана случайным образом из [[Универсальное_семейство_хеш-функций | универсального семейства хеш-функций ]] H, то для каждой пары вероятность возникновения коллизии равна <tex dpi="180">{1 \over m}</tex>. Пусть <tex>X</tex> - [[Дискретная_случайная_величина |случайная величина]], которая подсчитывает количество коллизий. Если <tex>m = n^2</tex>, то [[Математическое_ожидание_случайной_величины | математическое ожидание ]] числа коллизий равно
<tex>E[X] = </tex> <tex dpi="180"> \binom{n}{2} * {1 \over n^2} = {n^2-n \over n} * {1 \over n^2} < {1 \over 2}</tex>
}}
Это является очень хорошим результатом, если хотя бы вспомнить на примере [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0#.D0.92.D0.B2.D0.B5.D0.B4.D0.B5.D0.BD.D0.B8.D0.B5 парадокса дней рождения] о том, что вероятность коллизий растет крайне быстро по сравнению с размером хеш-таблицы.
== Метод №2 ==
Будем использовать <tex>O(n)</tex> памяти.
