liveBook · Manning

Bloom filter

As explained in 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.

A bloom filter answers a practical question: is an element definitely absent, or might it be present? It checks set membership with far less memory than a hashmap or hashset, but a “might be present” answer needs confirmation when certainty matters. It can produce false positives, not false negatives for inserted elements. section 6.13 section 6.13.1

The filter holds a fixed-size bitvector, not the elements themselves. To insert an element, hash it and set the selected bit to 1. To look it up, hash it again and inspect that bit: 0 means definitely absent; 1 means possibly present. Different elements can hash to the same position, so a set bit cannot identify which one was inserted. section 6.13.2

A collision in five bits

Suppose inserting “foo” sets bit 2. A lookup for “qux” also hashes to bit 2, even though “qux” was never inserted. The filter answers “possibly present”: a false positive caused by a collision. section 6.13.2

Multiple hash functions make the test more selective. Insertion sets every position they select; lookup reports “possibly present” only if every selected bit is set. Otherwise, the element is absent. More hash functions can reduce false positives, but each insertion and lookup takes more hashing work. section 6.13.3

Choose the filter around its limits:

  • Estimate how many elements you expect, choose a tolerable false-positive rate, then size the bitvector. A fixed-size filter becomes more prone to false positives as insertions accumulate. section 6.13.5 section 6.13.4
  • Use a definite “absent” result to skip unnecessary work, such as a database disk lookup. Do not use a standard bloom filter when membership must be certain or elements must be deleted: clearing a bit could affect another element. section 6.13.4 section 6.13.2
  • For latency-sensitive use, account for hash-selected bits landing in different CPU cache lines. A blocked bloom filter keeps a query’s bit checks within one cache-line-sized block. section 6.13.6

How The Coder Cafe covers it

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 it assumes
Builds on hashing and set membership while refreshing hashmaps before explaining the bitvector.
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.
How it connects
Connects hashing and hashsets to false-positive probability, database disk reads and CPU cache locality.

Also explained in

Compare how 3 books explain bloom filter →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of The Coder Cafe. The section links point to the parts of the book it draws on.