Фильтр Блума — это пространственно-эффективная вероятностная структура, которая отвечает на вопросы о принадлежности к множеству с одним нюансом: она может давать ложные срабатывания, но никогда ложные пропуски. "Определённо отсутствует" — это уверенность; "возможно присутствует" требует проверки.
Как это работает
Битовый массив из бит и хеширующих функций. Чтобы элемент, установите бит, на которые он хешируется. Чтобы , проверьте эти бит — если какой-то равен 0, элемента определённо нет.
