308
правок
Изменения
м
→Попарная независимость
|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(k) = x </tex> и <tex> h(l) = y </tex>, равна <tex dpi = "150"> \frac{1}{m^2} + o(\frac{1}{m^2}) </tex>.
}}
