Bloom Filter – Inchkeith Consulting Ltd

A Bloom filter is a probabilistic data structure that is used to test whether an element is a member of a set. It uses a bit array of a fixed size and a set of hash functions to store and retrieve elements efficiently. The basic idea of a Bloom filter is to encode each element of the set by setting the bits at the positions determined by the hash functions. To check if an element is a member of the set, the hash functions are applied to the element, and the bits at the corresponding positions in the bit array are checked. If all the bits are set, the element is probably in the set (with a small chance of false positives). If any of the bits are not set, the element is definitely not in the set.

One of the key advantages of Bloom filters is that they are space-efficient compared to other data structures for set membership testing, such as hash tables or binary search trees. This is because Bloom filters only store a fixed-size bit array and do not need to store the actual values themselves. However, this comes at the cost of allowing for false positives, meaning that the filter may indicate that an element is in the set when it is not. The probability of false positives can be reduced by increasing the size of the bit array and the number of hash functions used, at the expense of increased memory usage and computational overhead. Bloom filters are commonly used in various applications, such as spell checkers, network routers, and distributed systems, where efficient set membership testing is required, and the occasional false positive is acceptable.

Here is an example of a simple bloom filter implementation in Python using the bitarray library:

import bitarray
import hashlib
class BloomFilter:
    def __init__(self, size, hash_count):
        self.size = size
        self.hash_count = hash_count
        self.bit_array = bitarray.bitarray(size)
        self.bit_array.setall(0)
    def add(self, string):
        for seed in range(self.hash_count):
            result = hashlib.md5((string + str(seed)).encode())
            digest = int(result.hexdigest(), 16) % self.size
            self.bit_array[digest] = True
    def lookup(self, string):
        for seed in range(self.hash_count):
            result = hashlib.md5((string + str(seed)).encode())
            digest = int(result.hexdigest(), 16) % self.size
            if not self.bit_array[digest]:
                return False
        return True

import bitarray

import hashlib

class BloomFilter:

def __init__(self, size, hash_count):

self.size = size

self.hash_count = hash_count

self.bit_array = bitarray.bitarray(size)

self.bit_array.setall(0)

def add(self, string):

for seed in range(self.hash_count):

result = hashlib.md5((string + str(seed)).encode())

digest = int(result.hexdigest(), 16) % self.size

self.bit_array[digest] = True

def lookup(self, string):

for seed in range(self.hash_count):

result = hashlib.md5((string + str(seed)).encode())

digest = int(result.hexdigest(), 16) % self.size

if not self.bit_array[digest]:

return False

return True

Here’s how you can use the bloom filter:

bf = BloomFilter(500000, 7)
words = ['hello', 'world', 'test', 'python', 'programming']
for word in words:
    bf.add(word)
print(bf.lookup('hello')) # True
print(bf.lookup('goodbye')) # False

bf = BloomFilter(500000, 7)

words = ['hello', 'world', 'test', 'python', 'programming']

for word in words:

bf.add(word)

print(bf.lookup('hello')) # True

print(bf.lookup('goodbye')) # False

In this example, the bloom filter is initialized with a size of 500,000 bits and a hash count of 7. The add method hashes the input string multiple times and sets the corresponding bits in the bit array to 1. The lookup method hashes the input string in the same way and checks if all the corresponding bits in the bit array are set to 1. If any of the bits are 0, the method returns False.