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