Информатика / Алгоритмы и анализ данных

Фильтр Блума: вероятность ложного срабатывания

Фильтр Блума допускает ложноположительный ответ о наличии элемента. В стандартной вероятностной модели его частоту оценивают через число битов m, хеш-функций k и вставленных элементов n.

Опубликовано: 6 ноября 2026 г.Обновлено: 6 ноября 2026 г.

Формула

p_{\mathrm{FP}}\approx\left(1-e^{-kn/m}\right)^k

Схема Память и ложноположительный ответ

При n=100,k=4: оценка для 1000 и 2000 битов. Вероятности показаны долями, не процентами.

Обозначения

$m$: число битов фильтра, бит
$k$: число равномерных хеш-позиций на элемент, шт.
$n$: число вставленных различных элементов, шт.
$p_FP$: вероятность ложноположительного запроса отсутствующего элемента, доля

Условия применения

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

Ограничения

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

Подробное объяснение

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

Увеличение m уменьшает коллизии, а слишком большое k может снова повысить p, потому что быстрее заполняет массив. Оптимальное k примерно равно (m/n)ln2.

Фильтр не хранит сами ключи и не поддерживает обычное удаление: сброс одного бита может испортить другие записи. Для удаления применяют счётчики.

Формула является приближением при независимых равномерных хешах; конкретная реализация может иметь корреляции и другой уровень ошибки. Для контроля решения полезно отдельно выписать исходную модель, вычислить промежуточные величины и проверить, что финальный ответ имеет ожидаемый масштаб.

Увеличение k при неизменных m,n одновременно усиливает проверку и быстрее заполняет массив. Поэтому зависимость не монотонна по числу хешей: в приближённой модели оптимум находится около(m/n)ln2, после чего нужно сравнить ближайшие целые значения k.

Как пользоваться формулой

Укажите размер массива m, число различных вставленных элементов n и количество хеш-позиций k; проверьте модель равномерных хешей.
Найдите среднюю загрузку kn/m и оцените вероятность единичного бита как 1−exp(−kn/m), не путая её с частотой ложного ответа.
Возведите оценку доли единиц в степень k, поскольку для ложного положительного ответа должны совпасть все проверяемые биты.
Сравните несколько целых k и размеров m, затем проверьте реальную реализацию на независимых отсутствующих элементах.

Историческая справка

Бёртон Блум описал вероятностную структуру в статье «Space/Time Trade-offs in Hash Coding with Allowable Errors», опубликованной в 1970 году. Постановка допускает ошибки одного направления ради сокращения памяти и времени проверки принадлежности.

Современные курсы алгоритмов объясняют фильтр через занятость битов после случайных хеш-вставок. Приближение exp(−kn/m) появляется из вероятности не затронуть отдельную позицию множеством независимых обращений. Историческое название структуры не означает, что любая простая степенная оценка является точным результатом исходной работы: конечный массив и зависимость позиций требуют различать модель, приближение и фактическую реализацию.

Историческая линия формулы

Структура носит имя Бёртона Блума и связана с его публикацией 1970 года. Здесь используется распространённая приближённая оценка ложноположительной вероятности. Условия равномерного хеширования и отсутствие обычного удаления являются частью рассматриваемой модели.

Пример

Пусть m=1000 бит, n=100 различных вставленных элементов, k=4. Средняя загрузка kn/m=0,4. По модели вероятность единицы примерно 1−e^(−0,4)≈0,32967995. Ложноположительный ответ требует единиц во всех четырёх позициях: p_FP≈0,32967995⁴≈0,01181327. Ответ: примерно 1,1813% запросов отсутствующих элементов. Это не доля занятых битов, которая составляет около 32,968%. Проверка увеличением памяти: при m=2000 и тех же k,n загрузка 0,2, оценка ложного ответа(1−e^(−0,2))⁴≈0,0010796836, около 0,1080%. Уменьшение вероятности соответствует более разреженному массиву; конкретная реализация должна подтвердить расчёт экспериментом.

Частая ошибка

Не принимайте долю единичных битов за вероятность ложного ответа: нужно учитывать все k проверок. Не обещайте точную частоту по приближённой модели. Не обнуляйте биты для удаления элемента из обычного фильтра: они могут принадлежать другим вставкам. Не трактуйте положительный ответ как доказательство наличия элемента.

Практика

Задачи с решением

Четыре хеша

Условие. m=1000,n=100,k=4. Найдите оценку ложноположительной вероятности.

Решение. (1−e^(−0,4))⁴≈0,0118132709.

Ответ. Около 1,1813%.

Больше памяти

Условие. m=2000,n=100,k=4. Найдите оценку и сравните с первым случаем.

Решение. (1−e^(−0,2))⁴≈0,0010796836, что меньше оценки при 1000 битах.

Ответ. Около 0,1080%.

Дополнительные источники

https://doi.org/10.1145/362686.362692
https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750-s21/www/notes/lec8-slides.pdf

Связанные формулы

Математика

Задача коллекционера купонов: среднее время полной коллекции

$\mathbb E[T]=nH_n=n\sum_{j=1}^{n}\frac1j$

Если каждый из n типов купонов появляется независимо и равновероятно, среднее число покупок для полной коллекции равно nH_n. Последние недостающие типы дают основную задержку.

Математика

Вероятность в биномиальном распределении

$P(X=k)=C_n^kp^k(1-p)^{n-k}$

Формула «Вероятность в биномиальном распределении» задает численную характеристику вероятностной модели. Она переводит исходы, вероятности или наблюдения в показатель, который удобно считать, сравнивать и проверять.

Математика

Граница Буля—Бонферрони для объединения событий

$\Pr\!\left(\bigcup_{i=1}^{m}A_i\right)\le\min\!\left(1,\sum_{i=1}^{m}\Pr(A_i)\right)$

Вероятность хотя бы одного из нескольких событий не превосходит суммы их вероятностей. Граница работает без независимости и позволяет контролировать общую ошибку по отдельным рискам.