I first heard of Bloom filters from my professor at IIT Madras when talking about caching. I was young and new to the world of computer science then, but even so, I remember being fascinated by how simple yet powerful bloom filters are. After close to 9 years, I realize that this simple yet powerful data structure is still relegated to the side when someone thinks of mainstream data structures. This article is to correct that. What Are Bloom Filters? Bloom filters are a probabilistic data structure used for membership checks. They give true negatives and probable positives i.e., when I ask a bloom filter if an element exists in it, its answer would be ‘definitely not’ or ‘maybe yes’. The advantage is they do this in near-constant time using every little extra space. Curious, isn’t it? I will now explain how a bloom filter works, and you will understand the nature of their answers. A bloom filter has 2 components: k hash functions: A hash function is just a function that takes a string and outputs a mathematical ‘fingerprint’ of it.
bit array of size N: Nothing fancy, just N bits. Adding an Element When we add an element E to the bloom filter, we do the following: Hash E with each of the k hash functions and generate k hashes h1, h2…hk.
Find the reminder when each of these hashes is divided by N. Let these be r1, r2, …, rk.
Turn on the bits corresponding to r1, r2 … rk in the bloom filter’s bit array. If this is too complex to follow, let me explain the addition with a simple example using a small bloom filter with 2 hash functions and just 16 bits (2 bytes) of storage. Example: Add Bloom Filter construction: 2 hash functions: Here, I am going to use some imaginary function that gives me the values I need to explain. 16 bits storage, all set to 0 initially. The bits are indexed from 0 to 15. Step 1: Add ‘Ganesh’ hash1(‘ganesh’) = 2 hash2(‘ganesh’) = 7 So, we set the 2nd and 7th bits in our bit array to 1. Step 2: Add ‘palanikumar’
hash1(‘palanikumar’) = 5
hash2(‘palanikumar’) = 12 So, we set the 5th and 12th bits in our bit array to 1. After adding both these elements, the bits 2, 7, 5, and 12 are set to 1. Membership Check To check if an element Q is present in a filter, we do the following: Find the indexes that correspond to Q using the same method described above.
If any one of these indices is 0, that means Q is definitely not in the set. If the element had been added to the set, every one of these bits must have been turned on. If all of them are 1, it means Q ‘maybe’ in the set. Why the maybe? It is possible that these bits were turned on at separate times because of multiple other elements. Example: Check Following the same example above, let us check for ‘animal’.
hash1(‘animal’) = 6
hash2(‘animal’) = 2
But in our bit array, index 6 is not set to 1. So, we can say that ‘animal’ definitely does not exist in the set.
Now, let us check for '‘lottery’
hash1(‘lottery’) = 2
hash2(‘lottery’) = 12
In our bitarray, index 2 and 12 are indeed set to 1. But we know that ‘lottery’ is not in the set since we inserted only 2 words ‘Ganesh’ and ‘palanikumar’. This is an example of the bloom filter returning a false positive. Why Use Bloom Filters? Bloom filters are very useful as a data structure to represent sets in memory-constrained environments. They are often used in cache firmware to decide if an object is present in the cache or not before trying to access the object. Database engines like Postgres use Bloom Filters to reduce disk reads. Disk reads are the slowest operations in most systems so reducing them helps to significantly speed up queries. Bloom Filter vs Set: Evaluating Time and Space To analyze the speed vs memory footprint of Bloom filters, I prepared a small script in Python. Step 1: Define the Bloom Filter from bit array import bit array class BloomFilter: def init(self, size, num_hashes): self.size = size self.num_hashes = num_hashes self.bit_array = bitarray(size) self.bit_array.setall(0) def _hash(self, item, seed):
    return hash(item + str(seed)) % self.size

def add(self, item):
    for i in range(self.num_hashes):
        index = self._hash(item, i)
        self.bit_array[index] = 1

