Bloom Filter

A Bloom Filter is a space-efficient probabilistic data structure used to check whether an element is part of a set. It is mainly used when we need fast membership testing with very little memory.

Bloom filters give answers in constant time and use constant space, but the result is not always exact. It can sometimes say that an item is present even if it is not (false positive), but it will never say that an existing item is absent (no false negatives).

The main characteristics of a Bloom Filter are:

• Very fast membership checks

• Uses very small memory

• Allows only insert and query operations

• Does not support deletion of elements

• Can give approximate results (false positives are possible)

Steps to Add an Item to a Bloom Filter

1. 

   Take the item that needs to be added.

2. Pass the item through k different hash functions.

3. Each hash function gives a position in the bit array.

4. Apply modulo operation with array size to fit the result in the range.

5. Set the bits at all the resulting positions to 1.

After this process, the item is considered added to the Bloom Filter.

Steps to Check Membership of an Item

1. 

   Take the item to be checked.

2. Pass it through the same k hash functions used during insertion.

3. Find the corresponding positions in the bit array.

4. Check the bits at all those positions:

   • If any bit is 0, the item is definitely not present.

   • If all bits are 1, the item might be present (possible false positive).

Bloom Filters are useful when we need fast and memory-efficient lookups. They do not store the actual data, only hashed positions. False positives are possible, but false negatives are not. More hash functions → fewer false positives, but slower operations. Larger bit array → fewer false positives, but more memory usage.

*image credits: systemdesign.one