A Self-Tuning Bloom Filter

Until now you picked m and k by hand. A usable filter is configured by intent: "hold about n keys at false-positive rate p". After this lesson your program does that. INIT sizes the filter with the formulas from the false-positive lesson, ADD and CHECK use the double hashing from the hashing lesson, and DUMP prints the filter's bytes so the exact bits can be checked.

Putting the pieces together

1. Size it. m = ceil(-n * ln(p) / (ln 2)^2) and k = round((m/n) * ln 2), at least 1.
2. Allocate it. m bits, all zero. Pack them: a byte array of ceil(m/8) bytes, not one byte per bit. A million keys at 1% is about 1.2 MB packed and 9.6 MB unpacked.
3. Hash it. The positions of a key come from the hashing lesson: (h_a + i * h_b) mod m for i = 0 .. k-1. Your starter already has murmur3 and a position function; you do not rewrite them.
4. Set and test bits. Bit p lives in byte p / 8 (integer division) at bit number p mod 8, counting from the least significant bit. Setting it is array[p / 8] |= 1 << (p mod 8); testing it is the matching shift and mask.

Take INIT 12 0.1. The formulas give m = 58 and k = 3, so the array is 8 bytes with 6 unused bits at the end. Adding ant and bee sets these positions:

ant: 52, 1, 8
bee: 44, 13, 40

byte 0: bits 1  ->  0x02
byte 1: bits 0, 5  ->  0x21
byte 5: bits 0, 4  ->  0x11
byte 6: bits 4  ->  0x10

DUMP prints the 8 bytes as lowercase hex, which is 0221000000111000 here. A hex dump is the filter's serialisation: another program that knows m, k and the hashes can load it and answer the same CHECKs.

Load and drift

load is n_added / n, the fraction of planned capacity used. Up to 1.0 the false-positive rate is at or below p. Past 1.0 it rises, and by load 2 it is several times the target. STATS reports load and the number of bits set (set), the two numbers a later lesson uses to judge whether a filter is healthy.

Common mistakes

• Reducing modulo the byte count. Positions are taken mod m, not mod (8 * bytes). When m is not a multiple of 8, the last byte has unused high bits that must stay 0. DUMP exposes this.
• Not resetting on INIT. A second INIT must forget keys, the added counter and the old array.
• Counting duplicates wrongly. ADD of a key already present still counts as an add (n goes up) but sets no new bits.
• Rounding k after using the wrong m. Compute k from the m you actually allocate.
• Bit order. Counting bits from the most significant end of each byte gives a different DUMP.

Your exercise

The starter provides the hashing and the command loop. You write the INIT sizing and allocation, ADD, CHECK, STATS (including the popcount) and DUMP.