Bloom

Фильтр Блума (англ. Bloom filter) — это вероятностная структура данных, придуманная Бёртоном Блумом в 1970 году^[1], позволяющая компактно хранить множество элементов и проверять принадлежность заданного элемента к множеству. При этом существует возможность получить ложноположительное срабатывание(элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное.

[1] Bloom, Burton H. (1970), "Space/time trade-offs in hash coding with allowable errors", Communications of the ACM Т. 13 (7): 422–426