Bloom filter

Прошлый пост получил нереальное количество огонёчков, было супер приятно, спасибо за реакции❤️

Сегодня начну серию постов "компутер саенс лайт".

Расскажу о структурах данных, которые используются в популярных библиотеках. Вряд ли вы будете писать их самостоятельно, но полезно понимать, зачем они нужны. Плюс это очень интересно:)

Первый участник — Bloom filter (фильтр Блума). Помогает узнать, есть элемент во множестве или нет.

❓ Зачем нужна отдельная структура, когда есть метод contains?

В LinkedList contains последовательно обходит коллекцию, даже если элементы отсортированы. Это долго, сложность такого подхода составляет O(n). В бинарном дереве contains выполнится быстрее, за O(log n).

Но есть ситуации, когда даже такой поиск нежелателен: данных очень много, они не отсортированы или хранятся на диске. В этих случаях проверка займёт уйму времени.

Здесь на помощь приходит Bloom filter — вероятностная структура данных для быстрого contains. Если фильтр вернул

▫️ true — элемент скорее всего есть. Но может и нет
▫️ false — элемента 100% нет

Более формально: это структура с возможным false positive ответом

Принцип работы

В основе лежит bitSet, набор битов. Возьмём для примера bitSet длиной 8:

00000000

Чтобы добавить в фильтр элемент Х:

☝️ Считаем хэш тремя разными функциями, получаем H1, H2, H3
✌️ Вычисляем индексы в bitSet. Берём остаток от деления H1, H2, H3 на 8. Пусть это будет 0, 2 и 3
💅 Обновляем соответствующие индексы в фильтре. Получится
10110000

Повторяем для всех элементов списка/дерева/множества/etc.

Как проверить, был ли добавлен элемент в фильтр?

🔸 Считаем хэш элемента 3 функциями
🔸 Получаем 3 индекса и считываем биты
🔸 Если среди них хотя бы один 0, значит элемента в фильтре нет

Здесь можно поиграться и углубиться в детали.

Фильтры Блума активно используются в базах данных, роутерах, при проверке чёрных списков. Много примеров ищите здесь.

Готовая реализация BloomFilter есть в библиотеке Google Guavа.

❓ Как возможны false positive результаты? Если фильтр вернул true, почему элемента Х может не быть?

Другие элементы могут занять индексы, которые используются для проверки элемента Х. Поэтому фильтр вернёт true, хотя Х не был добавлен.

❓ Как размер фильтра влияет на вероятность false positive ответов?

Чем больше размер фильтра, тем ниже шанс, что индексы элементов будут пересекаться. Вероятность false positive снижается, но увеличивается размер занятой памяти.