Фильтр Блума

Фильтр Блума — структура данных, которая помогает быстро проверить, может ли элемент находится в наборе данных или точно его там нет. Используется, когда проверка наличия элемента должна быть быстрой, а использование памяти минимальным.

Как работает фильтр Блума

Фильтр Блума работает как "чек-лист". Он отвечает:

Может быть, элемент есть (иногда может ошибиться)
Точно элемента нет

Шаги работы фильтра Блума

Создание битового массива:
- Создается битовый массив длины m.
- Он состоит из 0 и 1.
- Изначально массив выглядит так: [0, 0, 0, 0, 0, 0, 0, 0].
- Каждая позиция (индекс) в этом массиве и значения (0, 1) — всё, что фильтр "запоминает".
Добавление элемента:
- Например, id = 12345.
- Фильтр пропускает id через несколько хэш-функций.
  - Хэш-функция — математический алгоритм, который превращает строку ("12345") в числа (индексы массива).
  - Пример:
    - hash_1("12345") -> 2
    - hash_2("12345") -> 5
    - hash_3("12345") -> 7
- Фильтр "ставит галочки" на этих позициях, т.е. устанавливает биты на этих индексах = 1:
  - [0, 0, 1, 0, 0, 1, 0, 1]
- Фильтр запоминает, что на позициях [2, 5, 7] есть что-то.
Проверка элемента:
- Чтобы узнать, есть ли id = 54321 в фильтре Блума:
  - Он снова пропускается через те же хэш-функции:
    - hash_1("54321") -> 1
    - hash_2("54321") -> 3
    - hash_3("54321") -> 6
  - Фильтр смотрит на эти индексы в массиве: [0, 0, 1, 0, 0, 1, 0, 1].
  - Позиция 1 = 0 -> id = "54321" точно не добавлялся.
  - Если бы добавлялся, то позиция 1 была бы = 1.
- Если все проверенные индексы равны 1, то фильтр говорит: может быть, элемент есть.
- Если хотя бы один бит на позициях, которые вычислили хэш-функции, равен 0, элемент точно отсутствует.

Чего нет в фильтре Блума

Не хранит сами данные (например, список id). Хранит информацию в битовом массиве (создаётся в оперативной памяти RAM). Это компактное представление множества.
Не знает ничего напрямую о добавленных элементах.
У него есть только массив битов (позиции, которые связаны с добавленными элементами) и хэш-функции (для поиска индексов).

Как выбрать параметры

Размер битового массива (m) → влияет на вероятность ложноположительных срабатываний. Количество хэш-функций (k) → влияет на баланс между точностью и скоростью.

Чем больше m и k, тем выше точность, но больше памяти требуется. Оптимальные значения выбираются в зависимости от ожидаемого числа элементов и допустимого уровня ошибок.

Примеры применения

В БД:
- Для ускорения поиска записей без полного сканирования таблиц.
- В индексах для предварительной проверки наличия ключа.
В веб-приложениях для быстрой проверки, есть ли объект в кэше, без полного перебора.
В блокировке спама для проверки, был ли email уже отправлен.
Для уменьшения сетевых запросов (в Cassandra или Redis) для предварительной проверки наличия данных на узле. Если фильтр говорит "данных нет", система не делает запрос к этому узлу.
В CDN (Content Delivery Network) для проверки, есть ли контент на edge-сервере.

В системах

Google Bigtable → использует фильтр Блума для ускорения поиска данных.
Apache Cassandra → проверяет, есть ли ключ в SSTable перед загрузкой с диска.
Bitcoin и блокчейн → фильтрация транзакций в P2P-сетях.

Альтернативы

Counting Bloom Filter (Фильтр Блума с подсчетом) → позволяет удалять элементы.
Cuckoo Filter (Кукушкин фильтр) → имеет более низкую вероятность ошибок и поддерживает удаление.
HyperLogLog → используется для подсчёта количества уникальных элементов.

Недостатки и ограничения

Стандартный фильтр Блума не поддерживает удаление элементов (есть модификации, например, Counting Bloom Filter).
Может ошибаться из-за коллизий хэш-функций: некоторые индексы в массиве могут пересекаться (коллизии).
- Пример:
  - "12345" ставит 1 на позициях [2, 5, 7].
  - "67890" ставит 1 на позициях [5, 7, 8].
  - Фильтр может ошибочно считать, что элемент есть, хотя его нет.
Не подходит, если нужна точность 100%.
Если фильтр переполняется, ложноположительные срабатывания становятся слишком частыми.