3 ms·

I thought the article had a very nice, succinct and clear explanation of bloom filters and wanted to say thanks to the author reading this thread. A year or tw

by gregw2 6y ago

I thought the article had a very nice, succinct and clear explanation of bloom filters and wanted to say thanks to the author reading this thread. A year or two ago when bloom filters became a recurring popular topic on HN I read a long illustrated medium post on them found via HN out of curiosity to add the concept and tool to my back pocket, and it all seemed complicated and the explanation didn't stick. Your explanation however was quick and made complete sense and I cannot forget it. Appreciate it! Thank you!

rkangel 6y ago
I agree. This article finally resulted in me grokking how the k hash functions actually work together.
ImaCake 6y ago
Yeah the visual really helps with explaining the concept. I read the wiki article on bloom filters first, which was great for understanding the motivation for a bloom filter, but I subtly mis-interpreted how the hash functions were used to set the bit-vector. The visuals in the linked post clarified this really succintly.
tomxor 6y ago
Agree, it almost highlights how bad others descriptions can be sometimes. I mean the article makes it feel like such a simple idea given how many words are spoken about it. I wonder if the key is in quickly grounding the core abstractions with concrete meaning early on, that way your mind quickly has a model of "things" to operate on before attempting to build up the behaviour with more abstract description. Many descriptions stay in the abstract too long without anything to attach it to for the uninitiated... in which case you either persevere and eventually it clicks and all the relationships fall into place - or you give up out of disinterest. I've noticed this when explaining things to others, especially non-technical people, when explaining seemingly very simple things, attempting to describe them in multiple ways and failing, and then realizing they need clarification of the "what", after which explanation is easy - sometimes you are blind to it when you already know "what" and already have the mental model so you jump straight into how and why.
hn_throwaway_99 6y ago
I always thought the explanation of bloom filters was way overcomplicated. They are simply chaining hash tables, without the chain. Chaining hash tables first hash a value to an entry in an array, then walk down the chain at that entry to see if the value is actually there and disambiguate when different values hash to the same array entry. Bloom filters just get rid of that second step and leave it up to you to determine if the thing you are looking for is "really" there. Of course, that assumes familiarity with chaining hash tables, but I feel like every CS program goes over hash table implementations, but bloom filters weren't something I learned about until I left college.

by gregw2 6y ago

rkangel 6y ago

I agree. This article finally resulted in me grokking how the k hash functions actually work together.

ImaCake 6y ago

Yeah the visual really helps with explaining the concept. I read the wiki article on bloom filters first, which was great for understanding the motivation for a bloom filter, but I subtly mis-interpreted how the hash functions were used to set the bit-vector. The visuals in the linked post clarified this really succintly.

tomxor 6y ago

Agree, it almost highlights how bad others descriptions can be sometimes. I mean the article makes it feel like such a simple idea given how many words are spoken about it. I wonder if the key is in quickly grounding the core abstractions with concrete meaning early on, that way your mind quickly has a model of "things" to operate on before attempting to build up the behaviour with more abstract description. Many descriptions stay in the abstract too long without anything to attach it to for the uninitiated... in which case you either persevere and eventually it clicks and all the relationships fall into place - or you give up out of disinterest. I've noticed this when explaining things to others, especially non-technical people, when explaining seemingly very simple things, attempting to describe them in multiple ways and failing, and then realizing they need clarification of the "what", after which explanation is easy - sometimes you are blind to it when you already know "what" and already have the mental model so you jump straight into how and why.

hn_throwaway_99 6y ago

I always thought the explanation of bloom filters was way overcomplicated. They are simply chaining hash tables, without the chain. Chaining hash tables first hash a value to an entry in an array, then walk down the chain at that entry to see if the value is actually there and disambiguate when different values hash to the same array entry. Bloom filters just get rid of that second step and leave it up to you to determine if the thing you are looking for is "really" there. Of course, that assumes familiarity with chaining hash tables, but I feel like every CS program goes over hash table implementations, but bloom filters weren't something I learned about until I left college.