liveBook · Manning

Bloom filter

A Bloom filter is a space-efficient probabilistic data structure for testing set membership that permits false positives but not false negatives.

How 3 Manning books explain it

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.

Read how The Coder Cafe 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.

Read how ScyllaDB in Action explains bloom filter →

Also covered in

What to know first

Related concepts

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.