19
правок
Изменения
→Описание структуры данных: добавлено преимущество фильтра Блума. то бишь ответ на вопрос "А зачем нужна такая структура данных?"
Чтобы проверить, что элемент <tex>e</tex> принадлежит множеству хранимых элементов, необходимо проверить состояние битов <tex> h_1(e) \dots h_k(e) </tex>. Если хотя бы один из них равен нулю, элемент не принадлежит множеству. Если все они равны единице, то структура данных сообщает, что элемент принадлежит множеству. При этом может возникнуть две ситуации: либо элемент действительно принадлежит к множеству, либо все эти биты оказались установлены при добавлении других элементов, что и является источником ложных срабатываний в этой структуре данных.
По сравнению с [[Хеш-таблица|хеш-таблицами]], фильтр Блума может обходиться на несколько порядков меньшими объёмами памяти, жертвуя детерминизмом. Обычно он используется для уменьшения числа запросов к несуществующим данным в структуре данных с более дорогостоящим доступом (например, расположенной на жестком диске или в сетевой базе данных), то есть для «фильтрации» запросов к ней.
== Минимизация вероятности ложноположительного срабатывания ==
