Lesson 10 · Advanced structures and algorithms

Bloom Filters

A Bloom Filter is a probabilistic data structure that can tell you if an item is definitely not in a set, or possibly in a set, using negligible memory.

Membership Without Storing Anything

A hash set answers 'have I seen this?' in O(1), but it stores every element. A set of a billion URLs averaging 60 bytes needs 60 gigabytes plus the table's own overhead. When the only question is membership, storing the elements is paying for information you never read back.

A bloom filter answers the same question while storing no elements at all. It is a bit array of m bits, all initially 0, plus k independent hash functions, each mapping an element to a position in that array.

To insert an element, hash it with all k functions and set the k resulting bits to 1. Bits already set stay set — nothing records which element set them.

To query an element, hash it the same way and check those k bits. If any is 0, the element was definitely never inserted, because insertion would have set it. If all are 1, the element is probably present — but the bits may have been set by other elements coincidentally.

So the structure gives an asymmetric answer, and the asymmetry is the whole design: false positives are possible, false negatives are not. It may claim something is present when it is not; it will never claim something is absent when it is.

The size is independent of what is stored. Ten bits per element covers a 60-byte URL or a 4-byte integer identically, because only the hash outputs matter. That is where the compression comes from — a billion URLs fit in about 1.2 gigabytes instead of 60.

A bit array plus k hash functions; no elements are retained
Insert sets k bits; query checks whether all k are set
Any zero bit proves absence; all ones only suggests presence
Space per element is constant regardless of element size

Why the Asymmetry Is Useful

A structure that sometimes lies seems unusable until you see the pattern it fits: a bloom filter is a cheap filter in front of an expensive check.

The arrangement is always the same. Query the filter first. If it says definitely absent, skip the expensive operation entirely — and that answer is always correct. If it says maybe present, perform the expensive check to find out. The filter never causes a wrong final answer; it only removes work.

So a 1% false positive rate means 1% of negative queries do an unnecessary expensive lookup, while 99% of them are eliminated for free. The correctness of the system is unaffected because the authoritative check still runs whenever the filter says maybe.

This is why the direction of the error matters so much. A false negative would cause the expensive check to be skipped when it should have run, producing a genuinely wrong answer. False positives only cost time. A structure with the errors reversed would be useless for this pattern.

The concrete applications all have this shape. Databases — Cassandra, HBase, LevelDB, RocksDB — keep a bloom filter per on-disk table file, so a lookup skips reading files that certainly do not contain the key, avoiding disk I/O that dominates the cost. Web caches and CDNs avoid a backend fetch for content known to be absent. Chrome historically used one to check URLs against a malware list before making a network call. Bitcoin SPV clients use them to request only potentially relevant transactions.

The general form is worth stating: use a bloom filter whenever a negative answer is common and the authoritative check is expensive. If most queries are positive, the filter rarely saves anything and is not worth its memory.

Always a cheap pre-filter in front of an authoritative check
'Definitely absent' is always correct, so nothing is wrongly skipped
A false positive costs one wasted lookup, never a wrong answer
Worth it when negatives are common and the real check is expensive

Sizing and the Optimal k

The false positive rate is tunable, and the formulas are standard exam material.

For n elements in m bits with k hash functions, the probability that a given bit is still 0 after all insertions is (1 − 1/m)^(kn) ≈ e^(−kn/m). A false positive requires all k checked bits to be 1, so the rate is approximately (1 − e^(−kn/m))^k.

Minimising that expression over k gives the optimal number of hash functions: k = (m/n) · ln 2, or about 0.693 bits-per-element. Substituting it back yields the required size for a target error rate p: m = −(n · ln p) / (ln 2)².

Working the numbers gives figures worth remembering. A 1% error rate needs about 9.6 bits per element and 7 hash functions. 0.1% needs about 14.4 bits and 10 functions. 10% needs about 4.8 bits and 3.

