Build a Bloom FilterStep 1 of 5

Bit Array & Hashing

12345

Step 1: Bit Array & Hashing

A Bloom filter is a bit array plus k hash functions. Each item maps to k positions; membership is "are all k bits set?". No per-item storage. Just bits, which is why it's so compact.

To keep tests deterministic, an optional hash_fn(item, i) is injected; tests pass a simple one so the positions are predictable.

Implement the primitives:

  • _indices(item): the list of num_hashes bit positions for an item (call hash_fn(item, i) for each i, or the default hasher)
  • _set_bit(i) / _get_bit(i): set a bit to 1 / read a bit

The default hasher is provided; _indices just needs to gather the num_hashes positions.

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          # hash_fn(item, i) -> index, or None for default
        self._bits = bytearray(size)    # size bytes, each 0 or 1

    def _indices(self, item):
        """The list of num_hashes bit positions for item."""
        # TODO: for each i in range(self.num_hashes), compute a position.
        #   if self.hash_fn is not None: use self.hash_fn(item, i)
        #   else: use _default_hash(item, i, self.size)
        pass

    def _set_bit(self, i):
        """Set bit i to 1."""
        # TODO
        pass

    def _get_bit(self, i):
        """Return bit i (0 or 1)."""
        # 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.

OverviewNext step