A false positive is a membership result that reports that an element may be present even though it was never inserted. Bloom filters produce false positives when hash collisions make the queried positions appear set; they never produce false negatives. section 6.13.2 section 6.13
False positives are the cost of a compact membership check. A bloom filter can safely identify elements that are definitely absent, but a positive result requires another check when existence must be guaranteed. Hashmaps or B-trees are better when false positives are unacceptable. section 6.13.4 section 6.13
The false-positive rate depends on how the bloom filter is configured and used:
- Adding more elements to a fixed-size filter raises the false-positive rate, so estimating the expected element count is important. section 6.13.5
- The relevant parameters are the number of hash functions, expected elements, and bitvector size. section 6.13.5
- False positives are acceptable when a positive result only triggers a more expensive verification; they are unsuitable when membership requires a strict guarantee. section 6.13.4
Estimating a rate
For a bloom filter expecting 1,000 elements with a 10 KB bitvector and two hash functions, the estimated false-positive rate is about 3.15%. To target at most 0.1% with 1,000 elements and two hash functions, the required bitvector is approximately 62,240 bits, or slightly less than 8 KB. section 6.13.5
Figure 6.1 A bloom filter can return all the options except for false negatives.
Use the outcome diagram to distinguish definite absence, possible presence, and the false-negative result a bloom filter does not return. section 6.13

























