Bloom Filters by Example

I recently used a bloom filter to achieve a log message anti-spam feature. In the logger I hashed the messages and inserted into the filter. If the entry was present I didn’t output the messages. Then every few seconds I would iterate over the filter and clear all the bits. It worked out nicely that I didn’t have to worry about atomically clearing all the bits in the filter, if messages were coming in and any of their bits had been cleared that was sufficient to cause them to be logged again. This was much more efficient than the previous implementation which kept a count of messages seen and would saturate at N and had the effect that if a particular message was being repeatedly logged it would be seen, just at most at the rate at which the filter was being cleared.

After being aware of bloom filters for a while it was quite satisfying to organically find a real use for one that was such an improvement.

This article is aimed squarely at people like me. I'd heard of them. I kept meaning to look them up everytime I saw them mentioned. I finally did when I saw your articale and it was the perfect intro that I was looking for :)

I wrote a Bloom Filter for college in CUDA in 2009. My advisor was a former Nvidia guy. I then went on to not do any GPU programming at all in my career.

I probably could have made $100,000,000 if I had made a different choice there.

It's always great to see interactive posts. I also appreciated the list of where Bloom filters were used in popular programs.

Another visualisation of Bloom filters can be found at the end of this page: https://www.chrislaux.com/hashtable.html

I have a trick I like:

For sets that are plausibly sometimes going to be small where you're going to do a lot of membership checks, you can speculatively add a 64 bit bloom filter with a trivial hash function.

This sounds really stupid, but the cost of doing this is so small you can do it as a gamble. If it doesn't work out you've added like 10ns to your insertions and membership checks, but when it does work out, you can save an incredible amount of work.

  - querySelector() in certain cases
  - Prefiltering hash lookups in CSS buckets
  - Rapid reject of elements when looking for certain Aria attributes (for accessibility)

Another one bloom filter post I really appreciated from Eli Bendersky if anyone wants to read more: https://eli.thegreenplace.net/2025/bloom-filters/

The overlap in concepts required to understand Bloom filters, sets and hash tables is about 95% IMHO. A set is a hash table used for membership tests where you only care about the key, not the value. And a Bloom filter is just a set that exploits the fact that many-to-one hashing 'compresses' the key-space with collisions. It deliberately uses a very collide-y hash function. If a specific key was ever hashed, you WILL get a hit, but there might be other keys that produced the same hash. It's a feature, not a bug.

I had used bloom filters in the past without really understanding how they worked. Then one day I decided to implement them just going off the Wikipedia article with the 32-bit MurmurHash function and was surprised at how simple it was. If you're using C++ you can use std::vector<bool> (or as of C++23, std::bitset) to make it even easier to store the bits in a space efficient way.

i got into bloom filters while debugging cassandra read spikes ,lot of sstable lookups even when key not exist ,didnt make sense at first ,then realised bloom filter on each sstable meant to skip disk ,but default fp rate was high like 0.1 or so ,too much for our case ,most reads were cache miss anyway so those false positives were killing us ,changed it to 0.01 ,bit more memory it consumed but way less useless reads ,lbrought p99 read latency by good 16-18%

I have a specific use case where I know from startup the list of words that I want to find and this will not change for the duration of the program. Can anyone think of a low latency solution to this? I have tried a lot of variations of bloom filter, perfect hash, linear lookup, binary search, set search etc

It appears that perfect hash is the one that works the best for my use case.