Bloom filters
1 min read

Bloom filters

A Bloom filter is a probabilistic data structure present in many common applications. Its purpose is answering the question: "is this item in the set?" very fast and not using a lot of space. The answers can be NO, or MAYBE YES.

They work using hash functions, we learned about them some time ago.

Image explaining how bloom filters work
Bloom filters explained

For example, one use case of Bloom filters is the following: you have a huge list of malicious URLs. In your browser, before a user navigates to a new URL, you want to check if it's inside the list of dangerous URLs. You can use a bloom filter to do that! It will take less space than saving the full list of URLs, and if the answer from the Bloom filter is "no" (the URL is not a malicious one), you can safely let the user visit it.

If you want to learn how to implement a Bloom filter from scratch, you can do it here. And if you liked this post, feel free to share it and tag me!