Bloom False Positive Probability

Problem

Compute the theoretical false positive probability of a Bloom filter.

For m bits, k hash functions, and n inserted items the probability is (1 - (1 - 1/m)^(k*n))^k, assuming uniform independent hashing. A non-positive bit count returns 1.0.

Return the probability as a float.

Hint

Each of the k bits is set with probability 1 - (1 - 1/m)^(k*n).

Test cases

case 1

in: [100,3,10]

expected: 0.017636834329119114

case 2

in: [10,1,5]

expected: 0.40950999999999993

case 3

in: [1000,7,100]

expected: 0.008213554634050255

case 4

in: [10,1,0]

expected: 0

case 5

in: [0,1,1]

expected: 1

Starter codePython

def bloom_false_positive_probability(num_bits, num_hashes, num_items):
    # Your code here
    pass

5 test cases · run your code against them in the editor