This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Bloom Filter Solution" Lesson
[00:00:00]
>> Brian Holt: So the first thing we're gonna need is some sort of internal data structure to keep track of this. I chose season array because that's a good way to model it. Something else that kind of just bares mentioning before we move on as well, is I'm teaching you the general principles here, and I'm teaching you in the simplest way hopefully that you can understand it.
[00:00:23] And I'm not teaching you the most efficient ways of doing things right? So if you were actually going to implement these in production for your code base, you'd probably go find more optimized versions of these than I'm giving you the training wheels version, not necessarily the motorcycle version okay?
[00:00:38] So with that being said, once you understand these, going to the optimized versions will be the next step. It'll be something that you'll be prepared to do. Okay, so, this is a ES6 class, right? They're new as of 2015 for JavaScripts. You could put in here a constructor, which I would imagine many people probably did, which is a totally acceptable way of doing it.
[00:01:05] I am lazy, so I don't want to do that. So I'm going to use what's called class properties, which are new to java script as well, which I can just do like this, new array
>> Brian Holt: 100 and fill it with zeros. So this is going to be creating something on the instance of this particular BloomFilter.
[00:01:29] That's going to be _array which just means, to me means private, right? Underscore doesn't mean anything particular. It's just a convention in JavaScript that if something is private to your array, that you just put an underscore in front of it. There's a new spec coming out where you could put #, where it would actually be private.
[00:01:50] I don't believe that works yet, so just know that's coming. Anyway, _array okay, so now I have an array that's 100 long and filled with 0s, cool? Cool, okay, then we're going to add an add function. It's going to take in some sort of string.
>> Brian Holt: Let's move that up a little bit.
[00:02:16] And this particular thing is just going to go through each one of this._array[h1(string)] = 1. And we're just gonna do that a couple of times but with h2 and h3.
>> Brian Holt: And that's it, we might return true or something there. I don't know, whatever you feel like doing, I don't care.
[00:02:41] So [LAUGH] not the point. Okay, and then we're gonna have a contains function.
>> Brian Holt: That's going to take in a string.
>> Brian Holt: Take in a string, and it's just going to return to you is it in the same spot in h1, h2, and h3 for the same string, right?
[00:03:05] So, the way I chose to do this, which it's up to you how you choose to do that, double exclamation point. Right? Which is going to basically coerce. And if you want to find out more about coercion, watch Kyle Simpson's stuff, cuz he knows all about it. Anyway, weird stuff.
[00:03:22] Suffice to say, if something is truthy, it will make it true. If something is falsey, it will make it false. And then I'm just gonna check this array [h1(string)]. I'm just gonna copy and paste that cuz that's just a whole lot of characters.
>> Brian Holt: And,
>> Brian Holt: I will put two here and h3 there.
[00:03:53] Right so I'm asking is it one at the h1 spot, the h2 spot and the h3 spot. Yeah. Cool. That's what that double and is. Something that always bothers people when I'm using this particular font, this font is called fear of code, and it has ligatures, right. So these double ands kind of mushed together, same with these exclamation points.
[00:04:23] The most obvious one, if I put, that looks like an arrow, right? But, in reality it's an equal space and an angle bracket put together. Congelateurs there are bunch of folks that use them. It makes my code more readable and I've gotten so used to it that I can't separate myself from it.
[00:04:45] Deal with it, I suppose. Cool. So, I guess we can run this and see if it works.
>> Brian Holt: Maybe, and we passed. Any questions? Or I suppose, what questions do you have?
>> Brian Holt: No, I nailed it, cool. Perfectly explained. Okay,
>> Brian Holt: So that's bloom filters. Hopefully you kind of see why this data structure could be potentially useful for you.
[00:05:27] This was invented, I believe it's like the 70s, right? Just like everything that I'm talking about today, not invented any time recently. What is cool though is this is pretty simple. It's not, I would judge that it wasn't terribly difficult for me to learn, which I think is really cool.
[00:05:49] There are now more efficient ways of doing something similar to this. There are bloom filters that you can like remove things from and that are more efficient. There's many flavors of this, this just happens to be one of the more simpler ones. But there are similar data structures that accomplish similar things in more efficient ways.
[00:06:08] If that's something you find yourself in your projects trying to implement do some research. That's all I'm trying to say. Cool, and again, the completed code is always down here if you get stuck, if you want to see how I personally did it. That's why I have the second laptop up here, so I don't forget how I did it.
[00:06:30] [LAUGH] So please, again, this is not a test, this is not cheating, this is just learning. So just make sure you're doing whatever you need to do to learn the best.
>> Brian Holt: But you will fail the course, I'm just telling you that there. [LAUGH] Yeah.
>> Speaker 2: Where is defined h1, h2 used in array.
[00:06:57]
>> Brian Holt: Where is h1 defined? Is that the question?
>> Speaker 2: I believe so.
>> Brian Holt: Okay. Well. Let's talk about h1. So, we have this thing here call, this is the hashing function that I wrote to just be. Something really quick. If you go in here to, settings. Okay so this is the settings for this particular code pin.
[00:07:26] Here in the JavaScript I got a bunch of stuff I'm including. One of them is this XXhash.nin.js this is just a library off of NPM. You can NPM install XX-JS and this will install this function. It's just a fast hashing function that I did not have to write, right?
[00:07:47] That's all it is. So that's where this gets defined. They're just seed values, so that the randomness is more spread out and different. And then this is just a bunch of stuff to make it work, so trial and error, that's how I figured it out. [LAUGH] That's a good question, though.
[00:08:09] Also if you look there, you can see,
>> Brian Holt: Yeah, this is all the stuff that's being loaded for the Jasmine. Same thing with the CSS, it's been loaded for the Jasmine as well. So that's where all of that came from.
>> Brian Holt: Since we're on the wavelength of codepen things just so you know, you can always look at ViewCompileJS if you actually want to see what the battle is compiling it to.
[00:08:39] Sometimes it's helpful, usually not but it's there if you want to take a look. And then I'm obsessive about using prettier on everything. If you've watched my other courses you're aware of that. If you click Tidy JS, it will tidy everything up for you, using prettier, right? This became a lot more readable than my crazy stuff that I had before.
[00:09:02] So, just be aware that Tidy JS is up there. It's really useful. I would suggest it.
>> Brian Holt: Okay, good question.