Bloom Filter

Updated September 30, 20263 min read

In short

A Bloom filter is a compact probabilistic data structure that tells you an item is definitely not in a set or probably is, while using very little memory.

What is a Bloom filter?

A Bloom filter is a space-efficient data structure for testing whether an item belongs to a set. It can say with certainty that an item is not in the set, but when it says an item is present, there is a small chance it is wrong, which is called a false positive. In exchange for that uncertainty, it uses a tiny fraction of the memory a full hash set would need, because it never stores the items themselves. It was invented by Burton Howard Bloom in 1970.

A Bloom filter is an array of m bits, all starting at 0, plus k different hash functions. To add an item, you hash it k times and set the bit at each resulting position to 1. To check an item, you hash it the same way: if any of those bits is 0, the item was definitely never added, and if all of them are 1, it was probably added, although other items may have set those same bits. The false positive rate depends on the array size, the number of hash functions, and how many items are stored; with about 10 bits per item and 7 hash functions, it is just under 1 percent.

It is like a doorman with a vague memory of faces: if he has never seen anyone like you, you are definitely not on the list, but if you look familiar, he still checks the real guest list. Bloom filters serve as a cheap first check in front of something expensive. Databases built on LSM trees keep one per data file to skip files that can't contain a key, caches use them to avoid storing items that have been requested only once, and services have used them to check URLs or passwords against huge blocklists without downloading the whole list.

A Bloom filter is often confused with a hash set. A hash set stores the actual items, so it answers exactly and lets you list or remove them, while a Bloom filter stores only bits, so it can't list its contents and gives some false positives, though never false negatives. A standard Bloom filter also can't delete items, since clearing a bit could erase other items too; counting Bloom filters and cuckoo filters are variants that support deletion.

Key takeaways

A Bloom filter answers either definitely not or probably yes for set membership.
It never gives false negatives, but it can give false positives.
It stores only a bit array, never the items, so it uses very little memory.
Adding and checking an item take O(k) time, where k is the number of hash functions.
It is a cheap first check that avoids expensive disk reads, network calls, or database lookups.

Example

A minimal Bloom filter in Pythonpython

SIZE, HASHES = 1000, 5
bits = [0] * SIZE

def positions(item):  # k bit positions per item, one from each seeded hash
    return [hash((seed, item)) % SIZE for seed in range(HASHES)]

def add(item):
    for p in positions(item):
        bits[p] = 1

def might_contain(item):
    return all(bits[p] for p in positions(item))  # any 0 bit means definitely absent

add("alice@example.com")
print(might_contain("alice@example.com"), might_contain("bob@example.com"))  # True False (almost always)

Readers ask

Can a Bloom filter give false negatives?

No. If an item was added, all of its bits are set to 1, so the filter always reports it as possibly present. Only false positives are possible, when other items happen to have set all the same bits.

How big should a Bloom filter be?

It depends on how many items you expect and what false positive rate you can accept. As a rule of thumb, about 10 bits per item with 7 hash functions gives a rate just under 1 percent, and each extra 5 bits per item cuts it roughly tenfold.

What is the difference between a Bloom filter and a hash set?

A hash set stores every item and answers membership exactly, but it needs memory for all the items. A Bloom filter stores only bits, so it is far smaller, but it can return false positives and can't list or, in its basic form, remove items.