Refreshing some computer science concepts by taking Brian Holt’s course on The first part lesson was on Bloom Filter’s, which sounded complicated and scary. The concept ended up being easy to grasp and he presents a great example of a practical application. The devil is obviously in the details but knowing a tool exists and the reasons to use it is always a step in the right direction.

A bloom filter answers the question, “Have I seen this before?” with “No.” or “Well, maybe.” in a fast and memory efficient way, the tradeoff being uncertainty in the answer.

The basic implementation done through the course goes like…

where h1, h2, and h2 are hashing functions.

So when asking the question “Have I seen this before?”, we’re calling ‘contains’. If the indices that a string hashes to are ‘on’, then our answer is “Well, maybe.”

A deeper dive is in order in the near future!