Что такое фильтр Блума и где он применяется?

Фильтр Блума — вероятностное множество из битового массива и k хеш-функций: на вопрос «есть ли элемент?» он отвечает «точно нет» или «возможно, да», занимая около 10 бит на элемент независимо от размера самих ключей.

Как работает

• Добавление: вычислить k хешей и выставить k битов.
• Проверка: если хоть один из k битов равен 0, элемента точно нет; если все единицы — возможно ложное срабатывание.
• Ложных отрицаний не бывает, ложные положительные — да.
• Удалить элемент нельзя: сброс бита затронет чужие элементы. Для удаления есть counting Bloom filter со счётчиками вместо битов.

Числа

• Вероятность ложного срабатывания ≈ (1 − e^(−kn/m))^k, где m — битов, n — элементов.
• Оптимальное k = (m/n)·ln 2.
• 1 % ошибок — около 9,6 бита на элемент и k = 7; каждое десятикратное снижение ошибки стоит ещё ≈4,8 бита на элемент.
• Вместо k независимых функций хватает двух: gᵢ = h₁ + i·h₂ (приём Кирша — Митценмахера).

Где применяется

• LSM-хранилища (RocksDB, Cassandra, HBase): перед чтением SSTable с диска проверить, может ли там быть ключ.
• CDN: не кешировать объект при первом запросе, чтобы не тратить диск на единичные обращения.
• Проверка «этот пароль в утечках?» или «URL уже обходили?» без хранения всего списка.

Коротко для собеседования

Фильтр Блума экономно отвечает «точно нет» или «возможно, да» и ставится перед дорогой проверкой — например, перед чтением с диска в LSM-хранилищах. Ложных отрицаний нет, но удалять элементы и расширять фильтр без исходных ключей нельзя, поэтому размер закладывают заранее.