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.
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 :)
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 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.
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 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.
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.
I love me a good bloom filter. Bloom filters are one of the concepts I try to make sure everyone I talk to about tech knows -- the others being Random Weight Hashing (aka Rendezvous Hashing, aka Highest Random Weight Hashing) and Cumulative flow diagrams.
All three concepts are key in understanding operations of complex distributed systems.
Note to the author -- I love the interactive part. One suggestion to really drive the point home: Give the user an example of two strings that have a hash collision, and tell them to enter one into the box, and then test for the other in the second box.
It will demonstrate why the answer is always "maybe it's in the set!" instead of "yes".
> When you add a string, you can see that the bits at the index given by the hashes are set to 1. I've used the color green to show the newly added ones
because all I saw was the content text of "Your set:" changing, no bits, no colors. It took me trying a different browser and then scrolling up and down to realize that it's the visualization two paragraphs above that was changing.
just asked chatgpt to write one in python, and used md5 digest slicing, what might be a common approach to simulate several hashes just from the base md5 digest. I guess fine for not critical use cases
19 comments
[ 3.3 ms ] story [ 46.4 ms ] threadFor 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.
It appears that perfect hash is the one that works the best for my use case.
I probably could have made $100,000,000 if I had made a different choice there.
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.
All three concepts are key in understanding operations of complex distributed systems.
It will demonstrate why the answer is always "maybe it's in the set!" instead of "yes".
> When you add a string, you can see that the bits at the index given by the hashes are set to 1. I've used the color green to show the newly added ones
because all I saw was the content text of "Your set:" changing, no bits, no colors. It took me trying a different browser and then scrolling up and down to realize that it's the visualization two paragraphs above that was changing.
There is a only bloom filter calculator that lets you just mess arpund with parameters
This one compares bloom and coockoo filters, so it adds a little more information.