FA-72847 / Probabilistic sketches / Member archive

Bloom filter with double hashing: second hash is not forced odd · case 02

Bit layouts diverge from a conforming writer and, for power-of-two m, some items collapse onto few bits.

Member previewVariant 2 · 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=63 k=3	`[[3, 13, 18, 24, 27, 28, 29, 34, 45, 47, 52, 55, 58], [true, true, false, true, false, false]]`	`[[3, 13, 15, 18, 26, 27, 30, 34, 46, 48, 54, 56, 58], [true, true, false, true, 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.