Probabilistic structures

Bloom Filters

You need to skip disk reads for keys that were never written to an SSTable. A full hash set of every key is too large in RAM; a compact that answers “definitely absent” is enough.

Typical Bloom filters allow and (under the classic insert-only contract) no . Positives must still hit the authoritative store.

Algorithm journey

Size from n and p

m ≈ −n ln(p)/(ln 2)²; choose k*.

add sets k bits

Idempotent at the bit level.

Query all k bits

Any zero: absent. All ones: maybe.

Confirm positives

Never authorize on maybe alone.

What actually happens

Naive idea: keep every key in RAM for negative filtering. Correct membership; wrong memory budget on large key spaces.

Better idea: hash each key to k bit positions and set them. A later query that sees a zero bit proves the key was never added (classic contract). All ones only means “maybe.”

The improved design still fails when cardinality exceeds the design n ( saturates), when the drifts between writers, when bits are cleared unsafely, or when “maybe” is treated as authorization.

Invariant

For an insert-only filter with a fixed hash contract: if a key was added, every one of its k positions is 1 (no false negatives). If any probed bit is 0, the key was not added. The converse of “all bits 1” is not membership.

How to choose a Bloom filter

1. Negatives common and expensive? Bloom screening pays off.

2. False positives acceptable with a confirm path? Required. No confirm path: use an exact set.

3. Need deletion or streaming age-out? Counting, cuckoo, or stable variants (and revisit the false-negative story).

Quantitative check

For p = 0.01, plan about 10 bits per key and k ≈ 7. At n = 10⁷ that is ~12.5 MB of bits, not the full keys. If r independent filters can each accept a positive, total false-positive rate is 1 − (1 − p)ʳ, not p.

Definite negative

any required bit = 0

The key was not added, assuming bits were never incorrectly cleared and hashing is consistent.

Probabilistic positive

all required bits = 1

The key may have been added, or other keys may have set the same positions.

No payload

m bits + hash contract

A positive must be confirmed against the authoritative map, database, or file.

Interactive false-positive trace

Insert two names, then query two names that were never inserted. One has a zero bit and is rejected; the other inherits three one-bits from unrelated keys and becomes a legitimate false positive.

Probabilistic membership laboratory

Watch unrelated keys create a false positive

Three deterministic demo hashes map each key into a 12-bit filter. The filter stores bits, not the inserted keys.

items n

set bits

0/12

hashes k

Initialize 12 zero bits

Step 1 of 5

Answer

empty filter

A zero at any required position proves that no inserted key could have set every required bit.

Inserted ground truth

∅

Real filters do not retain this list; it is shown so you can identify the false positive.

Sizing model

p ≈ (1 − e^−kn/m)^k = 0.0%

optimal k ≈ (m/n) ln 2 = —

The operation contract

Insertion

for i in h₁(x)…hₖ(x): bits[i] = 1

Insertion is idempotent at the bit level. The filter cannot tell whether x was inserted once, twice, or merely shares positions with other keys.

Query

all(bits[i] == 1 for i in hashes(x))

A false result is conclusive. A true result is a screening result and must not be treated as proof of identity, ownership, or authorization.

“No false negatives” has preconditions. It holds for the mathematical insert-only structure. Clearing a shared bit, changing serialization or hash seeds, losing a concurrent bit update, querying a stale replica, or aging a stable filter can create false negatives.

Where the false-positive formula comes from

With m bits, k independently uniform hash positions per key, and n inserted keys, there are kn bit-setting attempts. The standard approximation assumes idealized independent hashing.

A bit remains zero

(1 − 1/m)ᵏⁿ ≈ e⁻ᵏⁿ⁄ᵐ

More insertions or hashes increase occupancy.

False-positive probability

p ≈ (1 − e⁻ᵏⁿ⁄ᵐ)ᵏ

An absent key is positive only when all k queried bits are one.

Optimal hash count

k* ≈ (m/n) ln 2

Too few hashes underuse bits; too many saturate them.

Size from a target error rate

m ≈ −n ln(p) / (ln 2)²

For p = 0.01, the optimum is about 9.59 bits per expected key and 6.64 hashes, normally rounded to seven. Capacity planning must use expected peak cardinality, not today’s count.

Composition changes the budget

If a lookup accepts a positive from any of r independent filters, total false-positive probability is 1 − (1 − p)ʳ, not simply p. LSM engines therefore budget error across files or levels.

Reference implementation with identical semantics

These examples derive each index by hashing a seed plus the key bytes. Production code normally uses a tuned library, faster double hashing, stable serialization, and persisted configuration metadata.

Python

python

import hashlib
import math

