Probabilistic Data Structures: A Bloom Filter You Can Trust

BloomFilter offers Add / Contains in Go and add / contains in Python. Its useful guarantee is one-sided: a negative lookup rules a key out; a positive lookup asks an exact store to finish the decision. Prepare by tracing integer hashes modulo an array size and explain why two keys can share a cell.

Work the shared-bit history

With m=10 positions and k=3 hashes, start with all positions clear. For this hand example, assume these positions (they are not the exercise helper's output):

Operation	Positions	Set positions afterward	Result
Add apple	2,5,7	{2,5,7}	—
Add banana	1,5,9	{1,2,5,7,9}	—
Contains cherry	2,4,7	unchanged	false: position 4 is clear
Contains grape	1,5,7	unchanged	true: all set, although grape was not added

A position has no owner. No false negatives follows from an invariant: after insertion, every required position remains set. This assumes stable hashing, the same size and seeds for insertion and lookup, and no clearing or lost writes. Repeating an insertion is harmless; repeated hash positions within one insertion set the same cell again. A false positive is allowed, not a corrupted filter.

Clearing apple's positions would clear shared position 5 and turn banana into a false negative. A standard Bloom filter cannot delete this way. Counting filters replace bits with counters but require disciplined deletion and no overflow; decrementing for a key merely suspected present is unsafe. A Bloom hit cannot justify an authorization decision, suppress a required write, or prove that an item was processed: consult the authoritative membership record.

Match the scaffold before optimizing representation

The exercise's Go scaffold has size, k and bits []bool. The Python version uses a list of booleans. These are simple logical bit arrays, not packed bitsets: Go bool cells occupy a byte, and a Python list stores object references. The often quoted m-bit storage benefit describes a packed representation, not these scaffold layouts. Both use O(m) cells asymptotically, with different constants. The scaffold does not require a particular packed layout.

A packed alternative uses byte index p/8 and bit mask 1 << (p%8). Set with OR and test with AND. For m=10 it needs ceil(10/8)=2 bytes of bit payload; metadata and allocator overhead are additional. Do not silently switch representation and continue indexing as if each byte represented one position.

The constructor reference clamps nonpositive size or k to 1; the statement now makes this behavior explicit. An empty filter must return false even for the empty string. Insert and query must use the same position generator. The provided helpers are deterministic seeded FNV-style hashes; alternatives are allowed. No serialized format or cross-language hash equivalence is required. Use the exercise's helper rather than treating the hand example as test vectors.

Estimate error under stated assumptions

Under a model of independent uniform hash choices, a particular bit stays clear after n insertions with probability (1-1/m)^(kn), approximately exp(-kn/m). Treating queried bit occupancies as independent yields the familiar estimate:

false-positive rate ≈ (1 - exp(-k*n/m))^k
optimal real-valued k ≈ (m/n) * ln(2)

Choose a nearby positive integer k and compare; it is not a universal guarantee for arbitrary hashes and adversarial inputs. With 10 bits per inserted distinct key and k=7, the estimate is about 0.82%. More k is not always better: excess hashes fill bits faster. n is the planned population; overshooting it saturates the filter. Neither a tiny sample with zero false positives nor “several seeds” proves the target rate.

Double hashing generates positions (h1(x)+i*h2(x)) mod m. The Kirsch–Mitzenmacher paper proves an asymptotic false-positive result under its hash model. It does not certify that any chosen pair of deterministic hash functions behaves identically to independent random hashes at every finite size. For m=8 and h2=4, only two positions repeat; for h2=0, every generated position is the same. Avoid turning a theorem with assumptions into a blanket quality claim about the scaffold.

Count hash work as well as positions

If k positions are precomputed, setting/checking them takes O(k). The scaffold hashes an entire key separately for each seed, so for a key of L units its operation cost is O(k*(L+1)), with O(k) temporary positions. Go hashes UTF-8 bytes; the Python helper iterates string code points. Both still obey their own consistent membership contract. A double-hash implementation can hash the input twice and generate positions in O(L+k), subject to its quality assumptions.

A filter saves expensive negative lookups only when it is updated consistently with the backing store. Publishing a stored key before the filter knows it can produce a false negative at the system level, even if the data structure's insert-only code is perfect. For an immutable file, building and publishing the filter together with the file is a much simpler contract than asynchronous updates to a live exact set.

Finish a trace and design a falsification experiment

1. Start clear with 8 positions. A sets {1,3}, B sets {3,6}. C queries {1,6}. Predict C's result, then remove A by clearing its positions and predict B's result. Name the defect.
2. A packed array has m=17 positions. How many payload bytes are required, and which byte/mask represents position 16?
3. To estimate false positives, should inserted keys be in the denominator? What separate check establishes the no-false-negative invariant?

Check your reconstruction

1. C returns true despite being absent. Clearing A's positions clears shared 3, so B wrongly returns false. Ordinary deletion broke the invariant.
2. Three bytes. Position 16 is byte index 2, mask 1.
3. Query known-absent keys and divide false hits by absent queries. Separately verify that every inserted key remains positive after every insertion phase. Report sample size, hash configuration and workload; do not infer a universal error bound from one finite experiment.

Implement the exercise, including repeat insertions, empty strings and very small filters. Do not assert that every absent key must return false: that test would reject a legitimate Bloom filter. Later vary m while keeping the inserted population fixed and explain why the observed error rate might differ from the ideal estimate.