Bloom Filter False Positive Model

Problem

Compute the asymptotic false positive rate of a Bloom filter with num_bits bits, num_hashes hash functions, and num_items inserted.

Use the exponential approximation (1 - e ** (-k * n / m)) ** k. A non-positive bit count or hash count returns 1.0, and inserting no items returns 0.0.

Hint

A bit is still zero after all insertions with probability e ** (-k * n / m).

Test cases

case 1

in: [100,3,10]

expected: 0.017410586496326586

case 2

in: [1000,7,100]

expected: 0.008193722065862417

case 3

in: [10,1,5]

expected: 0.3934693402873666

case 4

in: [10,1,0]

expected: 0

case 5

in: [0,3,10]

expected: 1

Starter codePython

import math


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

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