JS Monday 11 – The HashTable Data Structure

An HashTable is a simple but powerful data structure which is used to associate a key with a given value.

If you’re coming from PHP , you may remember associative arrays , which are implemented as HashTables !

As you can see in the PHP example above, we’re creating an array which contains key-value data. Nothing strange!

So what’s so special about associative arrays? Why are they so popular and powerful? How are they implemented?

Why HashTables?

HashTables are used to store data, just like arrays or objects.

An HashTable uses a hashing algorithm to compute an index into an array of buckets (or slots ), where we can find the desired data.

Let’s illustrate an example:

Given the example above, we can pretend we have the following associative array ( in pseudocode ):

So, if we want to get the “ Ghibli” brand, we could loop over the array until we find the key “Ghibli” and then we retrive its value… but what if our array has thousands of items? Looping over it will require some time!

And what if we have some kind of hashing function that can retrieve for us the correct array index in a deterministic way?

That’s actually what HashTables do! So, our hashing function (in that case), could just return 4 , which is the index of “Ghibli”! Much more efficient than looping over an array!

Does the previous illustration make sense now?

Are there any chances that we can get the same index for different keys?

Yes of course! That is called collision .

We get a collision every time that two (or more) hashed keys returns the same index.

How do we handle that?

We just store both the key-value pairs in the same index using other collections like arrays or linked lists.

This technique is called separate chaining .

Implementing an HashTable

First of all, we need a simple and efficient hashing algorithm:

Great! With this simple function we’ll be able to always get the same result for the same input. That’s exactly what we need!

Let’s quickly test it:

So now we need to implement our HashTable class!

Let’s write it down:

We just created our HashTable class with 42 buckets. A bucket is a single array index, which we’ll store our data in.

For instance, if we get 21 from our hashing function, that means that we’ll find our desired data in the 21st bucket.

We also use the newest ES6 Map object, which will iterate its element in insertion order and will save us a bit of work!

Let’s implement our insert method:

Pretty easy, isn’t it? And what about a search method, to retrieve our data?

Even easier! Now we just need a method to delete our data:

Believe or not, we’re done! We’ve implemented a super basic HashTable in just a few lines of JavaScript! Let’s test it:

So now we log the following output to the console:

As you can see, “ Giulietta ” and “ DB11 ” causes a collision! Let’s try to retrieve their brands:

Oh yes! It works! And what about deleting some keys?

A Little Disclaimer

Ok, we cheated a bit so far. We implemented an HashTable using the Map object, which is doing some work for us.

We’re not currently managing collisions by hand, but we’ve achieved our task: building a simple HashTable class and understood how it works!