Init guide environment...
A Bloom Filter uses k independent hash functions. Each function maps any input element to a specific position in the bit array. More hash functions = fewer false positives, but more bits set per insert.
The backing data structure is a compact array of m bits, all initialized to 0. Elements are never stored — only their hash positions are recorded. This is what makes Bloom Filters incredibly space-efficient.
To insert an element, run it through all k hash functions. Each function returns an index in the bit array. Set every one of those bits to 1. The element itself is never stored.
To query if an element exists, hash it with all k functions and check each resulting bit. If any bit is 0 → definitely absent. If all are 1 → probably present (could be a false positive).
A false positive occurs when all k bit positions for a queried element happen to be set by different previously-inserted elements. The filter says "probably present" for something never inserted.
A Bloom Filter NEVER produces a false negative. If an element was inserted, its hash positions are permanently set — the lookup will always find all bits set. "Definitely absent" is an ironclad guarantee.
flowchart TD
A(["Element (e.g. 'apple')"])
H1["h₁(element) → index i₁"]
H2["h₂(element) → index i₂"]
H3["h₃(element) → index i₃"]
BA["Bit Array \n[0,0,0,...,0]"]
INSERT["Set bits[i₁], bits[i₂], bits[i₃] = 1"]
QUERY(["Lookup Query"])
CHECK["Check bits[i₁] AND bits[i₂] AND bits[i₃]"]
ALL1{"All bits = 1?"}
ABSENT["DEFINITELY ABSENT\n(zero false negatives)"]
PRESENT["PROBABLY PRESENT\n(false positive possible)"]
A --> H1 & H2 & H3
H1 & H2 & H3 --> BA
BA --> INSERT
QUERY --> H1 & H2 & H3
H1 & H2 & H3 --> CHECK
CHECK --> ALL1
ALL1 -->|"No (any bit = 0)"| ABSENT
ALL1 -->|"Yes"| PRESENT
style A fill:#12161f,stroke:#c6ff00,color:#fff
style H1 fill:#1a1f2b,stroke:#c6ff00,color:#c6ff00
style H2 fill:#1a1f2b,stroke:#00e5ff,color:#00e5ff
style H3 fill:#1a1f2b,stroke:#e040fb,color:#e040fb
style BA fill:#0d1117,stroke:#c6ff00,color:#fff
style INSERT fill:#12161f,stroke:#c6ff00,color:#c6ff00
style QUERY fill:#12161f,stroke:#ffab00,color:#fff
style CHECK fill:#1a1f2b,stroke:#ffab00,color:#ffab00
style ALL1 fill:#0d1117,stroke:#aaa,color:#aaa
style ABSENT fill:#12161f,stroke:#3effab,color:#3effab
style PRESENT fill:#12161f,stroke:#c6ff00,color:#c6ff00Step through insert and lookup operations on a 16-bit filter
| Structure | Space | Lookup | False Positives | False Negatives | Deletions |
|---|---|---|---|---|---|
| Bloom Filter | O(m) — very small | O(k) constant | Possible (tunable) | Never | Not supported |
| Hash Set | O(n) — grows linearly | O(1) average | Never | Never | Supported |
| Sorted Array + Binary Search | O(n) | O(log n) | Never | Never | O(n) cost |
| Counting Bloom Filter | O(m × c) bits | O(k) constant | Possible | Never | Supported |