Bloom filter
A Bloom filter is a space-efficient probabilistic data structure for testing set membership that permits false positives but not false negatives.
Advanced Algorithms and Data Structures
A Bloom filter is a space-efficient probabilistic data structure for testing set membership that can report false positives but not false negatives.
- How it is used
- Filters membership checks so definite misses avoid expensive server or disk access.
- How deep it goes
- Develops bit-level insertion and lookup, constructor sizing, false-positive reasoning, and running-time qualifications.
- Examples
- Uses server-backed email contacts, a four-bit collision example, and database-file membership checks.
- What you can do after
- Build it from scratch with packed bits and deterministic hashes, then size it for an expected capacity and error tolerance.
Read how Advanced Algorithms and Data Structures explains bloom filter →
The Coder Cafe
A bloom filter is a probabilistic data structure that tests set membership using a bit array and multiple hash functions, allowing false positives but not false negatives for inserted elements.
- How it is used
- Uses memory-efficient membership checks to rule out absent data before expensive lookups.
- How deep it goes
- Works through bit operations, collisions, multiple hashes, sizing considerations and cache behavior, without providing a complete implementation.
- Examples
- Illustrates collisions with a five-bit filter and applications in Cassandra, CDNs, Ethereum and network security.
- What you can do after
- Build it from scratch at the bit-operation level and evaluate when its false positives, fixed size and deletion limit fit a use case.
ScyllaDB in Action
A Bloom filter is a probabilistic membership structure that can report possible membership or definite non-membership with a configurable false-positive rate.
- How it is used
- Narrows SSTable searches by rejecting files that cannot contain a requested partition key.
- How deep it goes
- Explains bit arrays, multiple hashes, collisions, false positives, and filter sizing, but stops short of implementation configuration.
- Examples
- Uses a ten-bit filter with hash positions 2, 4, and 6 to demonstrate membership checks and collisions.
- What you can do after
- Evaluate how probabilistic membership checks reduce unnecessary SSTable reads while allowing false positives.
Also covered in
What to know first
- MapA map is an associative data structure that stores key-value associations and supports retrieving values by key.
- hash functionA hash function is a deterministic function that maps input data to a hash value, typically of fixed size, for uses such as lookup, indexing, comparison, or integrity checking.
- bitA bit is a binary digit and unit of digital information that represents one of two distinguishable values, conventionally 0 or 1.
Related concepts
- false positiveproduces · A false positive is a positive result that incorrectly indicates a target condition is present when it is absent.
- hash functionuses · A hash function is a deterministic function that maps input data to a hash value, typically of fixed size, for uses such as lookup, indexing, comparison, or integrity checking.
- binary vectorhas part · A binary vector is an ordered sequence of elements, each restricted to one of two values, conventionally zero or one.
Questions about bloom filter
What is bloom filter?
A Bloom filter is a space-efficient probabilistic data structure for testing set membership that permits false positives but not false negatives.
Which Manning books explain bloom filter?
Advanced Algorithms and Data Structures, The Coder Cafe and ScyllaDB in Action.
What should I know before learning bloom filter?
Manning books that teach bloom filter usually introduce Map, hash function, bit and e first.
What is bloom filter a kind of?
Bloom filter is a kind of probabilistic data structure. A probabilistic data structure provides approximate or uncertain results with probabilistic guarantees in exchange for reduced memory use or faster computation.
What are the parts of bloom filter?
Bloom filter includes binary vector.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.


