Bloom Filter Data Structure Visualizer

How to Use

Initialize: Set size (e.g., 20) and hash functions (e.g., 3) and click "Initialize"
Sample Data: Click Sample Data to populate with examples.
Add: Enter element (e.g., "apple") and click "Add"
Test: Enter element to test if it might be in the set
Clear: Reset the filter to all zeros

Bloom Filter Concept

Bloom Filter is a space-efficient probabilistic data structure for testing set membership.

Key Characteristics:

Uses bit array and multiple hash functions
No false negatives (if says "no", definitely not in set)
Possible false positives (if says "yes", might be in set)
Cannot delete elements (variants exist)
Extremely space efficient

How it Works: To add an element, hash it with k different hash functions to get k array positions, then set those bits to 1. To test membership, hash the element and check if all k bits are set to 1.

False Positive Rate: Probability ≈ (1 - e^(-kn/m))^k, where k = hash functions, n = elements added, m = bit array size.

Applications

Web crawling (avoiding duplicate URLs)
Database query optimization
Network routing and caching
Spell checkers and dictionaries
Distributed systems (membership testing)

Time Complexity

Operation	Time
Add	O(k)
Test	O(k)
Space	O(m)

k = hash functions, m = bit array size

Advantages

Extremely space efficient
Fast insertion and lookup
No false negatives
Simple implementation

Limitations

False positives possible
Cannot delete elements
Cannot retrieve stored elements
Filter size must be predetermined

Parameter Selection

Optimal hash functions: k = (m/n) × ln(2)

Optimal bit array size: m = -n × ln(p) / (ln(2))²

n = expected elements, p = desired false positive rate

Bloom Filter Data Structure Visualizer

Bloom Filter Setup

Bloom Filter Operations

Hash Functions

Statistics

Bloom Filter Visualization

Operation Steps