Bloom Filter

Start from brute force

The obvious approach is an exact set: add every item to a hash set and answer each query with q in seen. Membership is exact, and each insert or query costs O(L) expected time to hash a string of length L. The cost is space: O(total size of all items), because the set keeps every string plus per-entry overhead. A billion 50-byte URLs need at least 50 GB for the strings alone, while a Bloom filter at a 1% false-positive rate needs about 9.6 bits per item, roughly 1.2 GB, however long the items are. It is also wrong for this spec, which defines the answer by the bits: in the third example 'fish' must return True, and a set says False.

The approach

The insight is that an item's bit positions depend only on the item, so insertion and lookup touch exactly the same k bits. Insert sets them; lookup checks them. That gives the one guarantee a Bloom filter makes: an inserted item always finds all of its bits set, so there are no false negatives. An absent item returns True only when other items happened to set all k of its positions, which is a false positive and is allowed.

The reference solution makes bits = [0] * m, then for every x in items and every i in range(k) sets bits[(hash32(x) + i * hb(x)) % m] = 1. For each query it appends all(bits[(hash32(q) + i * hb(q)) % m] for i in range(k)), which stops at the first 0 it reads. Double hashing is what makes k hash functions cheap: two base hashes generate all k positions, and Kirsch and Mitzenmacher showed that this loses nothing in the asymptotic false-positive rate compared with k independent hashes.

Walk through an example

Trace the first example, bloom(['cat','dog','bird'], ['cat','dog','bird','zebra','fish'], 64, 3), where each row lists the three positions (hash32(x) + i * hb(x)) % 64 for i = 0, 1, 2.

Complexity

Optimal: O(k) bit operations per insert and per query, plus O(L) to hash a length-L string once (the reference recomputes both hashes for every i, which makes it O(k·L)); space is m bits, independent of item size. Brute force (a hash set): O(L) expected per operation, but space grows with every stored string.

Edge cases to test

• Empty filter: bloom([], ['a', 'b'], 64, 3) → [False, False]. Every bit is 0, so the first bit checked already proves absence.
• A false positive: bloom(['apple', 'banana', 'cherry', 'date', 'elder'], ['fish'], 16, 2) → [True]. 'fish' maps to bits 8 and 14, both set by other words; returning False means the code is not reading the bits.
• A second hash that shares a factor with m: with m = 64, hb('olive') % 64 is 32, so its positions cycle 52, 20, 52 and k = 3 sets only two distinct bits. Still no false negatives, just a weaker filter; real implementations use a prime m or force the second hash odd.
• m = 1: every position is bit 0, so after any insert every query returns True: bloom(['a'], ['a', 'b'], 1, 3) → [True, True].
• k = 0: all() over zero bits is True, so every query is “possibly present”, even on an empty filter. Valid input needs k ≥ 1.
• Duplicate inserts: setting a bit that is already 1 changes nothing, so inserting 'cat' twice gives the same filter as inserting it once.

Common mistakes

• Sizing m too small or picking the wrong k for the target rate, so false positives spike.
• Reading “maybe present” as “present” — it must be verified; only “absent” is certain.
• Trying to delete an element — a standard Bloom filter cannot; use a counting variant.
• Deriving positions from Python’s built-in hash(): string hashing is randomized per process, so a filter saved and reloaded by another process returns false negatives. Use a fixed hash, as the provided hash32 is.

Follow-ups an interviewer asks next

How do you choose m and k?

For n items and a target false-positive rate p, the optimal size is m = −n·ln p / (ln 2)² and the best hash count is k = (m / n)·ln 2. At p = 1% that is about 9.6 bits per item and k ≈ 7. For any chosen values, the rate is approximately (1 − e^(−kn/m))^k.

How would you support deletion?

A counting Bloom filter replaces each bit with a small counter, often 4 bits: insert increments the k counters, delete decrements them, and a query checks that all k are nonzero. It costs several times the memory, and deleting an item that was never inserted corrupts other items. A cuckoo filter supports deletion more compactly by storing short fingerprints instead of bits.

What if the set grows past the n you sized it for?

The false-positive rate climbs as the bits fill up, and nothing signals it. A scalable Bloom filter adds a new, larger layer with a tighter error target each time the current one reaches capacity, and a query checks every layer. The simpler option is to rebuild the filter at a larger m from the source of truth.

How do two machines combine their filters?

Two filters built with the same m, k and hash functions merge with a bitwise OR, and the result is exactly the filter of the union of their items. AND gives only an approximation of the intersection. Distributed databases use this to ship a compact filter of one side’s join keys so the other side can skip rows that cannot match.

Where this shows up

Bloom filters guard expensive lookups with tiny memory: an LSM-tree checks one before hitting disk, a crawler dedups URLs, a cache skips a certain miss. Trading a small, tunable false-positive rate for “definitely not here, skip the slow path” is the deal that makes them ubiquitous.

Reference solution

def hash32(s):                      # provided (xmur3 32-bit, matches TypeScript)
    h = (1779033703 ^ len(s)) & 0xffffffff
    for ch in s:
        h = ((h ^ ord(ch)) * 3432918353) & 0xffffffff
        h = ((h << 13) | (h >> 19)) & 0xffffffff
    h = ((h ^ (h >> 16)) * 2246822507) & 0xffffffff
    h = ((h ^ (h >> 13)) * 3266489909) & 0xffffffff
    return (h ^ (h >> 16)) & 0xffffffff

def hb(s):                          # provided second hash (for double hashing)
    return hash32("salt:" + s)


def bloom(items, queries, m, k):
    bits = [0] * m
    for x in items:                 # insert: set all k bits of every item
        for i in range(k):
            bits[(hash32(x) + i * hb(x)) % m] = 1
    out = []
    for q in queries:               # possibly-present iff every bit is set
        present = all(bits[(hash32(q) + i * hb(q)) % m] for i in range(k))
        out.append(present)
    return out


print(bloom(['cat', 'dog', 'bird'], ['cat', 'dog', 'bird', 'zebra', 'fish'], 64, 3))
# -> [True, True, True, False, False]

function hash32(s: string): number {   // provided (xmur3 32-bit, matches Python)
  let h = (1779033703 ^ s.length) >>> 0;
  for (let i = 0; i < s.length; i++) {
    h = Math.imul(h ^ s.charCodeAt(i), 3432918353);
    h = (h << 13) | (h >>> 19);
  }
  h = Math.imul(h ^ (h >>> 16), 2246822507);
  h = Math.imul(h ^ (h >>> 13), 3266489909);
  h ^= h >>> 16;
  return h >>> 0;
}
function hb(s: string): number { return hash32("salt:" + s); }  // second hash

function bloom(items: string[], queries: string[], m: number, k: number): boolean[] {
  const bits = new Array(m).fill(0);
  for (const x of items)                 // insert: set all k bits
    for (let i = 0; i < k; i++) bits[(hash32(x) + i * hb(x)) % m] = 1;
  return queries.map((q) => {
    for (let i = 0; i < k; i++) if (!bits[(hash32(q) + i * hb(q)) % m]) return false;
    return true;                          // every bit set → possibly present
  });
}

console.log(bloom(['cat', 'dog', 'bird'], ['cat', 'dog', 'bird', 'zebra', 'fish'], 64, 3));
// -> [true, true, true, false, false]