FA-72853 / Probabilistic sketches / Member archive

Bloom filter with double hashing: probe arithmetic does not wrap at 32 bits · case 03

A Python port disagrees with the 32-bit reference writer about which bits are set.

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 2 m=43 k=2	`[[0, 2, 4, 8, 18, 19, 31, 39], [true, true, false, false, false, false]]`	`[[0, 3, 4, 8, 18, 23, 29, 31], [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.