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

Sentry blog image

How to reduce TTFB

In the past few years in the web dev world, we’ve seen a significant push towards rendering our websites on the server. Doing so is better for SEO and performs better on low-powered devices, but one thing we had to sacrifice is TTFB.

In this article, we’ll see how we can identify what makes our TTFB high so we can fix it.

Read more

Top comments (0)

The best way to debug slow web pages cover image

The best way to debug slow web pages

Tools like Page Speed Insights and Google Lighthouse are great for providing advice for front end performance issues. But what these tools can’t do, is evaluate performance across your entire stack of distributed services and applications.

Watch video