Hash Functions for Bloom Filters

A Bloom filter with k hash functions needs k bit positions per key. This lesson builds the real thing: MurmurHash3 (32-bit), the hash used inside Bitcoin, Cassandra and many Bloom libraries, and the trick that turns two of its outputs into all k positions. After it, your program prints exact hashes and positions that match published test vectors.

Why two hashes are enough

Running k separate strong hashes per operation is the dominant cost of a filter. Kirsch and Mitzenmacher (2006) showed you only need two. With base hashes h_a and h_b, define

position_i(key) = (h_a(key) + i * h_b(key)) mod m        for i = 0 .. k-1

and the false-positive rate is, for practical purposes, the same as with k independent hashes. In this course h_a = murmur3(key, seed 0) and h_b = murmur3(key, seed 0x9747b28c): the same function run under two seeds.

Do the arithmetic in 64 bits. Each hash is up to 2^32, so i * h_b for i up to 50 overflows 32 bits, and a wrapped value gives different positions whenever m is not a power of two.

Worked example: bloom has h_a = 1219308610 and h_b = 77468785. For m = 1000 and k = 4:

i=0:  (1219308610 + 0 * 77468785) mod 1000 = 610
i=1:  (1219308610 + 1 * 77468785) mod 1000 = 395
i=2:  (1219308610 + 2 * 77468785) mod 1000 = 180
i=3:  (1219308610 + 3 * 77468785) mod 1000 = 965

One caveat: if h_b mod m is 0, every position is the same and the filter behaves as if k = 1. Production libraries guard against it, for example by forcing h_b odd.

MurmurHash3, 32-bit version

Murmur is not cryptographic; it is fast and spreads bits well, which is all a Bloom filter needs. If an attacker can pick your keys, use a keyed hash such as SipHash instead.

Inputs are the key as bytes and a 32-bit seed. All arithmetic is modulo 2^32. Constants: c1 = 0xcc9e2d51, c2 = 0x1b873593. rotl(x, r) rotates a 32-bit value left by r bits.

1. Start with h = seed.
2. For every complete 4-byte block, read it as a little-endian number k (the first byte is the lowest). Then k = k * c1, k = rotl(k, 15), k = k * c2, h = h xor k, h = rotl(h, 13), h = h * 5 + 0xe6546b64.
3. If 1 to 3 bytes are left over, pack them little-endian into k the same way, and apply only k = k * c1, k = rotl(k, 15), k = k * c2, h = h xor k. There is no rotate or multiply-add for the tail.
4. h = h xor length, where length is the number of bytes.
5. Finish with a bit mixer: h = h xor (h >> 16), h = h * 0x85ebca6b, h = h xor (h >> 13), h = h * 0xc2b2ae35, h = h xor (h >> 16).

Here is every intermediate value for the 5-byte key bloom with seed 0: one full block bloo and a 1-byte tail m.

h = seed                           0x00000000
block "bloo", little-endian        0x6f6f6c62
k * c1                             0xd4ca8502
rotl(k, 15)                        0x42816a65
k * c2                             0xbd9a00ff
h ^ k                              0xbd9a00ff
rotl(h, 13)                        0x401ff7b3
h * 5 + 0xe6546b64                 0x26f441e3
tail "m", little-endian            0x0000006d
k * c1                             0x1f594b7d
rotl(k, 15)                        0xa5be8fac
k * c2                             0x87df1bc4
h ^ k                              0xa12b5a27
h ^ length                         0xa12b5a22
h ^ (h >> 16)                      0xa12bfb09
h * 0x85ebca6b                     0x2fba06c3
h ^ (h >> 13)                      0x2fbb7b13
h * 0xc2b2ae35                     0x48ad64ef
h ^ (h >> 16)                      0x48ad2c42

The result is 0x48ad2c42. Published test vectors, listed in the exercise, let you check yourself.

Common mistakes

• Reading a block big-endian. bloo must become 0x6f6f6c62, not 0x626c6f6f.
• Not truncating to 32 bits after a multiply. In Python and JavaScript the product silently grows (JavaScript loses precision above 2^53, so use Math.imul).
• Treating the tail like a block. It gets no rotate-13 and no multiply-by-5; and the first leftover byte is the lowest, even though it comes first.
• Using the character count instead of the byte count. café is 5 bytes, and the length step uses 5.
• Computing i * h_b in 32 bits. POSITIONS 1000 8 wrap0 exposes it.

Your exercise

The starter reads the commands and prints the results. You write murmur3_32 (the block loop, the tail, the length and the mixer) and the position function that applies the double-hashing formula.