Overview
A Bloom filter hashes each inserted item to several bit positions and sets those bits. A query checks the same positions; if any bit is missing the item is definitely absent, otherwise it may be present.
CoreSource checked
Bloom Filter
Tests set membership with a compact bit array that allows false positives but not false negatives.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Intermediate
- Family
- Probabilistic Set
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
bit arraymultiple hashesprobabilistic membershipfalse positivesstored invarianthash functionprobabilistic setinvariant maintenance
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(k)
Average
O(k)
Worst
O(k)
Space
O(m)
When to Use
- Use when memory is limited and false positives are acceptable.
- Use when false negatives would be unacceptable for inserted items.
When Not to Use
- Avoid when exact membership answers are required.
- Avoid when deletion is needed unless using a counting variant.
What It Does
- Maps items through multiple hash functions
- Sets bits in a compact bit array
- Answers membership queries with possible false positives
Use Cases
- Cache and database negative-lookups
- Network and storage membership filters
- Prechecking expensive set lookups
Inputs
- Items
- Bit array size
- Hash functions
Outputs
- Probable membership result
Key Formulas (1)
False positive estimate
p ≈ (1 − exp(−k·n/m))k
p ~= (1 - exp(-k*n/m))^kEstimates false positive probability from hash count, item count, and bit array size.
Pseudocode
- 1.Initialize a bit array to zero
- 2.For insert, compute k hash positions and set each bit
- 3.For query, compute the same k positions
- 4.Return absent if any bit is zero
- 5.Return maybe-present if all bits are one
Canonical Example
- Input
- insert 'cat' using three hash positions 2, 5, 9
- Output
- bits 2, 5, and 9 set to 1
- Explanation
- A later query for 'cat' checks the same bits; another item may collide and create a false positive.
Implementation Notes
- Choose bit-array size and hash count from expected item count and target false-positive rate.
- Use double hashing or another documented method to derive hash positions.
- Track approximate load to know when rebuilding is needed.
Common Pitfalls
- Overfilling the filter raises the false-positive rate sharply.
- Poor hash independence creates uneven bit usage.
- Standard Bloom filters cannot safely delete items.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow several hash functions setting and checking bits.
Step 1 of 5: Initialize a bit array to zero
bloom-bitsNotes
Bloom filters are best used as probabilistic prefilters, not as exact sets.
Sources (1)
What each reference supports for this entry.
Bloom Filter
PaperOriginal Bloom filter paper supporting probabilistic set membership and false positives.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toHash Table
Data Structures · Foundation
Bloom filters use less memory but give probabilistic answers.
Compare with thisAlternativesCount-Min Sketch
Data Structures · Core
Count-Min Sketch organizes data with different query and update tradeoffs than Bloom Filter.
Compare with thisUsed byBloom Filter Membership Query
Searching · Core
Membership queries are the primary operation supported by a Bloom filter.
Compare with thisRelationships
View full relationship pageMembership queries are the primary operation supported by a Bloom filter.
Alternative toHash Table
Bloom filters use less memory but give probabilistic answers.
Related Algorithms
Tags
Data StructureProbabilistic Data StructureHashing