403
правки
Изменения
→Минимизация вероятности ложноположительного срабатывания
== Минимизация вероятности ложноположительного срабатывания ==
Пусть размер битового массива <tex> m </tex>, и заданы <tex> k </tex> хеш-функций, причем все хеш-функции являются [[Независимые случайные величины|независимыми случайными величинами]]. Тогда вероятность, что в <tex> j </tex>-ый бит не будет записана единица <tex> i </tex>-ой хеш-функцией при вставке очередного элемента, равна:
<tex dpi = "150">p(h_i(x) \neq j) = 1 - \frac {1}{m} </tex>
