Bloom Filters

A space-efficient way to say "definitely no" or "probably yes".

The idea

Checking if a username is taken usually requires a slow database query. A Bloom Filter is a tiny in-memory data structure that sits in front of the database. It can instantly tell you if the username is definitely available. If it says the username is probably taken, only then do you query the slow database to be sure.

How it works

To add an item, you run it through multiple hash functions (e.g. 3). Each hash function outputs an index. You flip the bits at those indices to 1. To check if an item exists, run it through the same hash functions. If ANY of those bits are 0, the item definitely does not exist. If ALL bits are 1, it probably exists (a false positive caused by overlapping bits from other items).

# Conceptual Bloom Filter
bit_array = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

def add_to_filter(item):
    idx1 = hash1(item) % 10
    idx2 = hash2(item) % 10
    bit_array[idx1] = 1
    bit_array[idx2] = 1

def check_filter(item):
    idx1 = hash1(item) % 10
    idx2 = hash2(item) % 10
    if bit_array[idx1] == 1 and bit_array[idx2] == 1:
        return "PROBABLY YES" # Might be a false positive
    return "DEFINITELY NO"    # 100% accurate

Cost

Space Complexity: O(1). You can represent millions of items in a few megabytes. Time Complexity: O(k) where k is the number of hash functions (extremely fast). The trade-off is the False Positive rate.

Watch out for

• You cannot delete: If you try to remove an item by flipping its bits back to 0, you might accidentally corrupt another item that shared those same bits! Standard Bloom Filters are append-only.
• Sizing: If you add too many items to a small Bloom filter, eventually all bits become 1, and every check returns "Probably Yes", rendering it useless.