JavaScript Hash Tables

Hash tables are one of many data structures. Hash tables can conceptually be thought of a JavaScript arrays with predetermined length. You can imagine that this is what a hash table looks like:

We call these predetermined spaces (this is where we hold the data), buckets (picture below).

The way we insert data into a hash table is through a hashing function. This is the most integral part of hash tables. This is what a hashing function looks like:

A hashing function is a function that take a key and the max amount of buckets in your hash table as it’s two arguments. The hashing function takes theses two arguments and returns an index in the hash table, where the hashing function will insert the data into the hash table. The neat thing is that whenever you insert the same key into the hashing function it returns the same index, resulting in O(1)/constant time complexity! This is the biggest advantage to hash tables. This is the fastest way to access values/data. So if speed is important for you hash tables might be for you. Here is an example of using the hashing function to insert data into the hash table:

In the example above you can see that every time we run the same key (‘Tacos’) in the hashing function we receive the same index back. This allows us to find our data in the hash table EXTREMELY fast. To retrieve data we just need put a key of previously stored data into the hashing function, and the hashing function will tell us exactly where the data is in the hash table!

As amazing as this sounds, I should probably warn you that sometimes the hash table puts two different pieces of data into the same index/bucket of the hash table. We call this a collision. Here is a visual example:

In the example above, the hashing function inserted “Pizza” and “Tacos” into the same index/bucket of the hash table. We call this a collision.

Hash tables handles collisions by creating tuples. A tuple is a column of data in a hash table. In other words, the empty bucket becomes an array so now it has more space available to store more data, you can picture an array within another array as one of its elements. To access data from a tuple would now be O(n)/linear time complexity. Once the hashing table gave you the index of where your key is stored inside the hash table you would now have to loop through the tuple to find the data, resulting in O(n)/linear time complexity for the tuple.

Now I will show you visual examples of how a hash table works. Lets start with an empty hash table

Here we have an empty hash table that is going to store the phone numbers of my friends. Currently the hash table is empty, but we just put my friend Jim through the hashing function and received what index in the hash table Jim will be placed at. Jim will be placed at index 8 in the hash table. Here is what that would look like:

Jim has now been inserted to the eighth index of the hash table. Now lets insert my friend Brittany into the hash table as well. In order to insert Brittany, first we need to put her through the hashing function. Lets do that now:

Now we have put my friend Brittany through the hashing function we have received the index of where she will be stored in the hash table. Brittany will be stored at index three inside of the hash table. Lets insert her into the hash table now:

Now we have Brittany and Jim, stored into the hash table, perfect everything is working perfectly. Lets see if we can retrieve Jim’s number by putting Jim through the hashing function and hopefully receiving the correct index in the hash table that Jim is stored at. Lets try that now:

Perfect, we received the correct index, eight! I used a get method which does the same thing as a hashing function but checks for tuples too. Now lets insert my friend John

Oh no! After running John through the hashing function, the hashing function is going to put John at index eight in the hash table, but index eight is were Jim is stored! Since we have a collision at index eight, lets turn index eight into a tuple so we can hold both Jim and John at index eight.

Perfect, so now we have inserted both Jim and John into the tuple at index 8 in the hash table. This a great way to solve a collision. Now lets go back to inserting my friends.

Wow, it looks like Becka also got inserted to the eighth index in the hash table, but its no biggie, because we already have a tuple at index eight inside the hash 😁. So Becka just got inserted into the end of the tuple which is perfectly fine.

Well that’s all for today, I hope you have gained some knowledge that you can spread 😁.

Related posts:

When it comes to working with data in programming, there are many different ways to organize it. One of the most common data structures is a linked list. A linked list is a collection of nodes, each…

It sounds really simple, right? But before You start reading my story, You need to get to know me better. So let me quickly introduce myself in a few hashtags: Unfortunately, still, not too much…

Everyday expecting mothers are getting advice from multiple faucets, with some having good reasoning and facts behind them while others are just old wise tales that elderly people might tell them…