bloom.nx

bloom.nx -- Bloom filter (Burton Howard Bloom, 1970). Probabilistic set membership: "probably present" or "definitely absent". Uses k independent hash functions to set k bits per insert; a query returns "absent" iff any of k bits is unset. Used for: cache-miss avoidance (Bigtable, Cassandra), spell- checkers, network protocol scoping (BitTorrent peer exchange), password leak detection (HIBP k-anonymity prefix). Trade-off: memory + time efficient at the cost of allowing false positives (no false negatives). For target false- positive rate p, expected items n: m = -n * ln(p) / (ln(2)^2) bits of bitmap k = (m / n) * ln(2) hash functions Caller picks (m, k) at construction. Invariants: BL1 False NEGATIVE rate is exactly 0. If a key was inserted, query returns true. BL2 False positive rate depends on (m, k, n) per the formula above. Caller responsibility. BL3 Capacity (cap_bits) must be a power of two so we can mask instead of modulo. Hash bits map to bit indices via & (cap_bits - 1). BL4 Two hash functions are mixed via the "Kirsch-Mitzenmacher double hashing" trick (h1 + i*h2 for i = 0..k-1) to cheaply produce k independent-enough hashes from two.