Expand description
SharedBloomFilter - cross-process probabilistic set membership.
Composite primitive: SharedBitVec +
k hash functions. Insert hashes the input k times and sets
those k bits; contains returns true if and only if all k
bits are set. No false negatives; false positives are possible
with a tunable rate.
§Sizing rules of thumb
For n distinct items and target false-positive rate p:
- Optimal
n_bits=-(n * ln(p)) / (ln(2)^2) - Optimal
n_hashes=(n_bits / n) * ln(2)
For example, n=10_000 items with p=0.01 (1% FPR):
n_bits ~= 95_851, n_hashes ~= 7.
Use suggest_config to
compute these.
§Cross-process angle
Just a SharedBitVec wrapper. The underlying bit array is the shared state; n_bits and n_hashes are header-stored config so cross-handle opens verify they match.
§Hash function: double-hashing FNV-1a
We compute two FNV-1a hashes with different seeds, then derive
the k hash positions via (h1 + i * h2) mod n_bits for
i in 0..k. This is the standard Kirsch-Mitzenmacher
double-hashing technique that gives k effectively-independent
hash positions from only two underlying hash computations.