A Self-Tuning Bloom Filter

Combine the math from the FP-rate lesson with the Kirsch-Mitzenmacher hashing trick into a filter you can configure by intent ("hold ~100 items at 1% FP") rather than by raw m and k.

API

INIT  <expected_n> <target_fp>
    Compute m_opt and k_opt; allocate a fresh bit array.
    Output:  "OK m=<m> k=<k>"

ADD   <string>
CHECK <string>            -> MAYBE | NO

STATS
    m, k, current n_added, load (n_added/expected_n) to 4 decimals.

Implementation notes

• Compute m = ceil(-n * ln(p) / (ln(2)^2)) and k = round((m/n) * ln(2)). Floor k to 1 to avoid degenerate INIT.
• Reset everything on every INIT — including counters — so the filter can be re-initialized cleanly.
• Pack bits when memory matters. For this exercise a plain [0] * m is fine.
• The hashing uses the same h_a / h_b from the previous lesson, derived k times via the Kirsch-Mitzenmacher trick.

Load and FP drift

Once load (n_added / expected_n) exceeds ~1.0, the actual FP rate starts climbing past target_fp. By load = 2.0 you're typically 5-10x your target FP. Watch this in production — see the monitoring lesson at the end of the course.