Bloom Filters: Probably Yes, Definitely No

[00:00:00]Imagine a structure that, when you ask whether something is in it, can give you two kinds of answers. One is probably yes, and sometimes that answer is a lie.

[00:00:11]The other is definitely no, and that one is never a lie. The no is always the truth. The yes might be wrong. What kind of structure answers the world like this? It's called a Bloom filter.

[00:00:27]At its heart, it's just a row of bits, all zero to start with. To insert a key, you hash it to one of those bit positions, and flip that bit on. Another key, another bit.

[00:00:39]But here's the catch. Two different keys can land in the same slot. Apple hashes to position three. Cherry hashes to position three. Now, we have no way to tell them apart. With a single hash, the collisions overwhelm us.

[00:00:55]So, we use K hashes instead of one.

[00:00:58]Every key arrives, gets hashed K different ways, and we set every one of those bits to one. Apple sets three bits, banana sets three more, cherry sets three, and some of them overlap with what's already there. That's fine.

[00:01:14]The bit array is the filter. The keys themselves, we can throw away.

[00:01:20]Now, for the trick.

[00:01:22]To check if grape is in the set, we hash grape with the same K functions, and look at those bits.

[00:01:28]If any one of them is zero, grape was never inserted, because inserting it would have set that bit. A zero is proof. That's the definitely no.

[00:01:38]But if every bit is one, the answer is only probably yes.

[00:01:43]Those ones could have come from other keys.

[00:01:46]Kiwi was never inserted, yet its three bits might all happen to land on bits set by apple and banana.

[00:01:54]The filter is lying.

[00:01:57]So, how often does it lie? The false positive probability is roughly 1 - e to the - kn over m all raised to the k. n is the number of items inserted, m is the number of bits in the array, and k is the number of hashes. The error bottoms out when k star equals m over n times the natural log of 2. 10 bits per item, seven hashes, and the filter lies less than 1% of the time.

[00:02:28]So, that's the whole idea. A bit array, a handful of hashes, and an answer that can be wrong in one direction, but never the other. Definitely no, because a zero bit can't lie. Probably yes, because the ones might come from anywhere. You trade exactness for bits, and it's why Bloom filters quietly sit inside databases, caches, routers, and blockchains.

[00:02:53]Anywhere a fast maybe here, takeaway, check saves you from doing an expensive lookup. And that's basically it. If you found this helpful, hit that like button, subscribe for more, and drop a comment if you have any questions. See you in the next one.

[00:03:11]Bye-bye.