# What’s a Bloom filter

A bloom filter is a data-structure that can be used to check if a set contains an element. It uses way less memory than a conventional set data-structure by sacrificing accuracy.

## Example

Say we are building a log-structured merge-tree, we can use a bloom filter to find out if the LSM-tree contains a particular key in O(1) time in most cases, the downside is that sometimes the bloom filter would say that the LSM-tree contains a key, but it actually does not and we would go searching for the value that’s mapped to the key and never actually find it.

It is used in a lot of places.

# How it works

A bloom filter is just a bit-set that uses `n`

deterministic hash functions to add elements to it.

*empty bit-set*

## Adding elements to the set

To add the key `bob`

to the set, we run the key through each of the `n`

hash functions and map the hash function output to one of the positions in the bit-set and for each position, we flip the bit to `1`

.

*bit-set after bob was added to the bloom filter*

## Finding out if the set contains an element

To find out if the set contains the key `bob`

, we run the key through each of the `n`

hash functions again – since the hash functions must be deterministic they will **always** map to the same position in the bit-set – and check if the bit is set to `1`

for each of the bit-set positions we reached after running the key through the hash functions. If every hash function maps to a bit set to `1`

, it means the key is in the set.

*bob is in the set because every hash function mapped it to a bit set to 1*

*alice is not in the set because not every hash function mapped to a bit set to 1*

## False positives

Since collisions can happen some keys will be mapped to bits that were set to `1`

when other keys were added to the set. In this case, the bloom filter will say that it contains the key even though it does not.

*the bit-set after bob was added to it*

*since john maps to the same bits as bob and the bits were set to 1 after bob was added to the set, we got a false positive*

## Removing an element from the set

As it stands, removing an element from the set is not actually possible. If we had a bloom filter that uses 3 hash functions that looks like this after adding `alice`

and `bob`

to it:

*bloom filter after adding alice and bob to it with 3 hash functions*

Note that `alice`

and `bob`

hash to the same position in the bit-set for some of the hash functions

*bits shared between alice and bob are in white*

The naive solution is to remove `alice`

from the bloom filter by setting the bits mapped by hash_{i}(alice) to `0`

:

*bits that were flipped to 0 are in white*

Now, let’s check if `alice`

is in the set, for a key to be in the set hash_{i}(key) must map to bits set to `1`

*hash _{i}(alice) maps to bits set to 0 which means alice is not in the set*

`alice`

is not in the set as expected. Let’s see if `bob`

is still in the set, it should be since we didn’t remove it.

*not every hash _{i}(bob) maps to bits set to 1 which means bob is not in the set, bits set to 0 after removing alice from the set are in white*

`bob`

is not in the set anymore, even though we didn’t remove it. The problem is that since keys may share the positions in the bit-set, we cannot just flip bits back to `0`

to remove a key from the set because in doing so we may flip bits that are used by other keys.

## Counting bloom filter

Since we cannot flip bits back to `0`

to remove a key from the set, we could maintain a counter instead of a single bit. When a key is added to the set, the counter is incremented and when a key is removed from the set, the counter is decremented. If the counter reaches 0, it means no keys are mapped to the position.

Positions that have more than one key mapped to it will have a counter greater than `1`

.

*positions in white are shared between two or more keys and have a counter greater than 1*

*removing alice from the set by decrementing the counters mapped by hash _{i}(alice)*

After decrementing the counters, not every hash_{i}(alice) maps to a counter greater than `0`

which means `alice`

is not in the set anymore. Unlike the bloom filter that uses only bits, hash_{i}(bob) still maps to counters that are greater than `0`

which means `bob`

is still in the set.

## Example in Rust

https://github.com/PoorlyDefinedBehaviour/bloom_filter/

# References

Network Applications of Bloom Filters: A Survey - https://www.eecs.harvard.edu/~michaelm/postscripts/im2005b.pdf

Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems - Martin Kleppmann