A Bloom filter

Build the Bloom filter from lesson 8. It has m bits and uses k positions per word. The two hash functions h1 and h2 are given in the starter code. The positions for a word are

(h1(word) + i * h2(word)) % m      for i = 0, 1, …, k − 1

This trick, called double hashing, makes k positions from just two hash values.

• add(word) sets the word’s k bits to 1.
• might_contain(word) is True only if all k of its bits are 1.
• bits() lists the positions that are 1, smallest first.
• false_rate(n) returns the expected false positive rate after n words (lesson 8). In Python it is (1 - math.exp(-k * n / m)) ** k. Here math.exp(x) is the number e (about 2.718) raised to the power x, and ** k raises the result to the power k.

B = Bloom(16, 3)
B.add('cat'); B.add('dog'); B.add('owl')
B.bits()                  # [0, 2, 3, 4, 6, 10, 11, 12]
B.might_contain('fox')    # False
B.might_contain('bee')    # True: a false positive

Store bits, not words: the tests check that false positives happen exactly where they should.

The tests make an object and call its methods in order. A test shows the list of calls, and compares the list of everything they returned (methods that return nothing give None).

Limits

• Up to 1,000,000 bits and 100,000 words.