---
title: Bloom Filter
localeTitle: Цветной фильтр
---
## Описание

Фильтр Bloom - это структура данных, аналогичная набору. Фильтр Bloom позволяет задать вопрос. _Этот элемент является членом набора?_ для быстрого ответа. Фильтр никогда не вернет _No,_ если элемент находится в наборе; но он может вернуть _Да,_ если элемент не находится в наборе. Это один из недостатков использования фильтра Bloom, есть вероятность получения ложных положительных результатов при проверке наличия элемента в наборе. Потенциал использования фильтра Bloom заключается в том, что добавление элемента в набор и проверка того, находится ли элемент в наборе, - это операция [O (n)](https://guide.freecodecamp.org/algorithms/algorithm-performance) с постоянным временем.

## пример

В следующем примере фильтр Bloom используется для создания списка друзей. Пример реализации использует три [функции хэширования](https://guide.freecodecamp.org/miscellaneous/hash-tables-and-hashing-functions) . Хеширующие функции поглощают строку (имя друга) и вычисляют единственное значение для строки в зависимости от количества пятен в фильтре Bloom.

Создайте фильтр как массив из 10 индексов. A `0` указывает, что в этом индексе нет элемента.

`[0,0,0,0,0,0,0,0,0,0]`

Пользователь добавляет Дэвида в список друзей. Строка ( `'David'` ) передается через несколько функций хеширования, которые возвращают `0` , `4` и `8` соответственно. Значения из хэш-функций используются для обновления массива фильтров по этим индексам.

Индексы фильтра обновляются с использованием этих хешированных значений. A `1` указывает, что элемент был добавлен в этот индекс.

`[1,0,0,0,1,0,0,0,1,0]`

Пользователь добавляет Рози в список друзей. Хеширующие функции возвращают `3` , `4` и `6` для `'Rosie'` . Индексы фильтра обновляются с использованием хешированных значений.

`[1,0,0,1,1,0,1,0,1,0]`

Есть чек, если Чак является членом списка друзей. Строка `'Chuck'` передается через хеширующие функции, возвращающие `1` , `3` и `6` . Когда массив фильтров проверяется по этим индексам, он возвращает `0` , `1` и `1` . Поскольку один индекс имеет значение `0` , Чак _определенно_ не входит в список.

Есть проверка, является ли Maja членом списка друзей. Строка `'Maja'` передается через хеширующие функции, возвращая `0` , `6` и `8` . Когда массив фильтров проверяется по этим индексам, он возвращает `1` , `1` и `1` . Поскольку все три индекса имеют значение `1` , Maja _может_ быть уже членом списка. Это ложноположительный результат.

## Соображения

Bloom фильтры позволяют быстро искать , чтобы определить , является ли значение , _возможно_ , состоит из набора или _определенно_ не является членом множества. Чем больше элементов, добавленных в фильтр Блума, тем больше вероятность получения ложных положительных результатов при проверке того, является ли элемент членом набора. Один из способов уменьшить скорость ложноположительных результатов - увеличить размер массива. Хотя это компромисс, потому что чем больше массив, тем большую память он займет. Необходимо определить приемлемую скорость ложноположительных результатов для заданного размера массива.

## Дальнейшее чтение

[Средний алгоритм публикации](https://blog.medium.com/what-are-bloom-filters-1ec2a50c68ff)

[Википедия на Bloom фильтры](https://en.wikipedia.org/wiki/Bloom_filter)