SpecializedData structureaka probabilistic set, approximate membership filter

Bloom Filter

A bit array plus k hash functions that answers "possibly in the set" or "definitely not" in O(k) with a tiny memory footprint and no false negatives.

Pattern: Hashing Practice (2)

Progress

Definition

A Bloom filter is a probabilistic set that uses m bits and k independent hash functions. To add an item, set the k bits at positions h₁(x) … hₖ(x). To query, check that all k bits are set: if any is 0 the item is definitely absent; if all are 1 the item is probably present. False positives happen when other items happened to set the same bits; false negatives never happen.

The trade-off is dramatic: storing a million URLs with a 1% false-positive rate takes about 9.6 million bits (1.2 MB), independent of URL length, versus tens of megabytes for a Hash Set of the strings. The cost is that items cannot be removed (clearing a bit could erase another item) and membership is approximate.

Bloom filters sit in front of expensive lookups: skip a disk or network read when the filter says "definitely not". Databases (Cassandra, RocksDB, HBase) use them per SSTable; browsers used them for malicious-URL lists; CDNs use them to avoid caching one-hit wonders.

probabilisticbit arraymultiple hashesfalse positivesspace-efficient

Intuition

A mental model before the formal terms.

Imagine a long row of light switches, all off. Each visitor to a party is told to flip three specific switches determined by their name. Later, to check whether "Alice" attended, look at Alice's three switches: if any is still off, she certainly was not there. If all three are on, she probably was — but it is possible that three other guests happened to flip exactly those switches between them.

You cannot record a guest leaving by flipping switches back off, because someone else may share a switch.

How it works

Parameters: for n expected items and target false-positive rate p: m = -n ln p / (ln 2)² bits and k = (m / n) ln 2 hashes. Example: n = 10⁶, p = 0.01 → m ≈ 9.6 × 10⁶ bits, k ≈ 7.
Hashing: rather than k independent functions, use double hashing hᵢ(x) = (h₁(x) + i · h₂(x)) mod m, which is provably almost as good (Kirsch–Mitzenmacher).
add(x): for i in 0…k-1, set bits[hᵢ(x)] = 1.
mightContain(x): return true iff every bits[hᵢ(x)] is 1.
Counting Bloom filter: replace bits with small counters to support deletion at 4–8× the memory.
Union of two filters with identical parameters is the bitwise OR; intersection is approximately the AND.

Why it works

No false negatives: adding x sets all of its bits, and bits are never cleared, so a later query for x sees all ones.

False-positive probability: after n insertions each bit is still 0 with probability (1 - 1/m)^(kn) ≈ e^(-kn/m), so a query for an absent item sees all k bits set with probability (1 - e^(-kn/m))^k. Minimising over k gives k = (m/n) ln 2 and p ≈ 0.6185^(m/n).

Operations

Operation	Description	Cost
add(x)	Set k bits derived from x.	O(k)
mightContain(x)	Check k bits; false ⇒ definitely absent.	O(k)
union(other)	Bitwise OR of two filters with equal m and k.	O(m)
estimatedCount()	Estimate n from the number of set bits.	O(m)
delete(x)	Not supported (use a counting Bloom filter).	—

Recognition

How to tell a problem wants this.

"Approximate", "probabilistic", "may contain", "avoid an expensive lookup", "de-duplicate a huge stream".
Memory is far too small to store the actual keys.
Only insert and membership are needed — no deletion, no enumeration, no counts.
A false positive is cheap (an extra disk read) but a false negative is unacceptable.

“have you seen this before” → Hashing “parity/odd occurrences” → Bit Manipulation

Interactive demo

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1init(m, k): bits = [0]*m
2h_i(x) = (h1(x) + i*h2(x)) mod m
3add(x): for i in 0..k-1: bits[h_i(x)] = 1
4might_contain(x): return all(bits[h_i(x)] for i in 0..k-1)
5params: m = -n ln p / (ln 2)^2; k = (m/n) ln 2

Implementation

