🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Bloom Filter 🎲 – вероятностная структура данных, которая за константное время отвечает, точно ли элемента нет в множестве или он там, вероятно, есть.
Аналогия: охранник со списком примет отпечатков – «этого точно не было» говорит уверенно, а «был» иногда путает с похожим.
⚡️ Ключевые особенности:
- Битовый массив – хранит миллионы элементов в килобайтах памяти
- Хеш-функции – несколько независимых хешей ставят биты на позиции элемента
- Односторонняя ошибка – ложноположительные срабатывания есть, ложноотрицательных нет
- Без удаления – классическая версия умеет только добавлять
💡 Кто использует:
Cassandra и ClickHouse отсекают лишние чтения с диска, браузеры и CDN – проверку по спискам. Классика там, где память дороже точности.
🚀 Результат: Bloom-фильтр = дешёвый фильтр перед дорогой проверкой. Килобайты вместо гигабайтов 🧠✨
#Term | Гайды Программиста