Изменения

Пусть размер битового массива <tex>m</tex> и задано <tex>k</tex> хеш-функций таких, что каждая из них назначает место элементу <tex>x</tex> в битовом массиве с равной вероятностью.:

<texdpi = "150">Pr(h_i(x) = t) = \frac 1m </tex>, где <texdpi = "150">t = 1 .. m</tex> Тогда вероятность того, что в некоторый p-й бит не будет записана единица во время операции вставки очередного элемента равна: <tex dpi = "150">Pr(h_i(x) \ne p)^k = (1 - \frac 1m)^k </tex> А вероятность того, что p-й бит останется равным нулю после вставки n различных элементов: <tex dpi = "150">(1 - \frac 1m)^{kn} </tex> В силу второго замечательного предела и достаточно большого m можем это записать как: <tex dpi = "150"">e^{-kn/m}</tex> Ложноположительное срабатывание происходит тогда, когда для несуществующего элемента все <tex>k</tex> бит окажутся ненулевыми, и фильтр Блума ответит, что он входит в число вставленных элементов.Вероятность такого события тогда равна: <tex dpi = "150">(1 - e^{-kn/m})^k</tex> Для фиксированных m и n, оптимальное число k (число хеш-функций), минимизирующих её, равно: <tex dpi = "150">k = \frac mn ln(2) </tex> А сама вероятность ложного срабатывания равна: <tex dpi = "150">2^{-k}</tex>