Build a Bloom FilterStep 3 of 5

Fill Metrics

12345

Step 3: Fill Metrics

How "full" the filter is drives its accuracy, the more bits set, the more likely a random lookup collides into a false positive. Expose two metrics:

  • count_set_bits(): how many bits are 1
  • fill_ratio(): the fraction of bits set (count_set_bits / size)

Adding the same item twice must not change either number. The bits were already 1.

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):
        """Number of bits currently set to 1."""
        # TODO
        pass

    def fill_ratio(self):
        """Fraction of the bit array that is set (0.0 to 1.0)."""
        # TODO
        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.

PreviousNext step