Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Key Components of a Hash Table" Lesson is part of the full, Data Structures and Algorithms in JavaScript course featured in this preview video. Here's what you'd learn in this lesson:

The key components of a hash table include a storage object as well as a hashing function. A hash table should also be able to get, set, and remove properties from the storage object. Bianca uses these key components to demonstrate how a hash table accesses objects in memory.

Get Unlimited Access Now

Transcript from the "Key Components of a Hash Table" Lesson

[00:00:00]
>> Bianca Gandolfo: So we're going to just think about the key components of our hash table. We're massaging this into our brain. So we have the storage, right? And when we implement our hash table, we cannot use a object as storage cuz that's cheating, just like we couldn't use an array for our QR stack when our first implementation.

[00:00:23] So we're gonna use something to store it, but it's not gonna be an object. What do you think it might be?
>> Speaker 2: So it's not gonna be an object?
>> Bianca Gandolfo: Yeah, our store. We have to store it somewhere. It's not gonna be an object. What's our other option?

[00:00:41]
>> Speaker 2: Array?
>> Bianca Gandolfo: Yep, we'll use an array. We have some hashing function, that's gonna take our input. It's gonna return a number that could be an index in our array, yeah. And then, we have some operations, you wanna be able to set. Which is gonna take the property in the value, the property or the key called there the interchangeable terms.

[00:01:09] It is going to map to the location, the value is what gets to saved at that location. You could also save the key, which you might need to if we have a collision, yeah? Does that make sense? So when we're hashing, we're not hashing the property and the value.

[00:01:33] We're just hashing the property because if we think about the interface of an object, right. When you're doing a key lookup, you only have a reference to the property. You usually don't know what the value is. If you knew what the value is, you wouldn't be doing the lookup.

[00:01:47] So you wanna be able to pass the property name, so that you can get that value. So your hash function is only gonna take the property name. Even though when you set it you're gonna take both the property and the value, when you get to Gt. You only have the property.

[00:02:02] So your hashing function should be returning a value based on the property, not a property and a value or the value. Just the property. That make sense? Okay, and then you should be able to remove it as well.
>> Bianca Gandolfo: Yeah?
>> Speaker 2: When we set the property, how do you, if we hash the property, we get
>> Bianca Gandolfo: So no, when you hash the property, you get like a hash key.

[00:02:41] So whatever it returns, so you put your property into your hashing function and it returns some value. And you could call that a hash code, a hash key, something like that.
>> Speaker 3: How to, so why do we see the values here in the, so the property we pass through the hash function, and then we get values.

[00:03:01] So at the beginning, if we set a value how does it works?
>> Bianca Gandolfo: Well, so I think what you're thinking about is you're thinking about the value of the hash being the value of the property. And it's actually something totally different, so if we open up our.
>> Bianca Gandolfo: Actually let me put it.

[00:03:26]
>> Bianca Gandolfo: I'm gonna put it in here so it's easier to read.
>> Bianca Gandolfo: Okay. So when we are, we have like, we have like myObj equals an object, right? And then you say, myObj.thingamagig, magig, I think that's how you. Could someone spell check that thingamagig?
>> Speaker 2: I think there's a j.

[00:03:58]
>> Bianca Gandolfo: [LAUGH]
>> Speaker 2: The middle g.
>> Bianca Gandolfo: You're right.
>> Speaker 4: Thingamagig?
>> Bianca Gandolfo: Yeah, there we go, thank you. I'm not a good speller. So, myObj.thingamajig is obviously true, I mean what else could it be. Then we have, you know, myobj.hello=, you know Spanish for hello. So, we now have an object It looks like this, right.

[00:04:37] So whenever we are setting a property onto an object we pass it both the property name. Sometimes we call this the key and we also pass the value and so, we have a data structure that looks like this. Deep underneath, and probably not even that deep, probably just below the surface.

[00:04:56] These properties are going to map to some location. And we'll say that we have, let's pretend that this is our memory and each location here has an address. Okay, we want to pass this property into our hash. You know, we wanted to return a memory address which lets just say it's gonna give us three.

