403
правки
Изменения
→Описание структуры данных
[[Файл:bloom_filter.png|thumb|360px|Пример фильтра Блума с <tex>m = 9</tex> и <tex>k = 3</tex>, хранящего множество из элементов <tex>A</tex> и <tex>B</tex>. Цветные стрелки указывают на места в битовом массиве, соответствующие каждому элементу множества. Этот фильтр Блума может определить, что элемент <tex>C</tex> входит в множество, хотя он и не добавлен в него.]]
Фильтр Блума представляет собой битовый массив из <tex>m</tex> бит. Изначально, когда структура данных хранит пустое множество, все <tex>m</tex> бит обнулены. Далее определяются и <tex>k</tex> независимых различных хеш-функций <tex>h_1\dots h_k</tex>, …, равновероятно отображающих элементы исходного множества во множество <tex>h_k\big\{ 0, 1, \dots m - 1 \big\}</tex>, отображающих каждый элемент соответствующее номерам битов в одну из массиве. Изначально, когда структура данных хранит пустое множество, все <tex>m</tex> позиций битового массива достаточно равномерным образомбит обнулены.
Для добавления элемента <tex>e</tex> необходимо записать единицы на каждую из позиций <tex>h_1(e)</tex>, …, <tex>\dots h_k(e)</tex> битового массива.
Чтобы проверить что элемент <tex>e</tex> принадлежит множеству хранимых элементов, необходимо проверить состояние битов <tex>h_1(e)</tex>, …, <tex>\dots h_k(e)</tex>. Если хотя бы один из них равен нулю, элемент не принадлежит множеству. Если все они равны единице, то структура данных сообщает, что элемент принадлежит множеству. При этом может возникнуть две ситуации: либо элемент действительно принадлежит к множеству, либо все эти биты оказались установлены по случайности при добавлении других элементов, что и является источником ложных срабатываний в этой структуре данных.
== Минимизация вероятности ложноположительного срабатывания ==
