Предположим, что API-интерфейс фильтра Блума имеет 2 параметра: 1. количество битов в фильтре Блума (n) и 2. ожидаемое количество вставок (m).
Будет ли m > n всегда приводить к complete ложным срабатываниям? Под complete я хочу сказать, будет ли каждый тест для метода «содержит (элемент)» возвращать true после условия m > n?
Фильтр Блума всегда ответит «да» не тогда, когда ваше m > n, а когда все n его битов равны 1 — тогда каждый запрос из h позиций (где h — количество хэш-функций) даст h 1 с. Тем не менее, типичная настройка, которая оптимизирует компромисс между пространством и частотой ложных срабатываний, — это когда вероятность установки любого бита составляет 1/2. Анализ показан в статье Википедии о фильтре Блума: http://en.wikipedia.org/wiki/Bloom_filter< /а>
