Bloom Filter: A Compact Data Structure in JavaScript
Introduction to Bloom Filter
A Bloom filter is a probabilistic data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set. It’s unique in that it has a certain allowance for false positives but guarantees zero false negatives. This means it might tell you that an element is in the set when it isn’t (false positive), but it will never tell you an element isn’t in the set if it is (false negative).
Core Components
- Bit Array: A large array of bits, initially set to 0.
- Hash Functions: Several hash functions that can hash an item to positions in the bit array.
Operations of Bloom Filters
- Add: Hash the item with each hash function to get array positions, and set the bits at these positions to 1.
- Test: Hash the item with each hash function to get array positions, and check if all these positions are 1. If they are, the item might be in the set; if not, the item is definitely not in the set.
Implementing Bloom Filter in JavaScript
class BloomFilter {
constructor(size = 100) {
this.size = size;
this.bitArray = new Array(size).fill(0);
}
// Simple hash functions
hash1(str) {
let hash = 0;
for (let i = 0; i < str.length; i++) {
hash += str.charCodeAt(i);
}
return hash % this.size;
}
hash2(str) {
let hash = 0;
let char;
for (let i = 0; i < str.length; i++) {
char = str.charCodeAt(i);
hash = ((hash << 5) - hash) + char;
hash |= 0;
}
return hash % this.size;
}
add(item) {
this.bitArray[this.hash1(item)] = 1;
this.bitArray[this.hash2(item)] = 1;
}
test(item) {
return !!this.bitArray[this.hash1(item)] && !!this.bitArray[this.hash2(item)];
}
}
Applications and Limitations
Applications:
- Web browsers: Caching previously visited web pages without storing them.
- Databases: Rapidly checking if an item exists without performing a full search.
Limitations:
- Inherent false positives.
- Deletion is not straightforward without introducing false negatives.
Conclusion
Bloom Filters are incredibly useful when memory efficiency and speed are paramount, and some margin of error is acceptable. Their unique characteristics make them valuable in specific scenarios where conventional data structures might falter. Grasping the essence of Bloom Filters and their implementation in JavaScript offers a remarkable tool in the arsenal of modern developers.