FA-72843 / Probabilistic sketches / Member archive

Bloom filter with double hashing: probe sequence skips the base probe · case 03

The filter sets bits at positions that another writer never probes, and base-hash bits are missing.

Member previewVariant 3 · 3 implementations · 7 checks per implementation

Case contract

Input {m, k, add, query}. Each string is hashed with 32-bit FNV-1a over its UTF-8 bytes using seed 0 (h1) and seed 0x5bd1e995 (h2); h2 is forced odd by OR-ing 1. Probe i for i in 0..k-1 is ((h1 + i*h2) mod 2^32) mod m. Return [sorted set bit indices, membership booleans for query] where membership requires every probe bit.

Why this case matters

Bloom filters built with Kirsch-Mitzenmacher double hashing must reproduce the exact same probe sequence across writers and readers; any drift silently changes the bit layout.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
bloom 0 m=64 k=3	`[[3, 6, 25, 31, 38, 46, 53, 54, 57, 60], [true, true, false, false, false, false]]`	`[[3, 6, 19, 24, 25, 31, 38, 46, 53, 54, 57, 60], [true, true, false, false, false, false]]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

Member access is invitation-based. Sign in with your invited account to inspect the sources.