One Hash Bloom Filters Explained

Bloom Filter Basics

A Bloom filter is a probabilistic data structure that efficiently determines if a key is likely present in a set. It can definitively state a key is not in the set, or probabilistically state it is. Users select an acceptable false positive rate for their specific workload.

These filters use minimal memory relative to the set's size and are computationally inexpensive. This makes them suitable for high-performance data systems, such as databases, to reduce disk I/O, and in backend systems like Bluesky to minimize database queries.

Traditional Bloom Filter Operation

A standard Bloom filter consists of a bit array and 'k' hash functions. The size of the array and 'k' are chosen beforehand to achieve a desired false positive rate. To add a key, it is run through all 'k' hash functions, and the bits at the resulting locations in the array are set.

To check for a key's presence, it is hashed 'k' times, and the corresponding bit locations are checked. If any bit is zero, the key is definitely not in the set. If all bits are one, the key is probably in the set.

Optimizing with Double Hashing

While Bloom filters are efficient, computing 'k' independent hashes per key can still be resource-intensive for very high-performance systems. Research by Kirsch and Mitzenmacher in 2008 demonstrated that two hash functions can achieve comparable results.

By deriving the i-th location using the formula (hash_1 + i*hash_2) % n, where 'n' is the array size, the false positive rate remains effectively the same as using 'k' independent hashes, reducing the computational overhead.