Изменения

Чтобы проверить что элемент <tex>e</tex> принадлежит множеству хранимых элементов, необходимо проверить состояние битов <tex>h_1(e)</tex>, …, <tex>h_k(e)</tex>. Если хотя бы один из них равен нулю, элемент не принадлежит множеству. Если все они равны единице, то структура данных сообщает, что <tex>е</tex> принадлежит множеству. При этом может возникнуть две ситуации: либо элемент действительно принадлежит к множеству, либо все эти биты оказались установлены по случайности при добавлении других элементов, что и является источником ложных срабатываний в этой структуре данных.

Пусть размер битового массива <tex>m</tex> и задано <tex>k</tex> хеш-функций таких, что каждая из них назначает место элементу <tex>x</tex> в битовом массиве с равной вероятностью:

<tex dpi = "150">k = \frac mn ln(2) </tex>