Даны фильтр Блюма размером N бит и K хэш-функций, из которых M бит (где M <= N) фильтра заданы.
Можно ли приблизительно определить количество элементов, вставляемых в фильтр Блюма?
Простой пример
Я размышлял над следующим примером, предполагающим BF размером 100 бит и 5 хэш-функций, из которых 10 бит установлены...
Наилучший сценарий: Если предположить, что хэш-функции действительно совершенны и однозначно отображают бит на некоторое X-число значений, то, учитывая, что было установлено 10 бит, можно сказать, что в БФ было вставлено только 2 элемента
Худший сценарий: Если предположить, что хэш-функции плохие и последовательно отображают один и тот же бит (но при этом уникальны между собой), то можно сказать, что в BF было вставлено 10 элементов
Диапазон, похоже, [2,10], где примерно в этом диапазоне, вероятно, определяется вероятностью ложного срабатывания фильтра - я застрял на этом моменте.