Фільтр Блума — це компактна імовірнісна структура, що відповідає на одне питання: «чи є цей елемент у множині?» Він використовує масив із m бітів і k геш-функцій, не зберігаючи жодного елемента.

Додавання елемента

Гешуємо елемент усіма k функціями, щоб отримати k позицій у [0, m), і встановлюємо ці біти в 1. Біти ніколи не скидаються.

Запит елемента

• Якщо будь-який із k бітів дорівнює 0 → точно немає в множині.
• Якщо усі k бітів дорівнюють 1 → можливо є в множині.

Оскільки встановлені біти ніколи не скидаються, справжній член завжди проходить — тож хибнонегативних немає. Але через колізії не-член може здаватися наявним: це хибнопозитивна відповідь.

Частота помилок

Після вставлення n елементів імовірність того, що випадковий не-член дасть усі одиниці, приблизно дорівнює (1 − e^(−kn/m))^k. Доданок e^(−kn/m) оцінює частку бітів, що досі є 0.

Налаштування k та m

Похибка мінімізується при k = (m/n)·ln 2, а цільова частота p потребує m = −n·ln p / (ln 2)² бітів — близько 9,6 біта на елемент для 1%.