Bloom Filter
A space-efficient probabilistic set-membership structure that can return false positives but never false negatives for inserted elements.
Data-Structure Context
A Bloom filter represents set membership with a bit array and several hash functions. It is useful in LSM-tree, cache, and network designs when a cheap probabilistic test can avoid an unnecessary disk access or remote lookup.
Error and Storage Boundary
A conventional Bloom filter can return false positives but not false negatives for items that were inserted correctly. Direct deletion is not supported without changing the structure; counting Bloom filters and related variants introduce different memory and correctness trade-offs.
Related Data Structures
- Hash Function
- LSM Tree
- False Positive
- Probabilistic Data Structure