418
правок
Изменения
м
→Метод №2
Если мы сохраняем <tex>n</tex> ключей в хеш-таблице в хеш-таблице размеров <tex>m=n</tex> c использованием хеш-функции <tex>h</tex>, выбираемой случайным образом из универсального множества хеш-функций, то <tex>E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] < 2n</tex>, где <tex>n_j</tex> - количество ключей, хешированных в ячейку <tex>j</tex>.
|proof=
<tex>E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] = </tex> <tex> E\left[ \displaystyle \sum_{j=0}^{m-1} (n_j + 2 \dbinom{n_j}{2})\right] = </tex> <tex> E\left[ \displaystyle \sum_{j=0}^{m-1} n_j\right] + 2E\left[\displaystyle \sum_{j=0}^{m-1} (\dbinom{n_j }{2)}\right]= </tex> <tex> E\left[n\right] + 2E\left[\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}\right] = n + 2E\left[\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2} \right]</tex><br>
Очевидно, что <tex>\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}</tex> - просто общее количество коллизий, поэтому по свойству универсального хеширования математическое ожидание значения этой суммы не превышает
<tex dpi="180">\binom{n}{2}{1 \over m} = {n(n-1) \over 2m} = {n-1 \over 2}</tex>
А так как <tex>m = n</tex>, то
<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>, ч.т.д.
}}
