A signup form asks “is this username taken?” against a billion registered names. A HashSet answers exactly — and stores every name. The hot path only needed a cheap maybe. You do not need the string back. You need to skip the database when the name is definitely free.
A Bloom filter is a bit array plus k hashes. Add sets k bits. Query checks those k bits. If any bit is 0, the key was never inserted. If all k bits are 1, the key might be in the set — or those bits were set by other keys. False positives are the bill for not storing the keys. False negatives are not part of the deal.
Glossary words this post will not re-teach — ADT vs implementation, expected vs worst-case, how to read a complexity table — live on the Data Structures Roadmap. The contract here is approximate membership: definitely not, or maybe yes.
The contract: maybe yes, definitely no
A set answers “is x a member?” with yes or no. A Bloom filter answers with a weaker pair of verbs:
| Answer | Meaning |
|---|---|
mightContain(x) == false | x was never added. This is certain. |
mightContain(x) == true | x was added, or other keys flipped the same bits. |
There is no get. There is no iteration of members. There is no “give me the username that hashed here.” The structure keeps bits, not payloads. That is why a billion names can fit in a few hundred megabytes instead of tens of gigabytes of strings.
The invariant that makes the structure usable: if you added x, a later query cannot say no. A 0 bit that x would have set can only still be 0 if add(x) never ran. Collisions can only turn extra answers into yes. They cannot erase a yes you already paid for.
Bit array plus k hashes
Pick two integers and keep them fixed after construction: m (how many bits) and k (how many hash functions). Storage is m bits. Java’s BitSet is a fine backing array.
m = 16 bits, k = 3 hashes
index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
start: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0Each hash function maps a key to one index in 0 … m-1. The same key must always produce the same k indexes — otherwise you cannot find what you stored. Different keys should spread. That is the same hash bet a table makes, except you never store the key in the bucket. You only flip bits.
A common teaching trick is two independent hashes, then k derived indexes — so you do not ship k separate hash functions:
h_i(key) = (h1(key) + i * h2(key)) mod m for i = 0 .. k-1h2 must not be 0 (or you land on one bit k times). Math.floorMod keeps a negative hashCode in range. The formula is an implementation detail. The layout is still an array of bits, addressed k times.
add vs mightContain
add does not check membership first. It hashes k times and sets those bits to 1. Bits that were already 1 stay 1. There is no counter in the classic structure.
void add(String key) {
for (int i = 0; i < k; i++) {
bits.set(index(key, i));
}
}mightContain hashes the same k times. The first 0 is a hard no. Only if every bit is 1 do you return maybe-yes.
boolean mightContain(String key) {
for (int i = 0; i < k; i++) {
if (!bits.get(index(key, i))) {
return false; // definitely not
}
}
return true; // maybe
}A tiny session on the 16-bit array. Indexes below are made-up but consistent — the picture is the bits, not a particular hash.
add("ada") → bits 2, 7, 11
0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0
add("bob") → bits 4, 7, 14 (7 already 1)
0 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0
mightContain("ada") 2, 7, 11 all 1 → maybe yes (true member)
mightContain("cy") 2, 9, 11 → bit 9 is 0 → definitely not
mightContain("eve") 2, 7, 14 all 1 → maybe yes (false positive)"eve" was never added. Bits 2, 7, and 14 were set by "ada" and "bob". The filter cannot tell the difference. That is not a bug in the hash. That is the structure working as designed: yes is a probability, no is a fact.
Note: Name the query mightContain, not contains. A method called contains that returns true for a stranger will be “fixed” by a later reader who does not know the contract.
False positive rate vs size
Every extra insert paints more 1s. The denser the array, the easier it is for a stranger’s k indexes to land on bits that are already set. Three knobs:
| Knob | If you raise it | What happens |
|---|---|---|
n (inserts) | More members | More 1s → higher false-positive rate |
m (bits) | More memory | Sparser array → lower false-positive rate |
k (hashes) | More probes per key | Helps until you saturate the array; then it hurts |
The usual approximation, once hashes look uniform:
p ≈ (1 - e^{-kn/m})^kp is the chance a non-member still sees k ones. Optimal k for a chosen m and expected n is about (m/n) ln 2 — roughly 0.7 hashes per bit-per-item. At that k, a common rule of thumb is ~10 bits per stored item for p around 1%. Double the bits, drop p a lot. Halve the bits, watch p climb.
You do not tune this on a whiteboard during an incident. You pick a target p and a capacity n, then size m (and k) before you start inserting. A filter you keep stuffing past its design n is a bit array that is mostly ones. mightContain starts answering yes to everyone. The structure has not broken. You have filled it.
Structure: Bloom filter (classic)
add(x) O(k) — set k bits
mightContain(x) O(k) — test k bits
space O(m) bits — not O(n) keys
false negative never
false positive p, from m, n, k
iterate members not supported
get the key back not supportedk is a small constant (often 3–10). The hot path is a handful of bit tests, independent of how many keys you have added — until the array saturates and the answers get worse, not the CPU.
No deletes (classic Bloom)
You cannot turn bits back to 0. "ada" and "bob" shared bit 7. Clearing it because "bob" left would make "ada" look absent — a false negative, which the contract forbids.
Counting Bloom filters replace each bit with a small counter so add increments and remove decrements; that is a different layout, with overflow as its own failure mode. Classic Bloom filters do not delete.
Rebuild from the source of truth if members disappear. Or accept that “once maybe-yes, always maybe-yes” for the life of this array.
Java: there is no JDK BloomFilter
java.util has BitSet, HashSet, and HashMap. It does not ship a Bloom filter. You write the handful of methods above, or you take a library. Guava’s com.google.common.hash.BloomFilter is the usual off-the-shelf choice if you already depend on Guava — this post will not walk its API.
A compact sketch you can run. It is a teaching machine, not a production filter: String.hashCode is not a cryptographic hash, and two derived functions are a shortcut.
final class BloomFilter {
private final BitSet bits;
private final int m;
private final int k;
BloomFilter(int m, int k) {
if (m <= 0 || k <= 0) {
throw new IllegalArgumentException("m and k must be positive");
}
this.m = m;
this.k = k;
this.bits = new BitSet(m);
}
void add(String key) {
for (int i = 0; i < k; i++) {
bits.set(index(key, i));
}
}
boolean mightContain(String key) {
for (int i = 0; i < k; i++) {
if (!bits.get(index(key, i))) {
return false;
}
}
return true;
}
private int index(String key, int i) {
int h1 = key.hashCode();
int h2 = Integer.rotateLeft(h1, 16) | 1; // odd, never 0
return Math.floorMod(h1 + i * h2, m);
}
}A session that shows the two answers:
BloomFilter usernames = new BloomFilter(64, 3);
usernames.add("ada");
usernames.add("bob");
System.out.println(usernames.mightContain("ada")); // true — member
System.out.println(usernames.mightContain("cy")); // false — definitely not
// usernames.mightContain("eve") may be true or false; true is a false positiveOn a 64-bit toy filter, a false positive for "eve" is luck of the hashes. On a filter sized for millions of names at 1% p, luck is a budget you chose.
When not to use a Bloom filter
Skip it when “maybe” is not an acceptable answer.
- You need a definite yes. Auth, billing, “this row exists so charge the card,” “this token is valid.” A false positive here is a product bug. Use a set, a map, or the database. The Bloom filter is a pre-check that lets you skip the exact store when the answer is no — not a replacement for the store.
- You need the actual keys. Iteration, debugging, “list everyone we added,” recovering a username from the filter. The bits are not reversible into strings. If you still keep the keys elsewhere, the filter is an index, not the source of truth.
nis small. A thousand strings in aHashSetis exact and cheap. Bits-plus-hashes start to win when storing the keys is the pain — hugen, or a check you want in a tiny cache line before a disk hop.- You need deletes on a classic filter. Rebuild, or use a counting variant on purpose. Do not clear bits.
Do not use a Bloom filter as a security boundary. “Maybe this password was leaked” is a research demo. “Maybe this session is authentic” is a hole.
The jobs that fit: skip a cache miss you can prove is a miss (Cassandra/HBase-style SSTable filters are the famous production picture), avoid a disk or network round-trip when the key is definitely absent, cheap “have I probably seen this URL / email / request id?” when a rare extra yes is cheap to confirm downstream.
Cheat sheet
Layout: m bits + k hashes; keys are not stored
add(x): set k bits
mightContain: any 0 → definitely not; all 1 → maybe yes
False +ve: p ≈ (1 - e^{-kn/m})^k ; size m for target p and n
False -ve: never (classic, no deletes)
Deletes: not in classic Bloom; counting Bloom uses counters
Hot path: O(k) bit tests, independent of n until the array fills
JDK: none — BitSet + your hashes, or Guava BloomFilter
Good: pre-check before a slow exact store; huge n, tiny memory
Avoid: definite yes, recovering keys, tiny n, security decisionsDo:
- Name the query
mightContain(ormightContainbehind a comment that says maybe). - Size
mandkfor a targetpbefore you insert past thatn. - Confirm a maybe-yes with the exact store when the yes matters.
- Treat a
0bit as gospel: skip the database, skip Redis, skip the disk file.
Don’t:
- Call it
containsand returntruefor strangers. - Clear bits to delete a key from a classic filter.
- Use maybe-yes as authorization, billing, or “the row exists.”
- Keep stuffing inserts into an undersized array and blame the hash.
Wrap-up
A Bloom filter trades exact membership for a handful of bits. Add paints k ones. Query trusts a zero and only suspects a run of ones. False positives are the point of the trade: you did not store the keys, so two different keys can share bits. False negatives are out of scope unless you delete, which classic Bloom filters do not.
Use it as a gate in front of an exact structure — a HashSet, a database, a sorted file — when “definitely not” lets you skip expensive work and a rare extra yes is cheap to verify. Need the members themselves, or a yes you can take to the bank? That is a set. The glossary and living index for this series sit on the Data Structures Roadmap.