The striking part is how slowly the cost grows: each additional factor of ten in accuracy costs only about 4.8 more bits per element. Even a very low error rate stays far below the cost of storing the elements themselves.

The behaviour of k is worth understanding rather than just computing. Too few hash functions means each element sets few bits, so collisions between different elements become likely. Too many means each element sets many bits, filling the array faster and pushing the whole structure toward all-ones. The optimum sits where the array ends up roughly half full of ones, which is a useful sanity check on an implementation.

One practical note: k independent hash functions are not needed in practice. Double hashing derives all k from two base hashes as h1 + i·h2, and Kirsch and Mitzenmacher showed this preserves the error bounds. Implementations typically compute one 128-bit MurmurHash and split it.

The parameters must be chosen from an estimate of n in advance. A bloom filter cannot be resized, and inserting far more than planned degrades the error rate sharply — eventually every query returns a false positive once the array is saturated.

Space required per element by target error rate
False positive rate	Bits per element	Optimal k
10%	≈ 4.8	3
1%	≈ 9.6	7
0.1%	≈ 14.4	10
0.01%	≈ 19.2	13

Error rate ≈ (1 − e^(−kn/m))^k
Optimal k = (m/n)·ln 2; required m = −n·ln p / (ln 2)²
Each tenfold accuracy gain costs only ~4.8 more bits per element
Size for n in advance — a bloom filter cannot be resized

Key reference

Terms, operations, and practical uses

Mechanics

Bit ArrayThe underlying storage is a single array of m bits, initially all set to 0.
Multiple HashesWhen an item is added, it is processed by k different hash functions, yielding k indices in the bit array to flip to 1.
Membership QueryTo check existence, hash the item k times. If all k bits are 1, it 'probably' exists. If any bit is 0, it definitively does not exist.

Properties

False PositivesOccur when the k bits queried were flipped to 1 by a combination of other inserted elements.
No False NegativesIf an element was actually inserted, its k bits were irrevocably flipped to 1, meaning it will never report as missing.
No DeletionsStandard Bloom Filters cannot delete items, because flipping a 1 back to 0 might break the record of other colliding items.

Tuning and Variants

Optimal ParametersThe math dictates that for n items and a target false positive rate p, the optimal bit array size is m = - (n * ln p) / (ln 2)^2.
Counting Bloom FilterReplaces single bits with small integer counters, allowing deletions at the cost of vastly increased memory usage.
Database UsageUsed extensively in databases like Cassandra and PostgreSQL to instantly verify if a disk read is necessary for a query.

Implementation

Add and query a Bloom filter

class BloomFilter:
    def __init__(self, size):
        self.bit_array = [0] * size
    def add(self, item):
        for i in range(3):
            # 3 hash functions
            idx = hash(item + str(i)) % len(self.bit_array)
            self.bit_array[idx] = 1
    def check(self, item):
        for i in range(3):
            idx = hash(item + str(i)) % len(self.bit_array)
            if self.bit_array[idx] == 0:
                return False
        return True
bloom = BloomFilter(64)
bloom.add('cat')
print('Possibly present' if bloom.check('cat') else 'Definitely absent')

#include <iostream>
#include <string>
#include <vector>
using namespace std;
class BloomFilter {
    vector<bool> bit_array;
    size_t slot(const string& item, int i) const {
        return hash<string> {
        }
        (item + to_string(i)) % bit_array.size();
    }
    public:
    BloomFilter(int size) : bit_array(size, false) {
    }
    void add(const string& item) {
        for (int i = 0; i < 3; i++) // 3 hash functions
        bit_array[slot(item, i)] = true;
    }
    bool check(const string& item) const {
        for (int i = 0; i < 3; i++)
        if (!bit_array[slot(item, i)]) return false;
        return true;
    }
};
int main() {
    BloomFilter bloom(64);
    bloom.add("cat");
    cout << (bloom.check("cat") ? "Possibly present" : "Definitely absent") << '\n';
}

