DEV Community

PrinceKumar799
PrinceKumar799

Posted on

1

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.

Image description

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
Enter fullscreen mode Exit fullscreen mode

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay