Build a Bloom FilterStep 5 of 5

False-Positive Rate & Guarantees

12345

Step 5: False-Positive Rate & Guarantees

The headline property: a Bloom filter never returns a false negative (if you added it, contains is always True), but it can return a false positive. The probability of a false positive, given the current fill, is approximately:

false_positive_rate = fill_ratio ** num_hashes

Implement:

  • false_positive_rate(): fill_ratio() raised to the power num_hashes

The tests also confirm the two guarantees: every added item is found, and a collision can make an un-added item report as present.

Hints
Starter code
import hashlib


def _default_hash(item, i, size):
    return int(hashlib.md5(f"{i}:{item}".encode()).hexdigest(), 16) % size


class BloomFilter:
    def __init__(self, size, num_hashes, hash_fn=None):
        self.size = size
        self.num_hashes = num_hashes
        self.hash_fn = hash_fn
        self._bits = bytearray(size)

    def _indices(self, item):
        if self.hash_fn is not None:
            return [self.hash_fn(item, i) for i in range(self.num_hashes)]
        return [_default_hash(item, i, self.size) for i in range(self.num_hashes)]

    def add(self, item):
        for idx in self._indices(item):
            self._bits[idx] = 1

    def contains(self, item):
        return all(self._bits[idx] for idx in self._indices(item))

    def count_set_bits(self):
        return sum(self._bits)

    def fill_ratio(self):
        return self.count_set_bits() / self.size

    def false_positive_rate(self):
        """Approximate false-positive probability at the current fill."""
        # TODO: return self.fill_ratio() ** self.num_hashes
        pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousAll challenges