Bloom filters are an interesting data structure that can increase performance for certain use cases. They use multiple overlaid hashing functions and can quickly tell you if an item definitely does not exist in a set. However, they can't say with certainty if an item exists, only that it is likely to. They are useful as a pre-filter, so that you can avoid performing a lookup, because you know for sure that the item won't be there.
The following diagram shows how a Bloom filter works. A, B, and C have been hashed and inserted into the filter. D is hashed to check if it is in the filter but, as it maps to a zero bit, we know that it is not in there:
Bloom filters are much smaller than holding all the data or even a list of hashes ...
