Bloom filter
A compact, probabilistic set that can say "definitely not present" or "probably present", using a bit array and several hash functions.
In more detail
Adding an item sets k bits chosen by k hashes; a query checks those k bits and answers "absent" if any is unset. It never gives false negatives, but can give false positives when other items happen to have set all k bits. It stores no items, only bits, so it uses little memory and cannot list or, in its basic form, delete what it holds.
Example
Bloom(128, 3) # 128 bits, 3 hash positions per itemRelated terms
- bit array — An array of single bits, each 0 or 1, used to record yes-or-no facts very compactly.
- false positive — A check result that claims something is true when it is not, such as a test passing on broken code or a tool flagging correct code.
- false negative — A result that wrongly says "no" when the true answer is "yes".
- counting Bloom filter — A Bloom filter variant that keeps a small counter instead of a single bit in each position, so items can be removed.
- probabilistic data structure — A data structure that trades a small, controllable chance of a wrong answer for large savings in memory or time.
Taught in
- Bloom Filters: Membership Without The Data — Algorithms & Data Structures for Working Engineers