308
правок
Изменения
Попарная независимость
Значит, <tex dpi = "150">\forall k\ne l\in Z_p\ P(h_{a,b}(k)=h_{a,b}(l))\le\frac{1}{m}</tex>, что означает, что множество хеш-функций <tex>H_{p,m}</tex> является универсальным.
}}
== Попарная независимость ==
{{Определение
|definition=
Пусть <tex> H </tex> {{---}} универсальное семейство хеш-функций.
Говорят что оно обладает свойством '''попарной независимости''', если для фиксированных <tex> x, y</tex> <tex> (0 \le x, y \le m-1)</tex> для каждой пары ключей <tex> k, l \in U, (k\ne l) </tex> количество хеш-функций <tex> h \in H </tex>, для которых <tex> h(k) = x </tex> и <tex> h(l) = y </tex> не превышает <tex dpi = "180"> \frac{|H|}{m^2} </tex>.
}}
==Источники==
