Optimal Bloom Hash Count

Problem

Return the optimal number of hash functions for a Bloom filter with num_bits bits holding num_items items.

Minimizing the false positive rate gives round((m / n) * ln 2), clamped to at least 1. Non-positive bit or item counts also return 1.

Hint

The optimal k grows linearly with bits per item, at roughly 0.69 hashes per bit.

case 1

in: [1000,100]

expected: 7

case 2

in: [100,100]

expected: 1

case 3

in: [2000,100]

expected: 14

case 4

in: [10,0]

expected: 1

case 5

in: [50,10]

expected: 3

Starter codePython

import math


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

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