🔍Фильтр Блума

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


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


Как работает?

🟢создается битовый массив длины m
🟢он состоит из 0 и 1
🟢изначально массив выглядит так: [0, 0, 0, 0, 0, 0, 0, 0]
🟢каждая позиция (индекс) в этом массиве и значения (0, 1) — всё, что фильтр "запоминает"

🍃Добавляется элемент

Например, id со значением 12345
1⃣Фильтр пропускает id через несколько хэш-функций
Хэш-функция — математический алгоритм, который превращает строку ("12345") в числа (индексы массива), например:
- hash_1("12345") → 2
- hash_2("12345") → 5
- hash_3("12345") → 7
2⃣ Фильтр "ставит галочки" на этих позициях, т.е. устанавливает биты на этих индексах = 1:
[0, 0, 1, 0, 0, 1, 0, 1]
Фильтр запоминает, что на позициях [2, 5, 7] что-то есть

🍃Проверка элемента

Чтобы узнать есть ли id = 54321 в фильтре Блума
id снова пропускается его через те же хэш-функции:
- 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). Это компактное представление множества
❌ не знает ничего напрямую о добавленных элементах

❗️У него есть только массив битов (позиции, которые связаны с добавленными элементами) и хэш-функции (для поиска индексов)


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

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


Недостатки

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


📎 Материалы
1. Что такое фильтр Блума?
2. Фильтр Блума: зачем нужен и как работает
3. Что такое фильтр Блума и как он работает на практике (с примерами)
4. Что такое фильтр Блума в Blockchain?
5. Вероятностные структуры данных и где они обитают
6. Фильтр Блума – вероятностная структура данных для проверки принадлежности элемента множеству
7. Просто о сложном: что фильтрует фильтр Блума?
8. Фильтр Блума
9. Когда фильтр Блума не подходит

#инфраструктура

➿➿➿➿➿➿➿➿

🧑‍🎓 Больше полезного в базе знаний по системному анализу