[00:05:36] So that means we're gonna save the value true in the location three.
>> Bianca Gandolfo: Okay, and so, this is memory. Okay, now, we want to look up myObj.thingamajig,
>> Bianca Gandolfo: Right? We wanted to return true. So what we do is under the hood, is we hash it again. So we're like we need to look up thingamajig.

[00:06:20] Where is it? You send it through the hash, the hash said, hash says. It's at 3. And then you just go to 3 and get that value. So the hash value actually is mapping to where it's located. While the property name is the name that we give it, right?

[00:06:38] So when we're naming our properties, we're not giving it memory address because that would be really, really difficult, right? If we were constrained to that, we're just giving it a string name and we just wanna map it to somewhere in memory so that it can go there directly instead of having to search through everything to find it.

[00:07:01]
>> Bianca Gandolfo: Is that clarified?
>> Speaker 3: Yeah, the value that pass is different from that time, yeah, that was my question.
>> Bianca Gandolfo: Yep, but yeah exactly. And so every time you pass this though you want it to give you the same value. Because imagine if you got two now, on accident.

[00:07:16] And now you're gonna go look up in memory and it's gonna give you Undefined and that would break everything. So that's why its really important that were getting the same value every time. And then similarly you know, we put hello we want to return whatever maybe 1 and then we're gonna put our value here.

[00:07:45]
>> Speaker 2: This is all a hypothetical use case, right? We haven't seen-
>> Bianca Gandolfo: No, this is what it does underneath the hood. This is like the internals of how your objects are working.
>> Speaker 2: I see.
>> Bianca Gandolfo: Yeah.
>> Bianca Gandolfo: So it's not hypothetical. It's a simplification, for sure, but this is the mechanics of it.

[00:08:15] It's that we're taking a string, we're somehow mapping that string to a location in memory. And getting it out, in constant time, this is what makes it constant time. We couldn't do this, then every look up like this would be, you know at least linear. Unless it's sorted in which case it could be.

[00:08:41]
>> Bianca Gandolfo: Logarithmic, logarithmic because we can make a binary search that's sorted, maybe, cool.
>> Speaker 2: So can you hash say, for example, a graph. So in your travels, you don't need to go both ways. You can avoid the
>> Bianca Gandolfo: I'm not sure, I mean they're definitely algorithms that you use hashing with graphs for like security related stuff.

[00:09:17] But I don't know if that would speed up your graph reversal. But I mean, we're using a hash table in our breakrams, right? We're using an object to make everything faster, right? If we didn't use our object to track where we had been, then suddenly everything gets really complicated.

[00:09:37] Yeah. Cool.
>> Bianca Gandolfo: Mm-hm.
>> Speaker 3: What kind of value we have to pass on in the first function, my function table? See the property values here.
>> Bianca Gandolfo: Mm-hm.
>> Speaker 3: So the value-
>> Bianca Gandolfo: Yeah, so the property.
>> Speaker 3: Yeah.
>> Bianca Gandolfo: Would be like thingamajig and the value would be true.

[00:10:05] So this is how objects actually work, right? And if we were to make our own, we can make a set function set set method, and we say thingamajig and then, true. And that would do the same thing as here where we're just setting it directly using dot notation.

[00:10:37]
>> Bianca Gandolfo: Right? And then.
>> Bianca Gandolfo: Right and those of you who are familiar with object oriented language are really familiar with setters and getters.
>> Bianca Gandolfo: I should have chosen a smaller word.
>> Speaker 2: Does JavaScript not have a formalized dictionary object?
>> Bianca Gandolfo: No.
>> Speaker 2: Because its, I'm getting confused cuz this just seems like a-

[00:11:09]
>> Bianca Gandolfo: It is a dictionary. It's another word for it, dictionary, HashMap.
>> Speaker 2: Okay, so a dictionary is a.
>> Bianca Gandolfo: As far as JavaScript is concerned yeah, it's all the same.
>> Speaker 2: And then the actual hashing part just takes place under the covers like that is just-
>> Bianca Gandolfo: Yeah.

[00:11:30]
>> Speaker 2: Okay.
>> Bianca Gandolfo: Yep.
>> Speaker 2: Okay.
>> Bianca Gandolfo: Yep. Awesome