Build a Bloom FilterStep 2 of 5

add and contains

12345

Step 2: add and contains

Now the two operations that matter:

  • add(item): set the bit at each of the item's _indices
  • contains(item): return True only if all of the item's bit positions are set

The asymmetry is the whole idea: if any bit is 0, the item was definitely never added; if all are 1, it was probably added (they could have been set by other items, a false positive).

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):
        """Set every bit position for this item."""
        # TODO: for idx in self._indices(item): set that bit to 1
        pass

    def contains(self, item):
        """True only if ALL of the item's bit positions are set."""
        # TODO: return whether every idx in self._indices(item) has a 1 bit
        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