Bloom Filters By Example

Bloom Filters by Example. I’ve heard of Bloom Filters a bunch of times but never took the time to understand how it works. For some reason I thought it would be hard, so I never really tried. Decided to read this article today and it turned out to be a pretty simple data structure. A Bloom Filter is a Bit Vector, let’s use a bit vector of size 16 as an example:

Indexes:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
Bits:     [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]

We add items to our set by applying n hash functions and using the results to set the bits of the bit vector.

For example, suppose we have a hash function h1. If we hash “apple” with h1, we might get a large number like:

h1("apple") = 74329

But our bit array only has 16 positions. So we reduce it to a valid index with:

index = 74329 % 16 = 9

This means: Set bit at index 9 to 1.

Indexes:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
Bits:     [ ][ ][ ][ ][ ][ ][ ][ ][ ][✖][ ][ ][ ][ ][ ][ ]

So, if we use 3 hashes in our Bloom Filter implementation, we may end up with the following configuration:

Indexes:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
Bits:     [ ][✖][✖][ ][ ][ ][ ][ ][ ][✖][ ][ ][ ][ ][ ][ ]

To check if an item is in the set, hash it with the same functions and see if all the resulting bit positions are set to 1 in the array. If they aren’t you know for sure, the item is not in the set.

#bloom-filter