class BloomFilter:
    def __init__(self, bit_count, hash_count):
        if bit_count <= 0 or hash_count <= 0:
            raise ValueError("sizes must be positive")
        self.m = bit_count
        self.k = hash_count
        self.bits = bytearray((bit_count + 7) // 8)

    def _indexes(self, value):
        payload = value.encode("utf-8")
        for seed in range(self.k):
            digest = hashlib.sha256(seed.to_bytes(4, "big") + payload).digest()
            yield int.from_bytes(digest, "big") % self.m

    def _set(self, index):
        self.bits[index // 8] |= 1 << (index % 8)

    def _get(self, index):
        return bool(self.bits[index // 8] & (1 << (index % 8)))

    def add(self, value):
        for index in self._indexes(value):
            self._set(index)

    def might_contain(self, value):
        return all(self._get(index) for index in self._indexes(value))

def optimal_shape(expected_items, false_positive_rate):
    if expected_items <= 0 or not 0 < false_positive_rate < 1:
        raise ValueError("expected_items > 0 and 0 < rate < 1 required")
    m = math.ceil(-expected_items * math.log(false_positive_rate)
                  / (math.log(2) ** 2))
    ideal_k = (m / expected_items) * math.log(2)
    k = max(1, math.floor(ideal_k + 0.5))  # explicit half-up rounding
    return m, k

Java

java

import java.math.BigInteger;
import java.nio.ByteBuffer;
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;

final class BloomFilter {
    private final int m;
    private final int k;
    private final BitSet bits;

    BloomFilter(int bitCount, int hashCount) {
        if (bitCount <= 0 || hashCount <= 0) {
            throw new IllegalArgumentException("sizes must be positive");
        }
        m = bitCount;
        k = hashCount;
        bits = new BitSet(bitCount);
    }

    private int index(String value, int seed) {
        try {
            MessageDigest sha256 = MessageDigest.getInstance("SHA-256");
            sha256.update(ByteBuffer.allocate(4).putInt(seed).array());
            byte[] digest = sha256.digest(value.getBytes(StandardCharsets.UTF_8));
            return new BigInteger(1, digest).mod(BigInteger.valueOf(m)).intValue();
        } catch (NoSuchAlgorithmException impossible) {
            throw new IllegalStateException(impossible);
        }
    }

    void add(String value) {
        for (int seed = 0; seed < k; seed++) bits.set(index(value, seed));
    }

    boolean mightContain(String value) {
        for (int seed = 0; seed < k; seed++) {
            if (!bits.get(index(value, seed))) return false;
        }
        return true;
    }

    static int[] optimalShape(int expectedItems, double falsePositiveRate) {
        if (expectedItems <= 0 || falsePositiveRate <= 0.0
                || falsePositiveRate >= 1.0) {
            throw new IllegalArgumentException("expectedItems > 0 and 0 < rate < 1 required");
        }
        double log2 = Math.log(2.0);
        int m = (int) Math.ceil(-expectedItems * Math.log(falsePositiveRate)
                                / (log2 * log2));
        double idealK = (m / (double) expectedItems) * log2;
        int k = Math.max(1, (int) Math.floor(idealK + 0.5)); // half-up, as above
        return new int[] {m, k};
    }
}

Complexity and what the notation hides

Bloom-filter operation costs and caveats
Operation	Cost	What happens
add(key)	Θ(k) hash/index work	Sets k bit positions; repeated positions are harmless but waste a hash.
mightContain(key)	O(k), often stops early	One zero proves absence; all ones produce only a possible match.
union	Θ(m / word size)	Bitwise OR is valid only for compatible size, hash count, seeds, and encoding.
intersection estimate	Θ(m / word size)	Bitwise AND is representable, but interpreting cardinality needs a probabilistic model.
space	Θ(m) bits	Independent of key byte length because keys themselves are not retained.

Hashing is not free: the seeded SHA examples above hash the full L-byte key k times, so their hashing work is Θ(kL). A production double-hashing design can hash once and derive k indices in Θ(L + k); the table isolates those k index and bit operations.

Choose the variant by the contract

Bloom-filter variants and related structures
Structure	Mechanism	Good fit	Trade-off
Counting Bloom filter	Small counters replace bits	Deletion when every remove matches a prior add	More memory; overflow/underflow and concurrent updates matter
Blocked Bloom filter	Hashes target one cache-sized block	Fewer cache misses and storage reads	Different false-positive analysis and tuning
Scalable Bloom filter	Add progressively sized filters	Unknown or growing cardinality	Query checks multiple layers; allocate an error budget per layer
Stable Bloom filter	Age or clear counters over time	Approximate membership for streams	Can introduce false negatives, changing the classic contract
Cuckoo filter	Store compact fingerprints in candidate buckets	Deletion and often good lookup locality	Insertion may relocate fingerprints or fail near capacity
Xor-family filter	Build a static fingerprint structure	Compact, fast read-mostly membership	Construction is offline; ordinary incremental inserts are not supported

Production design checks

Put it before an expensive negative path

Useful examples include avoiding an SSTable read, remote request, cache miss fill, or duplicate crawl, not replacing the authoritative lookup.

Persist the whole hash contract

Bit count, hash count, seed/version, byte encoding, normalization, and endianness must agree between writers and readers.

Measure actual cardinality

Underestimating n saturates bits and can make the observed false-positive rate dramatically worse than the design target.

Treat rebuilds as normal

A standard filter cannot shrink or remove safely. Build a replacement from source data, then switch readers atomically.

Coordinate concurrent writers

Setting two different bits in the same machine word can lose an update without atomic OR, locking, or thread-local filters merged later.

Never make it an authorization oracle

A possible match is not proof. Security and billing decisions require an exact, authenticated source of truth.

Exercises

Design m and k for n = 10⁶ keys at p = 0.01. Roughly how many megabytes of bits do you need?
Show a tiny bit array and two inserts that create a for a third key. Why is that not a ?
A stable Bloom filter ages bits. Which classic invariant breaks, and when would you still accept that trade?

Primary sources

Bloom, B. H. (1970): Space/time trade-offs in hash coding with allowable errors.
Broder & Mitzenmacher: Network applications of Bloom filters (survey).
Apache Cassandra / RocksDB docs: Bloom filters in front of SSTables (engineering practice).

Takeaway

Bloom filters trade false positives for tiny negative checks. Classic insert-only filters avoid false negatives only under a fixed hash contract; always confirm positives.