<tex>E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] \leqslant </tex> <tex dpi="150"> n + 2 \cdot {n-1 \over 2} = 2n - 1 < 2n</tex>, ч.т.д.
}}
Теперь выведем следствие 2 следствия из этой теоремы.
{{Теорема
}}
В данном методе видно{{Теорема|statement=Если мы сохраняем <tex>n</tex> ключей в хеш-таблице размером <tex>m=n</tex> с использованием хеш-функции <tex>h</tex>, выбираемой случайным образом из [[Универсальное_семейство_хеш-функций | универсального множества хеш-функций]], и устанавливаем размер каждой вторичной хеш-таблицы равным <tex>m_j=n_j^2</tex> <tex>(j=0,1,...,m-1)</tex>, то вероятность того, что очень неплохо экономится память по сравнению же с другими способами хешированияобщее количество необходимой для вторичных хеш-таблиц памяти не менее <tex>4n</tex>, меньше чем <tex>1/2</tex>.|proof=Применим [http://ru.wikipedia.org/wiki/Неравенство_Маркова неравенство Маркова] <tex>P(X \geqslant t) \leqslant E[X]/t</tex> Пусть <tex>X=\displaystyle \sum_{j=0}^{m-1} m_j</tex> и <tex>t=4n</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>, ч.т.д.}}
==См. также==
