A Gentle Introduction to Bloom Filter

Bloom Filter

Bloom filters are probabilistic space-efficient data structures. They are very similar to hashtables; they are used exclusively membership existence in a set. However, they have a very powerful property which allows to make trade-off between space and false-positive rate when it comes to membership existence. Since it can make a tradeoff between space and false positive rate, it is called probabilistic data structure.

http://bugra.github.io/work/notes/2016-06-05/a-gentle-introduction-to-bloom-filter/