Hash Functions: The Kirsch-Mitzenmacher Trick

You need k independent hash functions. Computing k full hashes per add/check is wasteful — it dominates cost. Kirsch & Mitzenmacher (2006) proved a beautiful result:

h_i(x) = ( h_a(x) + i * h_b(x) ) mod m       for i = 0, 1, ..., k-1

The linear combination of just two strong hashes is statistically indistinguishable from k truly independent hashes — for the Bloom filter use case (a small number of bit positions in a large array).

Why we care

• Hashing dominates filter cost. From k hash invocations down to 2 is a 5-10x speedup at typical k.
• The math holds: the FP rate is identical (within tiny constants) to using k true hashes.
• Almost every production Bloom (Cassandra, RocksDB, Redis) uses this trick.

Choosing the two base hashes

For trusted inputs: MurmurHash3, xxHash, CityHash. Fast, well-distributed, non-cryptographic. Implementations are 10-100 lines of C.

For adversarial inputs (an attacker could craft inputs to deliberately collide and inflate FP rate): SipHash, or HMAC-SHA-256 truncated. Slower but DoS-resistant.

Python's built-in hash() is randomized per process (PEP 456), so a Bloom that survives serialization needs a deterministic hash. xxhash, mmh3, or hashlib.sha256 are all fine.

The simple hashes for this course

For pedagogy (you can hand-trace them) we'll use two trivial hashes:

These are not good hashes in production — they're just predictable for the exercises. Substitute MurmurHash3 in a real system.