def check(self, item):
    for i in range(self.num_hashes):
        index = self._hash(item, i)
        if not self.bit_array[index]:
            return False
    return True Step 2: Write the Test Script import random import string import time from bloom_filter import BloomFilter def generate_random_string(length): return ''.join(random.choice(string.ascii_letters) for _ in range(length)) Parameters num_items = 1000000 num_checks = 10000 bloom_size = 10000000 num_hashes = 7 Create Data Structures bloom_filter = BloomFilter(bloom_size, num_hashes) standard_set = set() Generate Random Items and Add to Both Structures print("Adding items...") bloom_add_time = 0 set_add_time = 0 for _ in range(num_items): item = generate_random_string(10) start_time = time.time() bloom_filter.add(item) bloom_add_time += time.time() - start_time start_time = time.time() standard_set.add(item) set_add_time += time.time() - start_time print(f"Bloom Filter add time: {bloom_add_time/num_items:.6f} seconds") print(f"Standard Set add time: {set_add_time/num_items:.6f} seconds") Perform Membership Checks print(Performing membership checks...") bloom_time = 0 set_time = 0 for _ in range(num_checks): item = generate_random_string(10) start = time.time()
bloom_result = bloom_filter.check(item)
bloom_time += time.time() - start

start = time.time()
set_result = item in standard_set
set_time += time.time() - start print(f"Bloom Filter average check time: {bloom_time/num_checks:.6f} seconds") print(f"Standard Set average check time: {set_time/num_checks:.6f} seconds") Calculate False Positive Rate false_positives = sum(1 for _ in range(num_checks) if bloom_filter.check(generate_random_string(10))) false_positive_rate = false_positives / num_checks print(fFalse Positive Rate: {false_positive_rate:.2%}") Memory Usage Comparison import sys bloom_memory = sys.getsizeof(bloom_filter.bit_array) set_memory = sys.getsizeof(standard_set) print(fBloom Filter memory usage: {bloom_memory/1024:.2f} KB") print(f"Standard Set memory usage: {set_memory/1024:.2f} KB") print(f"Memory saved: {(set_memory - bloom_memory)/1024:.2f} KB") Output Adding items... Bloom Filter add time: 0.000004 seconds Standard Set add time: 0.000000 seconds . Performing membership checks... Bloom Filter average check time: 0.000002 seconds Standard Set average check time: 0.000000 seconds False Positive Rate: 0.84% Bloom Filter memory usage: 1220.78 KB Standard Set memory usage: 32768.21 KB Memory saved: 31547.43 KB. Analysis As you can see, there is a false positive rate of < 1%. The membership checks are also slightly less performant. However, the bloom filter uses just 3% of the space used by the set. In an execution environment where memory is at a premium, Bloom filters provide huge savings in space with a moderate reduction in performance. Conclusion Bloom filters are an efficient data structure for use in memory-starved environments. They have a lot of practical applications and are even used in popular tools like CDNs and database engines. Do you have any interesting use cases in which bloom filters would be helpful? Do let me know in the comments! I first heard of Bloom filters from my professor at IIT Madras when talking about caching. I was young and new to the world of computer science then, but even so, I remember being fascinated by how simple yet powerful bloom filters are. After close to 9 years, I realize that this simple yet powerful data structure is still relegated to the side when someone thinks of mainstream data structures. This article is to correct that. What Are Bloom Filters? Bloom filters are a probabilistic data structure used for membership checks. They give true negatives and probable positives i.e., when I ask a bloom filter if an element exists in it, its answer would be ‘definitely not’ or ‘maybe yes’. The advantage is they do this in near-constant time using every little extra space. Curious, isn’t it? I will now explain how a bloom filter works, and you will understand the nature of their answers. A bloom filter has 2 components: k hash functions: A hash function is just a function that takes a string and outputs a mathematical ‘fingerprint’ of it. bit array of size N: Nothing fancy, just N bits. k hash functions: A hash function is just a function that takes a string and outputs a mathematical ‘fingerprint’ of it. bit array of size N: Nothing fancy, just N bits. Adding an Element When we add an element E to the bloom filter, we do the following: Hash E with each of the k hash functions and generate k hashes h1, h2…hk. Find the reminder when each of these hashes is divided by N. Let these be r1, r2, …, rk. Turn on the bits corresponding to r1, r2 … rk in the bloom filter’s bit array. Hash E with each of the k hash functions and generate k hashes h1, h2…hk. Find the reminder when each of these hashes is divided by N. Let these be r1, r2, …, rk. Turn on the bits corresponding to r1, r2 … rk in the bloom filter’s bit array. If this is too complex to follow, let me explain the addition with a simple example using a small bloom filter with 2 hash functions and just 16 bits (2 bytes) of storage. Example: Add Bloom Filter construction: 2 hash functions: Here, I am going to use some imaginary function that gives me the values I need to explain. 2 hash functions: Here, I am going to use some imaginary function that gives me the values I need to explain. 16 bits storage, all set to 0 initially. The bits are indexed from 0 to 15. 16 bits storage, all set to 0 initially. The bits are indexed from 0 to 15. Step 1: Add ‘Ganesh’ Step 1: Add ‘Ganesh’ hash1(‘ganesh’) = 2 hash2(‘ganesh’) = 7 So, we set the 2nd and 7th bits in our bit array to 1. Step 2: Add ‘palanikumar’ hash1(‘palanikumar’) = 5 hash2(‘palanikumar’) = 12 Step 2: Add ‘palanikumar’ hash1(‘palanikumar’) = 5 hash2(‘palanikumar’) = 12 So, we set the 5th and 12th bits in our bit array to 1. After adding both these elements, the bits 2, 7, 5, and 12 are set to 1. Membership Check To check if an element Q is present in a filter, we do the following: Find the indexes that correspond to Q using the same method described above. If any one of these indices is 0, that means Q is definitely not in the set. If the element had been added to the set, every one of these bits must have been turned on. Find the indexes that correspond to Q using the same method described above. If any one of these indices is 0, that means Q is definitely not in the set. If the element had been added to the set, every one of these bits must have been turned on. must If all of them are 1, it means Q ‘maybe’ in the set. Why the maybe? It is possible that these bits were turned on at separate times because of multiple other elements. If all of them are 1, it means Q ‘maybe’ in the set. Why the maybe? It is possible that these bits were turned on at separate times because of multiple other elements. Example: Check Following the same example above, let us check for ‘animal’. hash1(‘animal’) = 6 hash2(‘animal’) = 2 But in our bit array, index 6 is not set to 1. So, we can say that ‘animal’ definitely does not exist in the set. Now, let us check for '‘lottery’ hash1(‘lottery’) = 2 hash2(‘lottery’) = 12 In our bitarray, index 2 and 12 are indeed set to 1. But we know that ‘lottery’ is not in the set since we inserted only 2 words ‘Ganesh’ and ‘palanikumar’. This is an example of the bloom filter returning a false positive. Following the same example above, let us check for ‘animal’. hash1(‘animal’) = 6 hash2(‘animal’) = 2 But in our bit array, index 6 is not set to 1. So, we can say that ‘animal’ definitely does not exist in the set. not Now, let us check for '‘lottery’ hash1(‘lottery’) = 2 hash2(‘lottery’) = 12 In our bitarray, index 2 and 12 are indeed set to 1. But we know that ‘lottery’ is not in the set since we inserted only 2 words ‘Ganesh’ and ‘palanikumar’. This is an example of the bloom filter returning a false positive. Why Use Bloom Filters? Bloom filters are very useful as a data structure to represent sets in memory-constrained environments. They are often used in cache firmware to decide if an object is present in the cache or not before trying to access the object. Database engines like Postgres use Bloom Filters to reduce disk reads. Disk reads are the slowest operations in most systems so reducing them helps to significantly speed up queries. Bloom Filter vs Set: Evaluating Time and Space To analyze the speed vs memory footprint of Bloom filters, I prepared a small script in Python. Step 1: Define the Bloom Filter from bit array import bit array class BloomFilter: def init (self, size, num_hashes): self.size = size self.num_hashes = num_hashes self.bit_array = bitarray(size) self.bit_array.setall(0) init def _hash(self, item, seed):
    return hash(item + str(seed)) % self.size

def add(self, item):
    for i in range(self.num_hashes):
        index = self._hash(item, i)
        self.bit_array[index] = 1

def check(self, item):
    for i in range(self.num_hashes):
        index = self._hash(item, i)
        if not self.bit_array[index]:
            return False
    return True def _hash(self, item, seed):
    return hash(item + str(seed)) % self.size

def add(self, item):
    for i in range(self.num_hashes):
        index = self._hash(item, i)
        self.bit_array[index] = 1

def check(self, item):
    for i in range(self.num_hashes):
        index = self._hash(item, i)
        if not self.bit_array[index]:
            return False
    return True Step 2: Write the Test Script import random import string import time from bloom_filter import BloomFilter def generate_random_string(length): return ''.join(random.choice(string.ascii_letters) for _ in range(length)) Parameters num_items = 1000000 num_checks = 10000 bloom_size = 10000000 num_hashes = 7 Create Data Structures bloom_filter = BloomFilter(bloom_size, num_hashes) standard_set = set() Generate Random Items and Add to Both Structures print("Adding items...") bloom_add_time = 0 set_add_time = 0 for _ in range(num_items): item = generate_random_string(10) start_time = time.time() bloom_filter.add(item) bloom_add_time += time.time() - start_time start_time = time.time() standard_set.add(item) set_add_time += time.time() - start_time print(f"Bloom Filter add time: {bloom_add_time/num_items:.6f} seconds") print(f"Standard Set add time: {set_add_time/num_items:.6f} seconds") Perform Membership Checks print( Performing membership checks...") bloom_time = 0 set_time = 0 for _ in range(num_checks): item = generate_random_string(10) start = time.time()
bloom_result = bloom_filter.check(item)
bloom_time += time.time() - start

start = time.time()
set_result = item in standard_set
set_time += time.time() - start start = time.time()
bloom_result = bloom_filter.check(item)
bloom_time += time.time() - start

start = time.time()
set_result = item in standard_set
set_time += time.time() - start print(f"Bloom Filter average check time: {bloom_time/num_checks:.6f} seconds") print(f"Standard Set average check time: {set_time/num_checks:.6f} seconds") Calculate False Positive Rate false_positives = sum(1 for _ in range(num_checks) if bloom_filter.check(generate_random_string(10))) false_positive_rate = false_positives / num_checks print(f False Positive Rate: {false_positive_rate:.2%}") Memory Usage Comparison import sys bloom_memory = sys.getsizeof(bloom_filter.bit_array) set_memory = sys.getsizeof(standard_set) print(f Bloom Filter memory usage: {bloom_memory/1024:.2f} KB") print(f"Standard Set memory usage: {set_memory/1024:.2f} KB") print(f"Memory saved: {(set_memory - bloom_memory)/1024:.2f} KB") Output Adding items... Bloom Filter add time: 0.000004 seconds Standard Set add time: 0.000000 seconds . Performing membership checks... Bloom Filter average check time: 0.000002 seconds Standard Set average check time: 0.000000 seconds False Positive Rate: 0.84% Bloom Filter memory usage: 1220.78 KB Standard Set memory usage: 32768.21 KB Memory saved: 31547.43 KB. Analysis As you can see, there is a false positive rate of < 1%. The membership checks are also slightly less performant. However, the bloom filter uses just 3% of the space used by the set. In an execution environment where memory is at a premium, Bloom filters provide huge savings in space with a moderate reduction in performance. Conclusion Bloom filters are an efficient data structure for use in memory-starved environments. They have a lot of practical applications and are even used in popular tools like CDNs and database engines. Do you have any interesting use cases in which bloom filters would be helpful? Do let me know in the comments!

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Bloom Filters - Power in Simplicity

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Async Without the Headache: Meet areq, the Drop-In Replacement for Python’s Requests

Probabilistic Data structures: Bloom filter

Bloom Filter Basics in Go

Understanding Bloom Filters: An Efficient Probabilistic Data Structure

The Database Zoo: Bloom Filters, HLLs, and Other Strange Beasts of Big Data

10 Tips for Using Diagrams to Ace The System Design Interview

Async Without the Headache: Meet areq, the Drop-In Replacement for Python’s Requests

Probabilistic Data structures: Bloom filter

Bloom Filter Basics in Go

Understanding Bloom Filters: An Efficient Probabilistic Data Structure

The Database Zoo: Bloom Filters, HLLs, and Other Strange Beasts of Big Data

10 Tips for Using Diagrams to Ace The System Design Interview

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps