# Bloom Filters ### Raison d'être > **Problem**: Does an element exist in a given set? This is the **membership problem**. > **Solution**: We can insert elements into the bloom filter and the data structure is responsible for remembering what's been inserted. ### Diagram  ### Main Ideas * The Bloom Filter is a data structure that compactly represents a set as a bitmap which is updated via hashing. * We will never have a false negative. We may have a false positive. * Used when we aren't worried about a false negative, and want low memory footprint and high speed. Very light weight data structure. This is great for looking to see if a user exists on a website. * We will want error probability to be small! ### Guarantees 1. A Bloom filter will never have a false negative. If an item is in the set, it will always correctly identify that it is. 2. It may have a false positive. ### Background Hash tables also offer a good solution to the membership problem, so why bother with a bloom filter? The primary motivation is to save space — a bloom filter compresses the stored set more than a hash table. In fact, the compression is so extreme that a bloom filter cannot possibly answer all membership queries correctly. That’s right, it’s a data structure that makes errors. Its errors are “one-sided,” with no false negatives (so if you inserted an element, the bloom filter will always confirm it) but with some false positives (so there are “phantom elements” that the data structure claims are present, even though they were never inserted). For instance, using 8 bits per stored element — well less than the space required for a pointer, for example — bloom filters can achieve a false positive probability less than 2%. More generally, bloom filters offer a smooth trade-off between the space used and the false positive probability. Both the insertion and lookup operations are super-fast (O(1) time) in a bloom filter, and what little work there is can also be parallelized easily.  --- References: * [Stanford - Bloom Filters The Basics](https://www.youtube.com/watch?v=zYlxP7F3Z3c) * [Stanford - Bloom Filters Heuristic Analysis](https://www.youtube.com/watch?v=oT-Zhry0hBI) * [Bloom Filters Explained by example](https://www.youtube.com/watch?v=gBygn3cVP80) * [Sketching data structures](http://lkozma.net/blog/sketching-data-structures/)