Given a bloom filter of size N-bits and K hash functions, of which M-bits (where M <= N) of the filter are set.Is it possible to approximate the number of elements inserted into the bloom filter?Simple ExampleI've been mulling over the following example, assuming a BF of 100-bits and 5 hash functions where 10-bits are set...Best case scenario: Assuming the hash functions are really perfect and uniquely map a bit for some X number of values, then given 10-bits have been set we can say that there has only been 2 elements inserted into the BFWorst case scenario: Assuming the hash functions are bad and consistently map to the same bit (yet unique amongst each other), then we can say 10 elements have been inserted into the BFThe range seems to be [2,10] where abouts in this range is probably determined by the false-positive probability of filter - I'm stuck at this point.
Computing the approximate population of a bloom filter
ds.data structures;pr.probability