На хабре уже немало рассказано про фильтр Блума. Напомню, что это структура данных, которая позволяет проверить принадлежность элемента ко множеству, не храня при этом сам элемент. Существует вероятность ложно-положительного ответа, но отрицательный ответ всегда достоверен. В фильтре с точностью 1% требуется всего лишь несколько бит на элемент.
Эта структура часто применяется для ограничения числа запросов к хранилищу данных, отсекая обращения за элементами, которых там заведомо нет. Кроме того, её можно применять для примерного подсчёта числа уникальных событий, пользователей, просмотров и т.д. Больше примеров интересных применений.
Однако есть трудности, которые могут сдерживать веб-разработчиков от применения фильтра Блума.
Читать полностью »