What a Bloom Filter Is: Bits, Hashes, Insert, Lookup

In one line

A Bloom filter is an array of m bits and k hash functions. Insert sets the k bits an item hashes to; lookup checks them. Any zero bit means "definitely absent"; all ones means "possibly present". Both operations take O(k) time and the filter takes m bits of space.

0/3 · 0%

Think of it like this

A wall of light switches in an office. Each visitor flips on the same three switches every time, chosen by their name. To check whether someone ever came, look at their three switches: if any is off, they never came. If all are on, they probably came, though other visitors might have switched those same ones on.

Key ideas

01
Structure: a bit array of m bits, all 0 at start, and k independent hash functions each mapping an item to a position in [0, m).
02
Insert x: for i in 1..k, set bit[h_i(x) mod m] = 1. Inserting the same item twice changes nothing.
03
Lookup x: for i in 1..k, if bit[h_i(x) mod m] == 0 return "definitely absent"; after all k, return "possibly present".
04
Why no false negatives: bits are only ever set, never cleared, so an inserted item's k bits are always 1 when it's looked up.
05
Complexity: insert and lookup are O(k), constant for fixed k (usually 3–14). Space is O(m) bits, independent of item size. You can't list, count exactly, or remove items from a standard Bloom filter.

Code & diagrams

insert-lookup.txttext

m = 16 bits, k = 3 hash functions
start:            0000 0000 0000 0000

insert "apple"  -> h1=2, h2=5, h3=9
                  0010 0100 0100 0000
insert "banana" -> h1=5, h2=11, h3=14
                  0010 0100 0101 0010

lookup "cherry" -> h1=2 (1), h2=7 (0) -> DEFINITELY ABSENT
lookup "grape"  -> h1=9 (1), h2=11 (1), h3=14 (1) -> POSSIBLY PRESENT
                   ("grape" was never inserted: a false positive)

bloom.mermaiddiagram

Rendering diagram…

tiny_bloom.pypython

import hashlib

class TinyBloom:
    def __init__(self, m: int, k: int):
        self.m, self.k, self.bits = m, k, bytearray((m + 7) // 8)

    def _positions(self, item: str):
        for i in range(self.k):
            h = hashlib.sha256(f"{i}:{item}".encode()).digest()   # k salted hashes (simple, slow)
            yield int.from_bytes(h[:8], "big") % self.m

    def add(self, item: str):
        for p in self._positions(item):
            self.bits[p // 8] |= 1 << (p % 8)

    def might_contain(self, item: str) -> bool:
        return all(self.bits[p // 8] & (1 << (p % 8)) for p in self._positions(item))

bf = TinyBloom(m=1000, k=7)
bf.add("user123")
print(bf.might_contain("user123"), bf.might_contain("user999"))   # True False (almost always)

Interview problem

The problem

Can you trust the answer?

A Bloom filter says "user123 exists". Can you trust it? It says "user456 does not exist". Can you trust that? Explain under what conditions each answer is reliable.

When it breaks

A service treats "possibly present" as "present"

What you see

It returns "username taken" or "item exists" for things that don't exist, at the false-positive rate, with no way to detect it.

Fix & prevent

Always verify "maybe" with the authoritative store, or only use the filter where a wrong "maybe" is harmless.

Explain it without notes

Explain why a Bloom filter never has false negatives but can have false positives.

Practice

Run the TinyBloom with m=1000, k=7, insert 100 random strings, then query 10,000 different random strings and measure the false-positive rate.

Trade-offs

↔
Bloom filters give tiny, fast, fixed-size membership checks, with no deletes, no listing and a small error rate.

Done when you can

I can describe the bit array, hash functions, insert, lookup, complexity and the one-sided guarantee.

Command Palette