Data Structures and Algorithms in JavaScript

# Implementing a Hash Table Solution

Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Implementing a Hash Table Solution" 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:

## Bianca walks through the solution to the Implementing a Hash Table exercise. The code for the solution is located on the “solutions” branch in the Github exercise repository.

Get Unlimited Access Now

Transcript from the "Implementing a Hash Table Solution" Lesson

[00:00:00]
>> Bianca Gandolfo: So we're just gonna go over the solution for implementing a hash table before we wrap up. So here's our hash table. We initialize it with a size that we can pass in, empty storage, and a counter. So if we wanted to create myHash table, we'd say new HashTable.

[00:00:21] Then we'll pass it [COUGH] into size 5, cool.
>> Bianca Gandolfo: Pretty straightforward, just creating an empty HashTable. So we console.log(myHash), it will look something like this.
>> Bianca Gandolfo: Right size, storage as empty and then count 0, right. So it looks like, cool. So we have this helper function called find, takes a key and it's gonna hash, right, it's gonna hash the key along with the size, right?

[00:01:08] Because the hash function is gonna be different depending on the size of the hash table.
>> Bianca Gandolfo: Cool, so then we just do a look up or,
>> Bianca Gandolfo: This that stores that hash is the value or something that's empty. We have some bucket. We have a match. We have some match index.

[00:01:35] We're gonna loop through our bucket, right? This is if we have multiples. Yeah, if we have multiples in the same place. We'll call it a bucket, why not. Where's our function? So we're gonna loop, look at that. So we're gonna loop through the entire bucket. We're going to say I have an index.

[00:02:03] This is just a gar so that's not looping through crazy stuff, it matches. And then return the item that's the value that we're looking for. And then also the index. Now, at the end of the day, we're gonna return the match, which is the value, the entire bucket, and the match index.

[00:02:29]
>> Bianca Gandolfo: Cool, so this is handling cases where we have multiple items in the same index, right, remember when we had both thingamajig and hello? Both of their values were in the same index. This is the case where we're gonna need to loop through that. We call that, in the index of bucket, and it's full of whatever collisions we might have had, right?

[00:02:53] And we just save them in there. And, if this is optimized and everything, like it is underneath the hood, this isn't gonna happen all the time, and it's gonna keep it within, still, on average, constant time. Cool, awesome. And here's a setter. So it's gonna take your key and value, and we're gonna save the value in its proper place, with the key as well, right, so we can look up later if there's collisions, so,

[00:03:25]
>> Bianca Gandolfo: Here we go. So the match, we're gonna send it through our find, our bucket. So this is if we already have this value saved. So how an object works is you can't have two,
>> Bianca Gandolfo: You can't have different values on the same property, right? So whenever you update, if I had wanted to change thingamajig from true to false, we can't both have thingamajig = true and thingamajig = false.

[00:04:02] It can only be one. And so this is making sure that if it already exists, we're not gonna put it there. We're just gonna update the value, right? So here, if there's a match, you're gonna update the value. Otherwise you're gonna add a new item, right. The new item is gonna be initialized as an empty object.

[00:04:25] We are gonna add the key and value, increment the count, which is gonna be useful later when we're gonna be resizing. When we get to a certain size, right? We're gonna push it into the bucket. And this is our resize, if we have a certain size. And then we just return this at the end so that we can chain, cool?

[00:04:53] Your implementation might be a little bit more simple than this and that's fine, it's just accounting for different situations and also has the extra credit kind of included for the resize. And by kind of, I mean it's using it but we haven't defined it. Any questions? No, cool, and then a getter, we're just gonna use that find function again, get that match.

[00:05:19] You're gonna return match and match.key.
>> Bianca Gandolfo: Or sorry, you're gonna return either the match or match.key, no and. This is true and we're gonna return the value. Okay, so if there's a match, we'll return the value, cool? Questions. Did you guys get a chance to implement these things?

[00:05:48]
>> Speaker 2: Mostly.
>> Bianca Gandolfo: Mostly? Awesome. It's a fun one.
>> Bianca Gandolfo: All right. So just a little summary of hash tables. So the pros, adding is fast, removing is fast, and accessing is fast. The cons, there's no preserved order, right, so some other data structures that we looked into, stacks, queues, linkless trees, have some order in relationships between them.

[00:06:19] Hash tables, we don't have that, but it's really good,5 and anytime you're looking up an item or you're deleting an item, using a hash table or just a JavaScript object is gonna be useful. Why are we implementing hash tables from scratch? Because it's a common interview question, so being armed with this deepens your understanding of how JavaScript objects work underneath the hood.

[00:06:43] But also, it's fair game in an interview and it's pretty common. So know that, cool? Yeah, ES6 gets you a map data structure. It's kind of like a hash table, but it has a preserved order. So you can look into that. It's kind of cool.