Bloom Filter

Bloom filter is a probabilistic data structure which is used to to find whether one particular element is a member of a construct.

• If It gives no as answer it is 100% sure that given value is not the member.

• If It gives yes as answer it may not be the member.

• It provides a quick and easy way to discard unwanted read on the disk.

What Problem does it solve?

Take example of instagram, where you have to keep the record of reels viewed by a person. So, that same reel is not showing again.

Why do we need this, can’t we implement same thing with set?

Yes, we can implement same functionality with set but the problem lies in implementation of the sets.

Set is implemented using balanced binary trees, where along with data node we keep track of left and right pointers.

Think of Data of 4MB we have to store 8MB of metadata regarding pointers.

Implementation:

class BloomFilter {
    constructor(size)
    {
        this.size = size;
        this.bitArray = new Array(size).fill(false);
    }

    static hash(value, size) {
    let hashValue = 5381;
    for (let i = 0; i < value.length; i++) {
      hashValue = (hashValue * 33) + value.charCodeAt(i);
    }
    return Math.abs(hashValue) % size;
  }
    add(value)
    {
        const indexVal = BloomFilter.hash(value,this.size);
        console.log(indexVal);
        this.bitArray[indexVal] = 1;
    }
    contains(value)
    {
        const indexVal = BloomFilter.hash(value,this.size);
        console.log(indexVal);
        return this.bitArray[indexVal];
    }
}

const bloom = new BloomFilter(10);
bloom.add('hii'); 
console.log(bloom.contains('hii'),bloom.contains('hi')); // true false