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.

The Cost of Hash Sets

Hash Sets are excellent for O(1) membership queries, but they store the actual items. When tracking whether a user ID exists in a database of a billion users, a Hash Set would require tens of gigabytes of RAM. Bloom Filters offer a space-efficient alternative.

Multiple Hash Functions

A Bloom Filter consists of a single bit array and a handful of different hash functions. When an item is added, it is passed through all hash functions to generate several indices. The bits at those specific indices are then flipped to 1.

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.

Code example

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')

class BloomFilter {
    vector<bool> bit_array;
public:
    BloomFilter(int size) : bit_array(size, false) {}
    void add(string item) {
        // Hash and flip bits to true
        bit_array[hash<string>{}(item) % bit_array.size()] = true;
    }
    bool check(string item) {
        // If any bit is false, return false
        return bit_array[hash<string>{}(item) % bit_array.size()];
    }
};

class BloomFilter {
    boolean[] bitArray;
    BloomFilter(int size) { bitArray = new boolean[size]; }
    void add(String item) {
        // Simulate 3 hash functions
        bitArray[Math.abs(item.hashCode()) % bitArray.length] = true;
    }
    boolean check(String item) {
        return bitArray[Math.abs(item.hashCode()) % bitArray.length];
    }
}

Inputadd "apple", then query "apple"

OutputPossibly present

Example

Run the example step by step

Output

Probabilistic Queries

To check if an item exists, we hash it again. If any of the resulting bit indices are 0, the item is definitely not in the set. If all bits are 1, the item is probably in the set. False positives are possible due to hash collisions, but false negatives are impossible.

Tuning the Error Rate

By carefully choosing the size of the bit array and the number of hash functions based on the expected number of elements, engineers can tune the false positive rate to exactly what the application tolerates (e.g., 1%), fitting a billion records into just a few megabytes.