> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/data_structures/bloom_filter.md).

# Bloom filter

## Basic idea

A probabilistic set: tells you whether an element is *possibly in* the set or *definitely not*. Uses $k$ hash functions to set bits in an $m$-bit array. Cannot have false negatives; false-positive rate is tunable.

## Key formulas

* False-positive rate: $p \approx \left(1 - e^{-kn/m}\right)^k$
* Optimal $k$: $k^\* = (m/n)\ln 2$
* Bits per element for FP rate $p$: $m/n = -\log\_2 p / \ln 2 \approx 1.44 \log\_2(1/p)$