public class Main {
    static class BloomFilter {
        boolean[] bitArray;
        BloomFilter(int size) {
            bitArray = new boolean[size];
        }
        private int slot(String item, int i) {
            return Math.abs((item + i).hashCode()) % bitArray.length;
        }
        void add(String item) {
            for (int i = 0; i < 3; i++) // 3 hash functions
            bitArray[slot(item, i)] = true;
        }
        boolean check(String item) {
            for (int i = 0; i < 3; i++)
            if (!bitArray[slot(item, i)]) return false;
            return true;
        }
    }
    public static void main(String[] args) {
        BloomFilter bloom = new BloomFilter(64);
        bloom.add("cat");
        System.out.println(bloom.check("cat") ? "Possibly present" : "Definitely absent");
    }
}

Watch it run

Step through it

Running on add "apple", then query "apple"

Output

Read all 13 Steps

Empty filter A bit array of 8 bits, all zero, plus k = 2 independent hash functions. It stores no keys — only bits.
hash 'apple' The first hash of 'apple' picks bit 1.
Second hash The second hash picks bit 5. Every insert sets k bits, not one — that is what separates it from a hash table.
Set both Both bits flip to 1. 'apple' itself is never stored anywhere.
hash 'berry' Now insert 'berry'. Its hashes land on bits 3 and 6.
Set both Four bits are now set. Memory used is constant no matter how long the keys were.
Query 'apple' Check 'apple': hash to bits 1 and 5 and test them.
Both set → maybe Both bits are 1, so the answer is 'possibly present'. It is never a certain yes.
Query 'cherry' Check a key that was never inserted. Its hashes land on bits 0 and 3.
One bit is 0 Bit 0 is still zero. A single zero bit proves the key was never inserted — this is the definite no.
The false positive Now query 'date', whose hashes happen to land on bits 1 and 6 — bits set by two different earlier keys.
Collision Both bits are 1, so the filter answers 'possibly present' for a key it never saw. That is a false positive, and it cannot be avoided — only tuned.
The tradeoff More bits or more hash functions lower the false-positive rate but cost memory and time. False negatives are impossible: a stored key always sets its own bits.

What It Cannot Do

The limitations are as important as the capabilities, and each one has a named workaround.

No deletion. Clearing an element's k bits would also clear bits shared with other elements, creating false negatives and destroying the structure's only guarantee. A plain bloom filter is insert-only.

The fix is a counting bloom filter, which replaces each bit with a small counter — typically 4 bits. Insertion increments the k counters, deletion decrements them, and a position is considered set when its counter is above zero. It costs four times the memory and introduces counter overflow as a concern, but deletion becomes safe.

No enumeration. The filter cannot list what it contains, because nothing is stored. There is no way to iterate, and no way to recover an element from the bits.

No resizing. The parameters are fixed at creation. Scalable bloom filters address this by chaining a series of filters, adding a new and larger one with a tighter error rate when the current one fills; a query checks all of them, so the cost grows with the chain length.

No count of occurrences. Membership is all it answers. A count-min sketch is the related structure for approximate frequency, using the same hashing idea with counters and returning an estimate that may overcount but never undercount.

Two comparisons worth being able to make. Against a hash set: the set is exact and supports deletion and iteration, but costs O(n) space proportional to the element sizes — take the set when it fits in memory, the filter when it does not. Against a cuckoo filter: it supports deletion, has better lookup locality, and is smaller at error rates below about 3%, at the cost of a more complex insertion that can fail when the structure is nearly full.

The decision rule: use a bloom filter when the data is too large to store exactly, the query is membership only, and a small false positive rate is acceptable because an authoritative check follows. If any of those three does not hold, use a hash set.

Deletion is impossible — it would create false negatives
Counting bloom filters allow it at 4× the memory
No enumeration, no resizing, no frequency counts
Use a hash set when the data fits and exactness is required