BLOOM FILTER: bit array of size m, k hash functions
INSERT(x):
for i=1 to k: bit[hash_i(x) % m] = 1
QUERY(x):
for i=1 to k:
if bit[hash_i(x) % m] == 0: return NOT PRESENT
return POSSIBLY PRESENT // may be false positive
FALSE POSITIVE RATE:
p = (1 - e^(-kn/m))^k
Optimal k = (m/n) * ln(2) // minimizes false positives
Section 2 -- The Idea, Step by Step
Picture a nightclub doorman who can't possibly remember every face. Instead he keeps a short checklist of traits: "wore a red hat," "had glasses," "was tall." When you walk up, he checks whether all of your traits are already ticked. If even one box is blank, you were definitely never here. If every box is ticked, you were probably here — though maybe a few other guests just happened to share your traits. That single idea is a Bloom filter: it answers "definitely not in the set" or "probably in the set," using astonishingly little memory.
Build it up. The checklist is really a row of $m$ light switches (bits), all starting off. To add an item we run it through $k$ different hash functions — each turns the item into a position number — and we flip those $k$ switches on. To test an item we look at its same $k$ positions: if any switch is off, the item was never added, so there are no false negatives, ever. If all $k$ are on we answer "possibly present." A quick feel for it: with $m=10$ switches and $k=3$, after a few inserts maybe 6 switches are on; a brand-new item whose 3 positions all happen to land on lit switches is a "false positive," and how often that happens is the whole game.
The precise picture (AP/college). After inserting $n$ items into $m$ bits with $k$ hashes, the chance one particular bit is still 0 is $\left(1-\tfrac{1}{m}\right)^{kn}\approx e^{-kn/m}$, so the false-positive probability is $p=\left(1-e^{-kn/m}\right)^{k}$. Minimizing $p$ over $k$ gives the sweet spot $k=\tfrac{m}{n}\ln 2$, where each bit ends up on with probability $\tfrac12$ and $p=(1/2)^{k}$. The lever that matters most is bits-per-item $m/n$: doubling it crushes the error rate exponentially, which is why a $1.2$ MB filter can stand in for $32$ MB of stored keys.
Try this in the panel above. Step through with the |< < >| >|> controls and watch the Step and Operations counters climb — each step is one elementary operation, just as a real INSERT touches exactly $k$ positions. Now slide $n$ up and press Reset: more items means more work and, in a real Bloom filter, more switches flipped on — exactly what pushes $p$ higher. Before you raise $n$, try predicting $p=(1-e^{-kn/m})^{k}$ for a couple of values and see whether bigger $n$ really should worry you.
Section 3 -- Complexity Analysis
Symbol
Meaning
n
Input size
T(n)
Time complexity
V,E
Vertices and Edges
W
Weight or capacity
Step 1 -- Structure. A Bloom filter is a space-efficient probabilistic set. Bit array of size m. k independent hash functions. No false negatives (if inserted, always found). False positives possible (not inserted, but all k bits happen to be set by other elements).
Step 2 -- False Positive Rate. After inserting n elements: probability a single bit is still 0 = (1-1/m)^(kn) ~ e^(-kn/m). False positive rate: p = (1 - e^(-kn/m))^k. For m=1000, n=100, k=7: p ~ 0.8% false positive rate.
Step 3 -- Optimal k. Minimize false positive rate over k: optimal k = (m/n) * ln(2) ~ 0.693 * (m/n). With optimal k, false positive rate: p = (0.5)^k = (0.5)^{0.693*m/n} = 2^{-0.693*m/n}.
Step 4 -- Space Efficiency. To achieve false positive rate epsilon with n elements: m = -n*ln(epsilon) / (ln 2)^2 bits. For epsilon=1%, n=10^6: m = 9.58*10^6 bits = 1.2 MB. A hash set for the same would use ~32-64 MB. ~30x more space efficient.
Step 5 -- No Deletion. Standard Bloom filter: cannot delete elements. Removing a bit would falsely report other elements as absent. Counting Bloom filter: replace each bit with a counter. Support delete by decrementing. 4x more space.
Step 6 -- Applications. Google Bigtable: avoid disk lookup for non-existent keys. Browser safe browsing (Google Chrome checks URLs against Bloom filter of malicious sites). CDN: avoid caching one-hit wonders. Blockchain: Ethereum light clients. Databases: approximate membership queries.
Section 4 -- FAQ
What is a false positive and why does it occur? concept+
False positive: query returns 'possibly present' for an element never inserted. Occurs because ALL k hash positions happen to be set by OTHER inserted elements. More elements inserted = more bits set = higher collision probability. No false negatives: if element IS inserted, all its k bits are set to 1.
Why can't Bloom filters support deletion? concept+
Deletion would require clearing a bit. But that bit may be shared by another inserted element -- clearing it causes a false negative. Solution: counting Bloom filter (counts instead of bits). Cuckoo filter (alternative structure) supports deletion with similar space efficiency.
Where is Bloom filter used in databases? applied+
Google Bigtable and HBase: before reading SSTable from disk, check Bloom filter. If Bloom filter says 'not present', skip disk I/O. False positive = unnecessary disk read (rare). False negative = impossible (no missed data). Reduces disk I/O by 90%+ for non-existent key lookups.
What is the optimal number of hash functions? complex+
Minimize false positive rate p = (1 - e^(-kn/m))^k with respect to k. Take derivative, set to 0: optimal k = (m/n) * ln(2). With this k, each bit is set with probability 0.5 on average. More hash functions: more bits set per element (more collisions). Fewer: each bit covers more elements but less discrimination.
Can a Bloom filter have false negatives? nonobv+
No -- by construction. INSERT sets k bits to 1. QUERY returns 'not present' only if ANY of k bits is 0. Since INSERT set all k bits, they remain 1 (Bloom filter never resets bits). If x was inserted, QUERY(x) always returns 'possibly present'.
What is a Cuckoo filter? deep+
Cuckoo filter (Fan et al. 2014): stores fingerprints of elements in a cuckoo hash table. Supports: membership query (like Bloom), deletion (unlike standard Bloom), slightly better space efficiency than Bloom for false positive rates below ~3%. Uses cuckoo hashing collision resolution -- evict existing fingerprint to alternate bucket.
Section 5 -- Misconceptions
Conceptual
X Bloom filters can have false negatives.
O No false negatives by design. If element was inserted, QUERY always returns 'possibly present'. False positives only.
X Any set of hash functions works for a Bloom filter.
O Hash functions must be INDEPENDENT and UNIFORM. Using similar hash functions (e.g., h_i(x) = (x + i) % m) introduces correlation and increases false positive rate. Use truly independent hash functions or double hashing.
X Bloom filter size m must be a power of 2.
O m can be any positive integer. Use modulo: bit[hash(x) % m]. Powers of 2 allow faster bitwise AND masking but are not required.
Implementation
X Setting k=1 (one hash function) minimizes false positives.
O k=1: each element sets one bit. False positive rate = n/m. For n=m: 63.2% false positive rate. Optimal k ~ 0.693*m/n balances coverage vs collision.
X Deleting an element by clearing its k bits.
O Clearing bits causes false negatives for OTHER elements sharing those bits. Never delete from standard Bloom filter. Use counting Bloom filter or Cuckoo filter for deletions.
X Bloom filter achieves O(1) space for membership testing.
O O(m) space where m depends on n (number of elements) and target false positive rate. m = O(n) for constant epsilon. Not truly O(1) -- grows with number of elements.