Фильтры Блума и вероятностные структуры данных

Коротко: Фильтр Блума экономно проверяет, может ли элемент находиться в множестве. Он отвечает либо «точно нет», либо «вероятно да», но никогда не говорит «нет» ошибочно.

Подробнее: Фильтр — битовый массив с несколькими хеш-функциями. При вставке устанавливаются k битов; при поиске должны быть установлены все k битов. Возможны ложноположительные срабатывания, ложноотрицательные — нет. Удаление невозможно (кроме вариантов со счётчиками).