Bloom Blog

bloom.py

class Bloom:
    def __init__(self, m, k):
        self.info = np.zeros(m, dtype='bool')
        self.k = k

    def insert(self, x):
        f = double_hash(x, self.k, self.info.shape[0])
        self.info[f] = True

    def is_in(self, x):
        f = double_hash(x, self.k, self.info.shape[0])
        return np.all(self.info[f])

    def __str__(self):
        return f'Bloom(info={self.info}, k={self.k})'

double_hash.py

def double_hash(delta, k, m):
    x = hash1(delta) % m
    y = hash2(delta) % m
    f = np.zeros(k, 'int')
    f[0] = 0

    for i in range(1, k):
        x = (x + y) % m
        y = (y + i) % m
        f[i] = x

    return f

triple_hash.py

def triple_hash(delta, k, m):
    x = hash1(delta)
    y = hash2(delta)
    z = hash3(delta)

    f = np.zeros(k, 'int')
    f[0] = 0
    
    for i in range(1, k):
        x = (x + y) % m
        y = (y + z) % m
        f[i] = x

    return f