Ни одного ложноотрицательного: пишем Фильтр Блума на C

Представьте: вы пишете парсер, который обходит сотни миллионов URL. Каждую новую ссылку нужно проверить — посещали ли мы её раньше? Заводить гигабайтный хеш-набор для хранения всех адресов — расточительно и медленно.

Но существует вероятностная структура данных, которая способна ответить на вопрос «видели ли мы этот URL?», занимая при этом в десятки раз меньше памяти, чем полное множество строк. Плата за такое — мизерная возможность ложноположительного срабатывания, где фильтр заявит что, хотя на самом деле URL новый. Зато на вопрос «не видели?» она не ошибётся никогда.

Это и есть Фильтр Блума, созданный Бёртоном Блумом аж в 1970 году. Более полсотни лет этому алгоритму! В принципе, никогда не помешает освежить знания и вспомнить, как писать реально оптимизированное ПО.