Изменения

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

<tex dpi = "150">Prp(h_i(x) = t\neq j) = 1 - \frac 1m </tex>, где <tex dpi = "150">t = {1 .. }{m} </tex>

Тогда вероятность того, что в некоторый p<tex> j </tex>-й ый бит не будет записана единица во время операции вставки очередного элемента равна:

<tex dpi = "150">Prp(h_i(x) \ne pneq j</tex> для <tex dpi = "150"> \forall i: i \in \big\{ 1 \dots k \big\})^k = (1 - \frac 1m{1}{m})^k </tex>

А вероятность того, что p<tex> j </tex>-й ый бит останется равным нулю после вставки <tex> n </tex> различных элементов:

<tex dpi = "150">(1 - \frac 1m{1}{m})^{kn} </tex>

В силу второго замечательного предела и достаточно большого <tex> m </tex> можем это записать как:

<tex dpi = "150">(1 - \frac {1}{m})^{kn} \approx e^{-kn/m}</tex>

Ложноположительное срабатывание происходит тогда, когда для несуществующего элемента все <tex>k</tex> бит окажутся ненулевыми, и фильтр Блума ответит, что он входит в число вставленных элементов.Вероятность Тогда вероятность такого события тогда равна:

Для фиксированных <tex> m </tex> и <tex> n</tex>, оптимальное число хеш-функций <tex> k</tex>, минимизирующих вероятность ложноположительного срабатывания, равно:

<tex dpi = "150">k = \frac mn ln(2) \frac {m}{n} \approx 0.6931 \frac {m}{n}</tex>