Изменения

Перейти к: навигация, поиск

Фильтр Блума

11 байт убрано, 15:50, 30 апреля 2012
Описание структуры данных
Для добавления элемента <tex> e </tex> необходимо записать единицы на каждую из позиций <tex>h_1(e) \dots h_k(e)</tex> битового массива.
Чтобы проверить, что элемент <tex>e</tex> принадлежит множеству хранимых элементов, необходимо проверить состояние битов <tex> h_1(e) \dots h_k(e) </tex>. Если хотя бы один из них равен нулю, элемент не принадлежит множеству. Если все они равны единице, то структура данных сообщает, что элемент принадлежит множеству. При этом может возникнуть две ситуации: либо элемент действительно принадлежит к множеству, либо все эти биты оказались установлены по случайности случайно при добавлении других элементов, что и является источником ложных срабатываний в этой структуре данных.
== Минимизация вероятности ложноположительного срабатывания ==
403
правки

Навигация