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)

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

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

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

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