Фильтр Блума
Вероятностная структура данных для вопроса «есть ли элемент в множестве?» — отвечает «возможно» или «точно нет». Ложноотрицательных нет, доля ложноположительных настраивается.
Бёртон Блум, 1970 год. Битовый массив и k хеш-функций. Крайне экономен по памяти: 1 % ложноположительных — это около 10 бит на элемент независимо от размера элемента. Применяется в SPV-узлах Bitcoin, построчных фильтрах BigTable/HBase, проверках наличия в кэше CDN, списках вредоносных URL в браузерах. Современная альтернатива — фильтры Кукушки (2014), поддерживающие удаление.