Hash Tables Explained and Implemented in JavaScript

One of the most used concepts in coding interviews, hash table. Many modern programming languages have built-in hash tables, which makes it very simple to use; for example in Python, its Python dictionary, and in JavaScript, it’s JavaScript object.

Photo by Tom Fisk from Pexels

What is a hash table?

A hash table is a data structure that allows us to store pairs of keys, and values, where every key maps to a value. In a hash table, you can access a value given a key. These are very powerful and common data structure, it is used often in practice and in coding interviews.

Fundamentally, hash tables are quite complicated, but for the purpose of coding interviews, we can just focus on the simple concepts.

Let’s look at an example,

"act" => 1  
"sun" => 2            
"fly" => 3

Here the keys “foo”, “bar”, “baz” maps to value 1, 2, and 3. I can access the value 1, given the key “foo” but we cannot use the key “foo” to find the value 1.

Insertion, search, and deletion of a key-value pair in the hash table all run in constant time O(1) on average.

We use a hash function to change a key into an index to fit in an array. When you search for a value of a given key, you will use this hashing function to change the key into an index, it maps to. If you find the index, you can grab the value in the array and that’s the constant time index.

Transform String into an Index

To change a string into an index, we can map every element in the string to its ASCII character encoding. You will have one integer per element, calculate the sum of all the integers to get the number.

                      ASCII         ASCII % length of the array - 1
"key1" => 1            134           139 % 3 = 1(1 is the reminder)
"key2" => 2            353           353 % 3 = 2
"key3" => 3            639           639 % 3 = 0
indecies   0  1  2
let arr = [3, 1, 2]

If we map every character in the string'key1' to its ASCII encoded value, add all the integers and get 134. Next, we’ll use the modulo operator % to get to the array position. So, it would look something like this, 134 % length of the array the answer will between 0 and the length of the array minus 1. Let’s say the length of the array is 3, 134 module length of 3 will be 1. At this point, we can store 1 at the index of 1. Repeat the same formula with strings ‘sun’ and ‘fly’ and store the values 2 and 0 in the array. Finally, this gives us the relevant indices for each key.

Collisions

Now let’s assume our second string 'key2' is also maps to 1, which means we now have two keys mapped to the same value, 1. This portrays that the hash table isn’t just an array; it's an array where each index maps to a linked list of potential values. This mainly takes care of situations where we have two keys get hashed into the same index and collides, which is known as a collision in the hash table.

ASCII               
"key1" => 1            139 % 3 = 1 \
                                     > Collision
"key2" => 2            352 % 3 = 1 /
"key3" => 3            639 % 3 = 0

To resolve the collision, we simply place all the keys with the same hash value in a separate linked list. In this case, the array will have three linked lists, value 3 at index 0, value 1 & 2 at index 1, 1 -> 2 . Now, you might be wondering how would you know which of the two values in indices, 3 is related to “key1” and “key2”. To look up the keys, each value also needs to point back to their key. So, value 3 will point back to “key3”, value 2 will point to “key2”, and value 1 will point to both value 2 and “key1”. This process makes it clear which key is related to which value.

Hash table support constant time, O(1) insertion, deletion, and search on average. In the worst case, the time complexity is O(n), linear time. If you end up in a scenario where you’re detailing with one long linked list or let say you’ve 15 values and 12 of them collide with one another and the rest is separate, this linked list of length 15, will be a linked list of length n; O(n) in the worst case. We use hashing functions to minimize the number of collisions. In fact, these hashing functions are so powerful that in the industry, we often forget about the linear time worst-case scenario. We almost always treat it as though the hash table supports constant time insertion, deletion, and searching on average.

So, it takes O(n) run time to initialize a hash table, n element in it. The space complexity depends on the values you’re storing because we only store the values, not the keys; we only point at the keys in the memory. As a result, the space complexity is O(n) for storing.

Finally, let’s go through a simple hash table interview question.

Question: Given a string str, determine whether it has all unique characters.

Input 1: “xyz”

Output 1: true

Input 2: “xyzz”

Output 2: false

function uniqueString(string){
        // create a hash table by assiging it to storage
        let storage = {}
        //start iteration at index 0
        let i = 0
        
        //enter the while loop
        while(i < string.length){
            //assign char to the value of the index
            let char = string[i]
            
            //check if the char is not in the storage hash
           if(!storage[char]){
                // add it in the hash table and increment
                storage[char] = true
                i++
            }else{
               //if char is already in storage return false
               return false
            }
        }
        //true, if you make your way out of the loop without any duplicate value   
     
        return true
    }

This program runs in O(n) times, where n is the length of the string. The space complexity is O(n), n is the values stored in storage, our hash table.

Previous posts:

Type Checking using PropTypes in React

12 Most Common JavaScript Number Methods

12 Must KnowArray Methods for the Next Interview — JavaScript

Arrays: Left Rotation (JavaScript)