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 →
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.
Related concepts
- false positiveproduces · A false positive is a result that incorrectly indicates a condition or class is present when it is absent.
- hash functionuses · A hash function deterministically maps input data to a value in a bounded output range, commonly for indexing, lookup, 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.
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.