Bloom Filters by Example | Hacker News Reader

Bloom Filters by Example

llimllib.github.io

247 pointsibobev37 comments

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 :)

Same with me

Learned about them when I was told to implement one for iBooks (for search) — over a decade ago.

They're really fun. I get so excited when a problem presents itself that requires a bloom filter (which can be rare depending on the domain unfortunately).

same!

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.

Could have also bought Bitcoin and made a lot more... just saying.

Improbable considering it was a CS idea in 1970. Surely every idea for GPGPU was fair game.

I wrote a hashcash implementation on a GPU 10 years ago. Pretty sure it's valueless now.

I think their implication is not that they weote a $100M one off but instead that if they had stayed in GPU programming they could now be making the proverbial big bucks in the current ai boom

I ported a machine learning algorithm to CUDA for my honours project, shrugged my shoulders and went into embedded programming

Same here.

I'm quite sure I wrote one of the first GPU optimized bioinformatics toolkits ... out of curiosity, on a GeForce 8, using CUDA v1(!) back in 2009.

Then went on to do other things ... missed the big bux.

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".

"bloom" and "demonstrators " (mind the trailing space character)

Both collide with: fnv: 7 murmur: 12

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.

Chromium does this in a bunch of places; the article only links to Safe Browsing using murmur, but the renderer (Blink) generally uses rapidhash and has some of these micro-filters which it uses for e.g.:

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

It's surprising that such tiny filters (32 or 64 bits) work at all, but they often do. There are also some larger Bloom filters around.

(I added some of these)

They just have a really unintuitive economy where they basically only need to work once or twice to make up for the cost of all the times they don't contribute any benefit.

For extra fun, you sometimes can make ideal filters with no false positives, if you know your possible elements ahead of time and you don't insert too many of them. (E.g., for 20 elements, you can construct a 12-bit code where there are guaranteed no false positives as long as you insert at most two elements.)

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

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

I thought I had seen this before, but actually it was this other page: https://bdupras.github.io/filter-tutorial/

This one compares bloom and coockoo filters, so it adds a little more information.

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.

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.

If you've grokked bloom filters, you're very close to also understanding both random projection and certain implementations of locality-sensitive hashes.

Glad to know I'm not alone in my mental modeling of Bloom filters as just hash tables that only track the buckets which have data but not the actual data itself.

I think the main bit your explanation is missing is how a bloom filter uses multiple hash functions to reduce collisions. For example, a bloom filter might have 3 hashes, and all of them have to hit for a key to be known to be in the set. This reduces the likelihood of false positive collisions while keeping the no false negatives guarantee.

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 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.

What about distributed hash table architectures in general? circle, chord, CAN and kademlia, etc.

There's only so many things you can put on your "I must tell everyone I meet about this" list. :)

But yes, those are pretty important too.

https://hur.st/bloomfilter/

There is a only bloom filter calculator that lets you just mess arpund with parameters

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.

You're saying you can use a perfect hash also implies you know you will only find those values? If so, then yes, the name is accurate and is probably a very good choice.

But if you put things into the perfect hash function it is not expecting, some fraction of them will collide.

If you're searching for a fixed set, look at the Ragel library. Compile-time generation of the search in a way that is very hard to beat.

> You're saying you can use a perfect hash also implies you know you will only find those values?

No, 99.999999% of the time the values is NOT what I am looking for. So the error rate is EXTREMELY high, so its very important that the failure path is quick.

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

I was very confused by

> 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.

You could also stack bloom filters to make hashing like querying a tree.

Reply on news.ycombinator.com