--- # === IDENTITY === id: software/patterns/bloom-filters/2026 canonical_question: "How do Bloom filters and probabilistic data structures work?" aliases: - "Bloom filter tutorial" - "probabilistic set membership" - "space-efficient set lookup" - "Bloom filter false positive rate" - "Counting Bloom filter vs Cuckoo filter" - "probabilistic data structures comparison" - "Bloom filter sizing formula" - "HyperLogLog vs Bloom filter" entity_type: software_reference domain: software > patterns > Bloom Filters region: global jurisdiction: global temporal_scope: 1970-2026 # === VERIFICATION === last_verified: 2026-02-24 confidence: 0.92 version: 1.0 first_published: 2026-02-24 # === TEMPORAL VALIDITY === temporal_validity: status: stable last_breaking_change: null next_review: 2026-08-23 change_sensitivity: low # === CONSTRAINTS === constraints: - "Standard Bloom filters do NOT support element deletion — removing bits may corrupt other entries" - "False positive rate increases as filter fills — never exceed designed capacity (n)" - "Hash functions must be independent and uniformly distributed — cryptographic hashes are too slow; use murmur3, xxHash, or FNV" - "A Bloom filter can never return false negatives — if it says 'not in set', the element is definitely absent" - "Filter size (m) and hash count (k) must be fixed at creation — they cannot be changed after insertion begins" # === SKIP CONDITIONS === skip_this_unit_if: - condition: "Need exact membership queries with zero false positives" use_instead: "Hash set / hash table — deterministic O(1) lookup with no false positives" - condition: "Need to count element frequencies, not just membership" use_instead: "Count-Min Sketch — frequency estimation in sub-linear space" - condition: "Need cardinality estimation (how many distinct elements)" use_instead: "HyperLogLog — distinct count in ~1.5 KB regardless of set size" # === AGENT HINTS === inputs_needed: - key: expected_elements question: "How many elements do you expect to insert into the filter?" type: choice options: ["<10K", "10K-1M", "1M-100M", ">100M"] - key: false_positive_rate question: "What false positive rate is acceptable for your use case?" type: choice options: ["1% (9.6 bits/element)", "0.1% (14.4 bits/element)", "0.01% (19.2 bits/element)", "Not sure — recommend based on use case"] - key: deletion_needed question: "Do you need to delete elements from the filter?" type: choice options: ["No — insert-only (standard Bloom filter)", "Yes — need deletion support (Counting Bloom or Cuckoo filter)", "Not sure"] # === DISTRIBUTION === canonical_source: "https://knowledgelib.io/software/patterns/bloom-filters/2026" suggested_citation: "Source: knowledgelib.io — AI Knowledge Library (verified 2026-02-24)" # === RELATED UNITS === related_kos: depends_on: [] related_to: - id: software/system-design/multi-layer-caching/2026 label: "Multi-Layer Caching Design" - id: software/system-design/search-engine/2026 label: "Search Engine Design" solves: [] alternative_to: [] often_confused_with: [] # === SOURCES (7 authoritative sources) === sources: - id: src1 title: "Bloom filter" author: Wikipedia url: https://en.wikipedia.org/wiki/Bloom_filter type: community_resource published: 2025-12-15 reliability: high - id: src2 title: "Bloom Filters by Example" author: Bill Mill url: https://llimllib.github.io/bloomfilter-tutorial/ type: technical_blog published: 2024-03-10 reliability: high - id: src3 title: "Cuckoo Filter: Practically Better Than Bloom" author: Bin Fan, Dave Andersen, Michael Kaminsky, Michael Mitzenmacher url: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf type: academic_paper published: 2014-12-02 reliability: authoritative - id: src4 title: "Probabilistic Data Structure Showdown: Cuckoo Filters vs. Bloom Filters" author: Fast Forward Labs url: https://blog.fastforwardlabs.com/2016/11/23/probabilistic-data-structure-showdown-cuckoo-filters-vs.-bloom-filters.html type: technical_blog published: 2016-11-23 reliability: moderate_high - id: src5 title: "Bloom Filters - Introduction and Implementation" author: GeeksforGeeks url: https://www.geeksforgeeks.org/python/bloom-filters-introduction-and-python-implementation/ type: community_resource published: 2025-06-20 reliability: moderate_high - id: src6 title: "bits-and-blooms/bloom: Go package implementing Bloom filters" author: bits-and-blooms url: https://github.com/bits-and-blooms/bloom type: community_resource published: 2025-11-01 reliability: high - id: src7 title: "Bloom Filter Calculator" author: Thomas Hurst url: https://hur.st/bloomfilter/ type: community_resource published: 2025-01-15 reliability: high --- # Bloom Filters & Probabilistic Data Structures: Complete Reference ## TL;DR - **Bottom line**: Bloom filters are space-efficient probabilistic data structures that answer "is X in the set?" with configurable false positive rates and zero false negatives, using a bit array and k independent hash functions. - **Key tool/command**: `m = -n * ln(p) / (ln(2))^2` (optimal filter size formula, where n = elements, p = desired FP rate) - **Watch out for**: Standard Bloom filters do not support deletion — removing a bit corrupts other entries. Use Counting Bloom or Cuckoo filters if you need deletion. - **Works with**: Any language/platform. No external dependencies. Common libraries: `pybloom_live` (Python), `bloom-filters` (npm), `bits-and-blooms/bloom` (Go). ## Constraints - Standard Bloom filters do NOT support element deletion — removing bits may corrupt other entries - False positive rate increases as filter fills — never exceed designed capacity (n) - Hash functions must be independent and uniformly distributed — cryptographic hashes (SHA-256) are too slow for high-throughput; use murmur3, xxHash, or FNV - A Bloom filter can never return false negatives — "not in set" is always correct - Filter size (m) and hash count (k) are fixed at creation and cannot be changed after insertions begin - Thread safety is NOT built into most implementations — add synchronization (mutex/lock) for concurrent access ## Quick Reference | Structure | Space (bits/element) | Insert | Query | Delete | FP Rate | Best For | |---|---|---|---|---|---|---| | Standard Bloom Filter | 9.6 (at 1% FP) | O(k) | O(k) | No | Configurable | Set membership, dedup | | Counting Bloom Filter | 3-4x standard | O(k) | O(k) | Yes | Same as standard | Membership with deletion | | Cuckoo Filter | ~12 bits (at 3% FP) | O(1) amortized | O(1) | Yes | Lower at <3% FP | Membership + deletion | | HyperLogLog | ~1.5 KB fixed | O(1) | O(1) | No | ~2% std error | Cardinality estimation | | Count-Min Sketch | O(1/e * ln(1/d)) | O(d) | O(d) | No | Over-counts only | Frequency estimation | | Quotient Filter | 10-25% more than Bloom | O(1) amortized | O(1) amortized | Yes | Configurable | Cache-friendly membership | **Key formulas** (standard Bloom filter): [src1] | Parameter | Formula | Description | |---|---|---| | Optimal bit array size (m) | `m = -n * ln(p) / (ln(2))^2` | n = expected elements, p = target FP rate | | Optimal hash count (k) | `k = (m / n) * ln(2)` | Minimizes FP for given m and n | | False positive probability | `p = (1 - e^(-kn/m))^k` | Actual FP rate after n insertions | | Bits per element (1% FP) | ~9.6 bits | Independent of element size | | Bits per element (0.1% FP) | ~14.4 bits | Each 10x reduction costs ~4.8 bits | ## Decision Tree ``` START: What problem are you solving? | +-- Set membership ("is X in the set?")? | | | +-- Need deletion? | | +-- YES --> Counting Bloom Filter (if space OK) or Cuckoo Filter (if space-constrained) | | +-- NO --> Standard Bloom Filter (most space-efficient) | | | +-- Need exact membership (zero false positives)? | +-- YES --> Use a hash set instead (not a probabilistic structure) | +-- NO --> Bloom Filter family (see above) | +-- Cardinality estimation ("how many distinct elements?")? | +-- YES --> HyperLogLog (~1.5 KB, ~2% error) | +-- Frequency estimation ("how often does X appear?")? | +-- YES --> Count-Min Sketch (over-counts, never under-counts) | +-- Need cache-friendly disk operations? | +-- YES --> Quotient Filter (better locality than Bloom) | +-- DEFAULT --> Standard Bloom Filter (simplest, most battle-tested) ``` ## Step-by-Step Guide ### 1. Calculate optimal filter parameters Determine the bit array size (m) and number of hash functions (k) based on your expected element count (n) and desired false positive rate (p). [src7] ```python import math def bloom_filter_params(n, p): """Calculate optimal Bloom filter parameters. Args: n: Expected number of elements p: Desired false positive rate (e.g., 0.01 for 1%) Returns: (m, k): bit array size, number of hash functions """ m = -n * math.log(p) / (math.log(2) ** 2) k = (m / n) * math.log(2) return int(math.ceil(m)), int(math.ceil(k)) # Example: 1 million elements, 1% false positive rate m, k = bloom_filter_params(1_000_000, 0.01) print(f"Bit array size: {m:,} bits ({m / 8 / 1024:.1f} KB)") print(f"Hash functions: {k}") # Output: Bit array size: 9,585,059 bits (1170.5 KB), Hash functions: 7 ``` **Verify**: Run the function with n=1000000, p=0.01 --> expect m ~ 9.6M bits, k = 7 ### 2. Implement the Bloom filter Create a bit array of size m and implement add/query operations using k hash functions. Use double hashing (two base hashes combined) to simulate k independent hash functions efficiently. [src2] ```python import mmh3 # pip install mmh3==4.1.0 from bitarray import bitarray # pip install bitarray==2.9.2 class BloomFilter: def __init__(self, n, p=0.01): self.n = n self.p = p self.m = int(-n * math.log(p) / (math.log(2) ** 2)) self.k = int((self.m / n) * math.log(2)) self.bits = bitarray(self.m) self.bits.setall(0) self.count = 0 def _hashes(self, item): """Generate k hash positions using double hashing.""" h1 = mmh3.hash(str(item), 0) % self.m h2 = mmh3.hash(str(item), 1) % self.m for i in range(self.k): yield (h1 + i * h2) % self.m def add(self, item): for pos in self._hashes(item): self.bits[pos] = 1 self.count += 1 def __contains__(self, item): return all(self.bits[pos] for pos in self._hashes(item)) @property def estimated_fp_rate(self): """Current estimated false positive rate.""" return (1 - math.exp(-self.k * self.count / self.m)) ** self.k ``` **Verify**: Insert 1000 elements, test 10000 non-existent elements --> false positive count should be near 1% of 10000 (roughly 100 +/- 30) ### 3. Test actual false positive rate Always validate your filter against the theoretical FP rate after deployment. [src1] ```python import random import string def test_fp_rate(n=100_000, p=0.01): bf = BloomFilter(n, p) # Insert n elements inserted = set() for _ in range(n): item = ''.join(random.choices(string.ascii_letters, k=12)) bf.add(item) inserted.add(item) # Test with elements NOT in the set false_positives = 0 test_count = 100_000 for _ in range(test_count): item = ''.join(random.choices(string.ascii_letters, k=12)) if item not in inserted and item in bf: false_positives += 1 actual_fp = false_positives / test_count print(f"Target FP: {p:.4f}, Actual FP: {actual_fp:.4f}") print(f"Filter size: {bf.m / 8 / 1024:.1f} KB, Hash functions: {bf.k}") test_fp_rate() # Expected output: Target FP: 0.0100, Actual FP: ~0.0095-0.0105 ``` **Verify**: Actual FP rate should be within 10% of target p ### 4. Choose the right variant for your use case If your requirements include deletion, switch to a Counting Bloom Filter or Cuckoo Filter. [src3] ```python # Counting Bloom Filter — supports deletion via counters instead of bits class CountingBloomFilter: def __init__(self, n, p=0.01, counter_bits=4): self.n = n self.m = int(-n * math.log(p) / (math.log(2) ** 2)) self.k = int((self.m / n) * math.log(2)) self.max_count = (1 << counter_bits) - 1 # 15 for 4-bit self.counters = [0] * self.m def _hashes(self, item): h1 = mmh3.hash(str(item), 0) % self.m h2 = mmh3.hash(str(item), 1) % self.m for i in range(self.k): yield (h1 + i * h2) % self.m def add(self, item): for pos in self._hashes(item): if self.counters[pos] < self.max_count: self.counters[pos] += 1 def remove(self, item): if item not in self: return False for pos in self._hashes(item): if self.counters[pos] > 0: self.counters[pos] -= 1 return True def __contains__(self, item): return all(self.counters[pos] > 0 for pos in self._hashes(item)) ``` **Verify**: Add "hello", check "hello" in filter (True), remove "hello", check again (False) ## Code Examples ### Python: Standard Bloom Filter with mmh3 > Full script: [python-standard-bloom-filter-with-mmh3.py](scripts/python-standard-bloom-filter-with-mmh3.py) (26 lines) ```python # Input: list of items to insert, items to query # Output: membership test results (True = possibly in set, False = definitely not) import mmh3 # pip install mmh3==4.1.0 from bitarray import bitarray # pip install bitarray==2.9.2 import math # ... (see full script) ``` ### JavaScript: Bloom Filter for Browser/Node.js > Full script: [javascript-bloom-filter-for-browser-node-js.js](scripts/javascript-bloom-filter-for-browser-node-js.js) (42 lines) ```javascript // Input: items to add, items to query // Output: boolean membership test results class BloomFilter { constructor(expectedItems, fpRate = 0.01) { this.m = Math.ceil(-expectedItems * Math.log(fpRate) / (Math.log(2) ** 2)); # ... (see full script) ``` ### Go: Bloom Filter using bits-and-blooms ```go // Input: items to add, items to query // Output: boolean membership test results package main import ( "fmt" "github.com/bits-and-blooms/bloom/v3" // v3.7.0 ) func main() { // Create filter: 1M expected elements, 0.1% FP rate filter := bloom.NewWithEstimates(1_000_000, 0.001) // Add elements filter.AddString("user:12345") filter.AddString("user:67890") // Query membership fmt.Println(filter.TestString("user:12345")) // true fmt.Println(filter.TestString("user:99999")) // false (definitely not in set) // Check filter stats fmt.Printf("Bit array size: %d bits\n", filter.Cap()) fmt.Printf("Hash functions: %d\n", filter.K()) // Serialize for storage/transfer data, _ := filter.MarshalJSON() fmt.Printf("Serialized size: %d bytes\n", len(data)) } ``` ## Anti-Patterns ### Wrong: Using a single hash function ```python # BAD — single hash function causes excessive collisions and high FP rate import hashlib class BadBloomFilter: def __init__(self, size): self.bits = [False] * size def add(self, item): h = int(hashlib.md5(item.encode()).hexdigest(), 16) % len(self.bits) self.bits[h] = True # Only one bit set per element def __contains__(self, item): h = int(hashlib.md5(item.encode()).hexdigest(), 16) % len(self.bits) return self.bits[h] ``` ### Correct: Using k independent hash functions with double hashing ```python # GOOD — k hash functions spread bits optimally, matching theoretical FP rate import mmh3 class GoodBloomFilter: def __init__(self, expected, fp_rate=0.01): self.m = int(-expected * math.log(fp_rate) / (math.log(2) ** 2)) self.k = max(1, int((self.m / expected) * math.log(2))) self.bits = bitarray(self.m) self.bits.setall(0) def add(self, item): for seed in range(self.k): self.bits[mmh3.hash(str(item), seed) % self.m] = 1 def __contains__(self, item): return all(self.bits[mmh3.hash(str(item), seed) % self.m] for seed in range(self.k)) ``` ### Wrong: Not sizing the filter before use ```python # BAD — arbitrary size without considering element count or FP rate bf = BloomFilter.__new__(BloomFilter) bf.m = 1000 # Way too small for 100K elements bf.k = 3 bf.bits = bitarray(1000) bf.bits.setall(0) # After inserting 100K items, nearly all bits are 1 --> FP rate approaches 100% ``` ### Correct: Calculate parameters from requirements ```python # GOOD — size derived from actual requirements n = 100_000 # expected elements p = 0.01 # 1% false positive rate bf = BloomFilter(n, p) # m ~ 958,506 bits (117 KB), k = 7 --> FP rate stays at ~1% ``` ### Wrong: Trying to delete from a standard Bloom filter ```python # BAD — clearing bits may corrupt other entries def bad_remove(bf, item): for seed in range(bf.k): idx = mmh3.hash(str(item), seed) % bf.m bf.bits[idx] = 0 # This may unset bits shared with other elements! ``` ### Correct: Use Counting Bloom Filter or Cuckoo Filter for deletion ```python # GOOD — counters allow safe deletion cbf = CountingBloomFilter(100_000, p=0.01, counter_bits=4) cbf.add("item_a") cbf.add("item_b") cbf.remove("item_a") # Safe — decrements counters, does not affect item_b print("item_a" in cbf) # False print("item_b" in cbf) # True ``` ## Common Pitfalls - **Undersized filter**: Creating a filter too small for actual data volume causes FP rate to skyrocket as bits saturate. Fix: Always calculate m from `m = -n * ln(p) / (ln(2))^2` before creating the filter. [src1] - **Wrong number of hash functions**: Using too many or too few hash functions relative to m/n ratio wastes space or increases FP. Fix: Use `k = (m/n) * ln(2)` and round to nearest integer. [src7] - **Cryptographic hash functions**: Using SHA-256 or MD5 as hash functions is orders of magnitude slower than necessary. Fix: Use murmur3, xxHash, or FNV-1a — non-cryptographic hashes with excellent distribution. [src2] - **No thread safety**: Most Bloom filter implementations are not thread-safe. Fix: Wrap add/query in a mutex or use a concurrent-safe implementation (e.g., `sync.Mutex` in Go). [src6] - **Unbounded growth**: Continuously inserting beyond capacity n without monitoring FP rate. Fix: Track insertion count and create a new, larger filter when approaching n. Use Scalable Bloom Filters for auto-growing. [src1] - **Confusing false positive with false negative**: Bloom filters never produce false negatives. If "not in set" is returned, the element is definitely absent. Fix: Understand that only "possibly in set" needs verification against the source of truth. [src5] ## When to Use / When Not to Use | Use When | Don't Use When | Use Instead | |---|---|---| | Checking if an element was seen before (dedup) | You need exact set membership with zero errors | Hash set / hash table | | Pre-filtering expensive disk/network lookups | You need to enumerate or iterate set members | Sorted set or B-tree | | Spell-checking dictionaries | You need to delete elements frequently | Cuckoo filter or hash set | | Network packet routing (is destination in cache?) | Dataset fits comfortably in memory as a hash set | Hash set (simpler, deterministic) | | Distributed systems: reducing cross-node queries | You need element frequency counts | Count-Min Sketch | | Database: avoiding unnecessary disk reads (LSM trees) | You need cardinality estimation (count distinct) | HyperLogLog | ## Important Caveats - The theoretical FP formula `p = (1 - e^(-kn/m))^k` is an approximation. Actual FP rate is slightly higher due to hash collisions and non-perfect independence between hash functions. Always test empirically. - Scalable Bloom Filters (SBF) allow growth by adding new filter layers but increase query time linearly with the number of layers. Consider pre-sizing if possible. - Counting Bloom Filters use 3-4x more memory than standard Bloom filters. Cuckoo filters are more space-efficient when deletion is needed and FP rate target is below 3%. - Bloom filters serialized across systems must agree on hash function, seed, bit array encoding, and endianness. Always use the same library version on both ends. - In distributed databases (Cassandra, HBase), Bloom filters are used per-SSTable. Misconfigured bloom_filter_fp_chance causes excessive disk reads — tune per table based on read patterns. ## Related Units - [Multi-Layer Caching Design](/software/system-design/multi-layer-caching/2026) - [Search Engine Design](/software/system-design/search-engine/2026)