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> Первый переход в равенстве мы совершили благодаря формуле <brtex>a^2 = a + 2\cdot\dbinom{a}{2}</tex>. Далее мы воспользовались свойствами [[Математическое_ожидание_случайной_величины | математического ожидания]], в частности - линейности.
Очевидно, что <tex>\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}</tex> - просто общее количество коллизий, поэтому по свойству универсального хеширования математическое ожидание значения этой суммы не превышает
