Bloom filters, Count-Min and HyperLogLog

A Bloom filter uses m bits and k hash positions. Insertion sets bits; one unset query bit proves absence. All set bits mean possible presence. The standard correctly updated model has no false negatives but may have false positives. Clearing a bit can damage another member; deletion requires another design. Approximate false-positive probability is (1−e^(−kn/m))^k under suitable hashing assumptions.

Approximately optimal k is (m/n)ln2. Operations take O(k) hash/bit work, not unconditional constant time with negligible memory. Replica lag or incorrect deletion can introduce operational false negatives even though the mathematical structure does not.

Count-Min Sketch estimates frequencies and can overestimate in nonnegative insert-only streams. HyperLogLog estimates distinct cardinality, not membership. Cuckoo filters use fingerprints and support certain deletions. Error bounds, seeds, merge compatibility and adversarial input are design-specific.

Budget false positives

Under the approximate ideal-hashing model, p=(1−e^(−kn/m))^k. Choosing k≈(m/n)ln2 yields m≈−n ln p/(ln2)². For one million elements and p=0.01, this is about 9.59 million bits, or roughly 1.2 MB of bit storage before metadata and overhead. k is about 6.64, so evaluate an integer choice such as seven. The filter uses real memory, though much less than many exact string sets.

Positive does not prove membership. A filter before a cache/disk lookup skips expensive work only on definite absence; maybe-present results query the source of truth. Never base authorisation solely on Bloom positives. False positives should cost extra lookups, not grant access.

Exceeding capacity saturates bits and increases p. Monitor actual insert counts and sampled false positives. Correlated hashes, mismatched merge seeds or incorrect deletion invalidate assumptions. Persist hash-family, seed and capacity metadata with the filter.

Foundation: What happens when n doubles but m stays fixed? Intermediate: Measure simulated false positives with a confidence interval. Advanced: Specify counter overflow, underflow and duplicate-deletion behaviour for counting Bloom, handling incompatible metadata safely.

import hashlib
bits=[False]*128
def positions(value):
    return [int.from_bytes(hashlib.sha256((str(i)+":"+value).encode()).digest()[:8],"big")%128 for i in range(3)]
def insert(value):
    for p in positions(value): bits[p]=True
def maybe(value): return all(bits[p] for p in positions(value))
insert("docker")
assert maybe("docker")