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 item

Related terms

Taught in

References