Are you preparing for a technical interview for your first job? Maybe you’re like me: a code school grad with a non-tech background and now needs to learn algorithms and
data structures to pass that first round of interviews. There was no time in my 3-month code school to teach this subject, nor do I think this subject should have been included. I’ve been told over and over again that data structures are not so much used on the job. If you ever needed one though, you could google it. Nevertheless, all my technical interviews so far have consisted of a a HackRanker 6 to 8 question automated timed test where the questions all had to do with data structures and algorithms. I still haven’t passed any of these tests, so I’ve never gotten to the 2nd round where, I assume, I might have the chance to talk about my coding projects and experience.
So let’s cracking and talk about one of those data structures we’ll have to learn and practice as we look for jobs: the hash table AKA hash map. (I’ll use both those terms interchangeable in this article.)
You already have a good idea of what a hash table is, I’m sure! Think of objects in JS, dictionaries in Python or hashes in Ruby. They all share the same basic idea with the hash table data structure. You’re essentially working with key/value pairs. For the phonebook on your cell phone, for example, you can take a name like “Orlando” and you can store his cell number “555-1212” under his name. The name “Orlando” becomes the key we’ll use when we want to retrieve the value “555-1212”.
What I’ve taken for granted, having worked mostly with JS for my short tech career, is that JS’s version of a hash table--an object--comes right out of the box with JS. A JS object is pre-baked and ready to use. All I have to do is click my heels and type in a couple of braces and I’m ready to start adding key/value pairs to my JS object.
However, now with this data structure called “hash table” we will “rip” the pretty packaging off our JS object and see what is inside, how it “ticks” and how we can make our own hash table from scratch without relying on JS’s pre-baked version of a hash table AKA JS object.
Recipe For A Hash Table
Our Hash Table made from scratch will just need three ingredients:
First: An array. For our array, think of a chocolate bar like this
Note our chocolate bar consists of defined squares.
For a hash table, our array also has these “chocolate squares”, except in “Hash Table land” the chocolate squares are called buckets. Each bucket will contain some information, for example, we will put Orlando’s cell phone number in one of those buckets.
Second: Now that we have an array, we’ll need the information we’ll store in the hash table. In our case, we’ll need the keys (the names we want to put in our hash map), and the keys’ corresponding values ( the cellphone number of each person)
Third: here’s where the magic happens--in order to convert all this raw information from step 2,we’ll need a
hash function. Our hash function will stuff each cell phone number into a “bucket” in our array and then will associate each individual phone number with its corresponding name. How will the hash function relate a number to a name? Remember an array has indices. The hash function will use an index as a kind of an address that will allow us to find Orlando’s phone number. What index was his number at again? The magic hash function will set that up.*
Let’s look at a picture:
(Picture courtesy of:
Jorge Stolfi - CC BY-SA 3.0)
Let’s identify what we see in the picture above as it relates to our hash map recipe.
On the right side of the picture we see our array. Our array consists of a series of “buckets”, each of which can contain information. Each of those buckets has an index number assigned to it. In the picture above, the indices of our array range from 0 to 15.
On the left side, you see we’re inserting our information: names as keys plus their corresponding telephone numbers.
Lastly you see the hash function in the middle of the picture. The hash function is taking our key/value pairs and inserting the values(telephone numbers) into the array buckets. The hash function will remember where it put a particular telephone number by taking note of the “address” or index corresponding to the bucket.
And so there you have your basic hash map. So now you’ve stepped beyond your basic JS, Python or Ruby and know more about what’s under the hood of your JS Object, Python Dictionary or Ruby Hash.
But what about the implementation of the actual hash function? You want to see how the magic happens? Stay tuned for Part II.
In the meantime,
Keep coding out your dreams!
Namaste
*More on the specifics of the Hash Function in Part II of this article coming shortly.
Oldest comments (1)
Great article. Looking forward to part 2!