Bloom Filters

The read path probes SSTables newest-first — and for keys that do not exist, it probes every one of them for nothing. A Bloom filter is the fix: a tiny bitmap attached to each SSTable that answers "could key X be in this file?" with one of two verdicts — MAYBE (go read the file) or NO (skip it, guaranteed). It can be wrong in only one direction: false positives happen; false negatives never do.

Mechanics

An m-bit array, initially all zeros, plus k hash functions. To add an item, set the k bits its hashes select. To query, inspect those same k bits: any zero → the item was never added → NO; all ones → MAYBE (other items may have set those bits between them).

Deletion is impossible: clearing a bit might destroy evidence of other items sharing it. (Cuckoo filters store fingerprints instead and support deletes; SSTables do not care — each immutable file gets a freshly built filter.)

The false-positive math

With n items in m bits under k hashes, a lookup of an absent key tests k pseudo-random bits; each is set with probability about 1 − e^(−kn/m), so:

P(false positive) ≈ (1 − e^(−kn/m))^k

Minimizing over k gives the optimal hash count k ≈ (m/n)·ln 2 ≈ 0.7·(m/n). At the industry-standard 10 bits per key that lands at k ≈ 7 and an FP rate near 1% — which is why RocksDB's default filter budget is ~10 bits/key. This exercise's config (m=100, k=3) holding three keys gives (1 − e^(−9/100))^3 ≈ 0.0006: absent keys are essentially always rejected.

Double hashing: k functions from two

Nobody computes 7 independent hashes. The Kirsch–Mitzenmacher construction synthesizes them all from two:

hash_i(s) = (h1(s) + i · h2(s)) mod m,   for i = 0 … k−1

This exercise pins the base hashes exactly (everything mod 100):

Note that i starts at 0 — so hash_0 is plain h1 — and that h2 weights each byte by its position plus one. Worked example: apple has byte sum 530, so h1=30; weighted sum 1594, so h2=94; its bits are {30, 24, 18}. banana maps to {9, 51, 93} — disjoint from apple's bits, which is why checking banana after adding only apple answers NO.

Your exercise

Implement BLOOM-NEW, BLOOM-ADD, BLOOM-CHECK, BLOOM-BITS. The grader-caught mistakes, from the real tests: (1) reset semantics — BLOOM-ADD apple, then BLOOM-NEW, then BLOOM-CHECK apple must print NO; a BLOOM-NEW that fails to zero the array prints MAYBE and fails the hidden test; (2) verdict tokens are exactly MAYBE and NO — and an empty filter answers NO to everything, since every bit is zero; (3) BLOOM-BITS prints the whole array as one line of exactly 100 characters — the fresh-filter hidden test expects one hundred 0s, no spaces, no truncation; (4) a check requires all three bits set — testing any of them inflates MAYBEs: after adding foo, bar, baz, the check on qux must still print NO.