Bloom Practice

[00:00:00]
>> So we're gonna come over here to our exercises, and we're gonna go to Bloom Filters. Okay, and let's take a look at this. So first of all I have three hashing functions here for you that I have already built for you. You don't have to do anything about them, you don't have to understand how they work.

[00:00:23]
They use a library called xxhashjs, which is just a really fast hashing algorithm. They'll take a string and turn it into a number, and then I turned that number into a number between 0 and 199, right? So that you can use a bloom filter of size 100. So the first thing I'll say here for your bloom filter, in fact, this just kind of set this up for you so you can get rolling right away.

[00:00:50]
Bloom filters solutions. So I would just put a constructor up here. And then I would just say like this._array = new Array(100).fill(0). So this will give you an array on this ._array that is just filled with 0s, right? And then you'll just be flipping those to 1 just like how I showed you.

[00:01:24]
So all you need to do is do an add here and a contains here, and we'll go from there, cool. This is actually a fairly straight forward one, I think I only end up writing ten lines of code to get all this all done. So, yeah, cool. Let's build a bloom filter.

[00:01:48]
So, the first thing we already built here was this array = new Array(100).fill(0). We have an array of 100 things filled with 0s, right? So, to do an add really all we're going to do is this._array. And then we're gonna put our three hashing functions here, string = 1, right?

[00:02:15]
And actually we're just gonna do that three times for all of our three hashing functions. That's it, that's all I gotta do to add something. So one big key thing that you know about Bloom filters, we can't delete anything, right? Because how do you know what to delete and what has previously used and what hasn't, right?

[00:02:38]
There's no additional information here. So that's another kind of downfall of Bloom filters is that they cannot delete from a Bloom filter, Okay? Then here with the contains, all you're gonna do is return and I'm gonna show you a little trick here. If you put a double exclamation point this is gonna coalesce it into a Boolean, right?

[00:03:03]
So this is gonna take whatever this comes back as a true or false. And I'll say this._array, each one string and then I want to do this like this h2. Sorry, this one right here is gonna be h2 and this one right here is gonna be h3, just like that.

[00:03:40]
So, yeah, let's talk about this is a little bit clever, but let's just walk through it. Each one, so this is gonna be either a 0 or a 1, this is gonna be a 0 or a 1, and this is gonna be a 0 or a 1, right?

[00:03:57]
0s, if you do this, I'll just ignore that's not helpful. Make a little bit bigger down here. If you look here in the bottom, right, if I do, 0 == false, that's true, right, same with true == 1. So these things if you're willing to do, what's the word I'm looking for?

[00:04:29]
That's just escaping me, the term there, anyway. If you're willing to convert it from a number to a Boolean, then you can do it this way with a double equal sign. So if I put !!0 that actually comes back as false, right? And if I put !!1 that comes back as true.

[00:04:56]
So if I do !!0(&&0 &&0), that's false, but if any one of these is true, this comes back as or actually, Right? So only if they all come back as 1 is it true. So now, we should be able to run our test here. Let's reset my Zoom here play.

[00:05:35]
And if you go look at Bloom filters we got to not skip this, And click Play. And did that work? No. How these are all skipped, let's do this. Okay, one more time, let's try it, Bloom filters, there we go. And let's click on that, you can see that it's returning false and empty, handles one item, handles many items, all that works super well.

[00:06:26]
Okay, so you could have done this in a much less clever way and just said like if this._array h1 === 1 and the h2 and h3, all that kind of stuff. And that would have probably been more clear, but this seemed kind of terse and nice so I went well with that.

[00:06:48]
That's it, that's all Bloom filters. Anyone have any questions about Bloom filters?
>> Yeah, I got a question about implementation. Because it's JavaScript, right? Like no matter what our hash function is gonna return, it's still gonna put it there. The fact that we create an array of size 100 doesn't matter, right, like, technically.

[00:07:11]
If it doesn't return the number if it's gonna return the string, Is just gonna go there and create a property.
>> Yeah, that's true. Okay.
>> I think, I mean, not good programming, but let's just triple check, make sure that correct. If I say x = empty array, and I say x(100) = 1, and then I asked for x(100) gives me 1 back, yeah?

[00:07:40]
So, you're absolutely correct.
>> Okay, good.
>> So, but here we created a number, an array of 100. So I guess what you're saying is, JavaScript will dynamically allocate that for you no matter what. So you could have just said new Array and you can treat undefined as 0.

[00:08:04]
Yeah, that would work with JavaScript. I don't know if I suggested it, do I suggest it? I don't know if it matters, honestly, I don't know. [LAUGH] It's good to have defined boundaries to your problem.
>> Yeah, just my problem is like, it's kind of an illusion if our hash function is not just numeric, right, it's still gonna work.

[00:08:25]
Like we're not gonna know,
>> Yep. Yeah, yeah. And the only reason that does work is cuz we have these modules right here for our hashing functions that guarantees that it stays between 0 and 99.