bloom_filter.py

"""Bloom: Studio album by Troye Sivan."""

import pyhash


def calculate_hash(value, m):
    # FNV
    hash1 = pyhash.fnv1_32()(value) % m
    # MurMur
    hash2 = pyhash.murmur1_32()(value) % m
    return hash1, hash2


class BloomFilter(object):
    """Basic BloomFilter."""

    def __init__(self, m):
        super(BloomFilter, self).__init__()
        self.m = m
        self.bitmap = 16 * [0]

    def add_element(self, value):
        for _hash in calculate_hash(value, self.m):
            self.bitmap[_hash] = 1

    def __contains__(self, value):
        for _hash in calculate_hash(value, self.m):
            if not self.bitmap[_hash]:
                return False
        return True

superheros = [
    "Shaktimaan",
    "Doga",
    "Nagraj",
    "Devi",
    "Krrish",
    "Parmanu",
    "Chotta Bheem"
]


bf = BloomFilter(m=16)
for hero in superheros:
    bf.add_element(hero)

print(bf.__contains__("Devi"))
print(bf.__contains__("Hulk"))