Bloom Filter

Вероятностная структура данных для проверки принадлежности элемента к множеству, которая может давать ложноположительные ответы, но не дает ложноотрицательных; очень компактна по памяти; используется перед обращением к “тяжелому” хранилищу, чтобы проверить отсутствие элемента (например, нет ли ключа в БД) и избежать лишней операции; ложноположительный процент настраивается размером фильтра; широко применяется в кешах, распределенных БД (Cassandra) для ускорения пропускной способности.