Изменения
→Теоретическое обоснование
{{Теорема
|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>, то [[Математическое_ожидание_случайной_величины | математическое ожидание]] числа коллизий равно
Тогда <tex>P \left \{\displaystyle \sum_{j=0}^{m-1} m_j \geqslant 4n \right \} \leqslant E\left[\displaystyle\sum_{j=0}^{m-1} mj\right]</tex> <tex dpi="150"> {1 \over 4n} < </tex> <tex dpi="150">{2n \over 4n} = {1 \over 2}</tex>, ч.т.д.
}}
==См. также==
* [[Хеширование]]
