Bloom filter

Если нужно быстро и с малым количеством памяти проверить, есть ли элемент в каком-то списке (например, емейл в блеклисте), можно использовать Bloom filter. Этот алгоритм умеет выдавать два ответа: "этого элемента точно нет" и "этот элемент возможно есть".

Как он работает:

Выделяется массив бит длиной m (чем больше m, тем меньше ложноположительных срабатываний).

Далее, по каждому элементу списка пробегаемся и вычисляем несколько хеш функций (разных, и желательно быстро работающих). Результат хеш-функции - это некое число. Если взять остаток от деления на m, то получим позицию бита.

Короче, для каждой хеш функции выставляем в итоге бит в 1.

И так каждый элемент списка: выставит свои биты в 1, некоторые будут совпадать с другими элементами.

Проверка на вхождение элемента в список

точно также, вычисляем теми же хеш фунциями позиции битов и смотрим, что там, в этих позициях.

Если хотя бы один бит равен 0, то этот элемент точно отсутствует в списке. Если все 1, то возможно присутствует.

Элементарно и эффективно.

Хеш-функций нужно несколько, чтобы уменьшить вероятность ложноположительных ситуаций.

Количество требуемой памяти и оптимальное количество хеш-функций вычисляется по простым формулам (можно найти в Википедии), исходя из требуемой вероятности ложно-положительного срабатывания и количества элементов в списке.

Особенности фильтра:

Вы сами задаёте количество памяти исходя из требуемого качества.

Работает за константное время O(1)

Из него невозможно удалить значения. Лишь пересобрать полностью заново.

Можно разные фильтры объединять в один простым побитовым ИЛИ

🫥 Cross Join - канал о разработке