Как работает фильтр Блума и когда его неточность экономит память

Фильтр Блума сообщает: «элемента точно нет» или «элемент, возможно, есть». Ложные срабатывания допустимы, но добавленное значение он не пропускает. Так можно отсечь часть запросов перед точной проверкой.

В обстоятельном разборе Bloom Filters при добавлении значения хеш-функции выбирают позиции в битовом массиве и записывают в них единицы. Совпадение всех позиций означает «возможно». Автор объясняет, как заполнение повышает долю ложных срабатываний, как подобрать размер массива и число функций, почему удаление может стереть следы других значений.

В примере список из миллиона вредоносных ссылок занимает 20 МБ. Фильтр с одним ложным срабатыванием на миллион проверок занимает 3,59 МБ, на 82% меньше; ответ «возможно» можно сверить с полной базой через API. Для отсева заранее оцените объём данных и приемлемую долю ошибок.