1import hashlib
2import math
3from typing import Iterator
4 
5 
6class BloomFilter:
71 · State — bit array, number of hashes, insert count
83 · Size the filter from expected items and target false-positive rate
9    def __init__(self, expected_items: int, false_positive_rate: float = 0.01):
10        n, p = max(1, expected_items), false_positive_rate
11        self.m = max(8, int(-n * math.log(p) / (math.log(2) ** 2)))  # number of bits
12        self.k = max(1, round(self.m / n * math.log(2)))              # number of hash functions
13        self.bits = bytearray((self.m + 7) // 8)
14        self.count = 0
15 
162 · Hashing — two base hashes, k derived via double hashing
17    def _indices(self, item: str) -> Iterator[int]:
18        data = item.encode()
19        h1 = int.from_bytes(hashlib.md5(data).digest()[:8], "little")
20        h2 = int.from_bytes(hashlib.sha1(data).digest()[:8], "little") | 1
21        for i in range(self.k):
22            yield (h1 + i * h2) % self.m
23 
244 · add — set k bits
25    def add(self, item: str) -> None:
26        for pos in self._indices(item):
27            self.bits[pos >> 3] |= 1 << (pos & 7)
28        self.count += 1
29 
305 · mightContain — all k bits set? (false positives possible, never false negatives)
31    def might_contain(self, item: str) -> bool:
32        return all(self.bits[pos >> 3] & (1 << (pos & 7)) for pos in self._indices(item))
33 
34    def __contains__(self, item: str) -> bool:
35        return self.might_contain(item)
36 
376 · Estimated current false-positive probability
38    def false_positive_rate(self) -> float:
39        return (1 - math.exp(-self.k * self.count / self.m)) ** self.k

Walkthrough

The constructor computes optimal m and k with math.log; bytearray((m + 7) // 8) is a mutable byte buffer that acts as the bit array.
_indices derives two 64-bit base hashes from md5 and sha1 digests via int.from_bytes, then yields k positions using double hashing.
add sets bits with |= on the byte at pos >> 3 using mask 1 << (pos & 7).
might_contain uses all(...) over a generator so it short-circuits at the first clear bit.
__contains__ lets callers write item in bloom, mirroring set syntax.
false_positive_rate evaluates the standard (1 - e^{-kn/m})^k estimate.

Complexity (this implementation)

time O(k) per add/query · space O(m) bits

Two cryptographic digests per operation dominate runtime; swap in mmh3 or xxhash for speed.

Language notes

hashlib is used because Python's built-in hash() is salted per process (PYTHONHASHSEED) — a filter persisted to disk would break.
bytearray supports in-place |= on elements and packs 8 bits per byte; a list[bool] would be ~28x larger.
Python ints are unbounded so h1 + i * h2 cannot overflow; the modulo does all the work.
The pybloom-live / bloom-filter2 packages exist for production use.

Common mistakes in this language

Using hash(item) — differs between processes, so a filter cannot be serialized or shared.
Building the bit array as [0] * m — works, but wastes memory and defeats the purpose.
Trying to implement remove — a plain Bloom filter cannot delete (use a counting Bloom filter).

Language differences that matter here

Hashing: C++ gets a 64-bit unsigned FNV with wrap-around; JS/TS must use Math.imul and >>> 0 because number is a double and silently loses bits above 2^53; Python uses hashlib because built-in hash() is randomized per process.
Bit storage: C++ std::vector<uint8_t>, JS/TS Uint8Array, Python bytearray — all pack 8 bits per byte.
Python supports item in filter via __contains__; the others expose mightContain explicitly.
Integer overflow: h1 + i*h2 is safe in all four (unsigned wrap in C++, < 2^53 in JS/TS, unbounded in Python), but only because JS/TS restrict the base hashes to 32 bits.

Complexity

Operation	Average	Worst	Note
Access	—	—
Search	O(k)	O(k)	Probabilistic: may return a false positive.
Insert	O(k)	O(k)
Delete	—	—	Unsupported; counting variant is O(k).
Update	—	—
Union	O(m)	O(m)
Space	O(m)		m ≈ 1.44 · n · log₂(1/p) bits; about 9.6 bits per item at p = 1%.

Advantages & disadvantages

Advantages

Constant memory per item (~10 bits for 1% error), independent of key size.
O(k) insert and query with excellent cache behaviour on the bit array.
No false negatives, so it is safe as a pre-filter.
Filters merge with a bitwise OR — easy to distribute.

Disadvantages

False positives; the rate rises as the filter fills beyond its design capacity.
No deletion, no enumeration, no exact count.
Requires good, fast hash functions; poor hashing inflates the error rate.
Must choose m and k up front from an estimate of n.

Use cases

LSM-tree databases: skip SSTables that cannot contain a key.
Web crawlers: "have I seen this URL?" over billions of URLs.
Spell checkers and malicious-URL / password-breach checks.
Network routers and CDNs: cache admission, packet de-duplication.
Distributed joins: ship a Bloom filter of one side's keys to prune the other.

Use it when

Membership pre-checks in front of slow storage.
De-duplicating enormous streams with bounded memory.
Sharing a compact summary of a key set between machines.

Avoid it when

Exact membership is required — use a Hash Set.
Items must be deleted — use a counting Bloom filter or a cuckoo filter.
You need to list or count the members.
The set is small enough that a hash set fits comfortably.

Alternatives

Hash Set Hash Table Trie

Common mistakes

Treating a positive answer as certain.
Under-provisioning m for the real n — the error rate climbs quickly past capacity.
Using k correlated hash functions (e.g. h(x) + i) which cluster bits and raise false positives.
Trying to remove items by clearing bits.
Using m that is not coprime with the double-hashing step, causing cycles (force h₂ odd or use prime m).

Interview patterns

System design: "how would you check if a URL was already crawled with 10 billion URLs?"
Derive m and k from n and p; explain why there are no false negatives.
Compare with hash set, cuckoo filter, and counting Bloom filter.
Use as a first-stage filter before a database lookup in a cache design.

Interview questions on this

Recognizing the approach from an array and a targetIntermediate
Deciding whether O(n²) can be improvedIntermediate
Hash map or array?Beginner
Average case versus worst caseIntermediate

Mock interviews

Two SumBeginner
Longest Substring Without Repeating CharactersIntermediate
Subarray Sum Equals KIntermediate

Interview problems

Design HashMapeasy Repeated DNA Sequencesmedium