Hacker News Reader

Comment by eis | Hacker News Reader

Bloom filters explained in a single HN comment:

They are an efficient implementation of a Set that contains hashes of the elements.

bloomfilter.add("foo") will internally add hash("foo") to the Set

bloomfilter.has("foo") checks if the Set contains hash("foo")

False positives arise due to different elements hashing to the same hash. If "foo" and "bar" hash to the same value, bloomfilter.has("bar") would return true.

No false negatives are possible.

They are used when an actual check for an element in a datastructure is quite costly and the hitrate for not-in-the-datastructure is non-trivial and can therefor be skipped if the bloomfilter gives a negative.

View on HN

Thanks for your comment! (I'm the author of the image/poster). At first, I wanted to give a similar explanation than yours, but then decided to make it more verbose / less technical, and it ended up having more text that I would like to.

Also, your last sentence is a great summary of when they should be used. I included a few use cases, but I should have also included something like what you said.

I'll take that into account for future posts, thanks!

I don't think that's quite right though. A bloom filter does not keep a list of hashes. If it did it'd grow with every item added to the set, and it doesn't. A bloom filter adds a new hash by bitwise-or-ing it with the currently stored value. Checking if a hash is present in the bloom filter is as simple as checking that all the 1 bits in the bash are 1 bits in the stored value in the bloom filter. This makes sure there are never any false negatives because bits only ever get turned on, never off. False positives are possible because of either direct hash collisions, or unrelated hashes turning on enough bits for a match.

So it means with a dataset big enough, your bloom filter is virtualy all 1s, and will return true for every values you want to check regardless if it is actually in there ? Is there a threshold you can monitor to avoid this situation ?

Yes, if a dataset keeps growing, the whole bloom filter will eventually become 1s. If you know the (approximate) expected size of your dataset and the probabilities of false positives you can tolerate, you can calculate how big the filter should be and how many hashing functions you have to use.

I guess there are other techniques to dynamically grow the filter when you need it.

It's indeed not a list of hashes but (as I said) a set of hashes. Usuaully the size of the set is static and determined when creating the bloom filter (how many bits in the bitmap). The hashes are not full blown hashes like a sha1 sum or similar but a bit (or a few) in the bitmap. You only add to the set and never remove. The bitwise or-ing with the stored value is the mentioned hash collision and just an implementation detail. It's still a set of hashes.

"unrelated hashes turning on enough bits for a match" is the case of hash collisions or I am misunderstanding that part.

I think this is a great explanation for using a bloom filter and getting a feel for why you can get false positives but not false negatives.

Super useful and succinct!

This explanation could apply to a few hash-set style implimentations but I think it misses what made the bloom filter so beautiful and elegant when I'd discovered it. It's a specific data structure with it's own memory/performance/tuning profiles!

This was easier to digest than the "image". Thanks.

Reply on news.ycombinator.com