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


