Introduction to Bloom Filters

Table of Contents Introduction to Bloom Filters Operation on the Bloom Filter Example Advantages of a Bloom Filter Over a Set Data Structure Choosing a Hash Function Tuning a Bloom Filter Example Use Cases Introduction to Bloom Filters Bloom filter is a probabilistic data structure used to solve the set membership problem. A relaxed constraint here is that false positives are tolerated to an acceptable level. Bloom filter uses a bit array to store the presence of items. Bloom filter uses hash functions to save the presence of an item without saving the actual item. Bloom filters can give false positives, but never false negatives. This means that if the bloom filter returns positive, it means that the element may be present in the set, but if it returns negative, it means that the element is definitely not present in the set. Now let us define a few variables before jumping into the algorithm: n - The number of elements to be added in to the set. k - The number of hash functions we use