Introduction to HashMaps JavaScript

Photo by Ilya Pavlov on Unsplash

There is always more to learn as the ever expansive online world continues to grow. Fresh out the gate, in this blog I will discuss Hashmaps. To go into this topic, I will use a Leet Code Problem as an example to explain what is going on under the hood. With my time in the past couple of months, I have been working on practicing algorithms and code challenges alone and with peers. I had predominantly been using loops and going a layer further, nesting loops within loops, which isn’t good practice, especially because of the time complexity.

Before continuing let me introduce the problem: The problem is titled “Two Sum” on Leetcode. The challenge calls for us to given an array, return the indices that add up to a specific target or number. In other words, we are a creating a function that receives two arguments: first, an array of numbers and second, a target number. Our objective is to return the indices of the numbers in the array, that would add up to the target. The example given is:

Given nums = [2,7,11,15], target = 9
Because nums[0] and nums[1] add up to 9
Our expected output is [0, 1]

Next let’s move onto creating the meat and bones of our function. Initially I would solve this problem with a nested loop, which is very brittle. So instead of showing that, I will show the solution implementing a hashmap.

var twoSum = function(nums, target) {
   const hashmap = new Map();
   for (let i = 0; i < nums.length; i++){
      let currVal = nums[i]
      if(hashmap.has(currVal)){
         return [hashmap.get(currVal), i];
      }
      let difference = target - currVal;
      map.set(difference, i);
   }
}

This is one solution I found online, by Juan Daccarett’s YouTube tutorial and I wanted to go a step further and explain the above code line by line.

So at the top we are using nums and target as two arguments (nums represents the array of numbers and target represents the target number we are adding up to).

We are then creating a new Map object and setting it to the variable hashmap. A Map object is an object in JavaScrip that holds key value pairs and remembers the original insertion order. In the for loop we are iterating through the nums array starting with the number at index 0 as represented by the variable i. Every time we loop through the array, we first create and set the currentValue variable equal to the current number we are iterating over starting with index 0.

Let’s say our nums array = [3, 4, 7, 9, 12] and our target = 16. We want our output to equal [1, 4] which are the indices of the numbers 4 and 12, because 4 + 12 = 16. The if statement in the solution above, only returns true if the currentValue exists in our hashmap. In our first iteration through the nums array, the if statement will be false, so we’ll skip over the return line (and come back to it later).

Next, below the conditional statement we are creating a variable called difference with the value of our target minus the currentValue. So if our currentValue is 3 in the beginning then we are subtracting 3 from 16 or 16 — 3, which returns 13. In the following line we are setting a key, value pair into the hashmap, which will be the difference of the currentValue and target as the key, and the index of the currentValue as the value, or 13: 0.

So the solution will look for the number 13 as we continue to iterate through the array. Our hash after the second iteration will look like:

hashmap = {
   13: 0, 
   12: 1
} 

As we continue, our hashmap will end up looking like:

hashmap = {
   13: 0, 
   12: 1,
   9: 2, 
   7: 3, 
   4: 4 //The code will not reach this point. 
}

Before iterating through the last value, we will meet the conditions as the number 12 (when it is the currentValue) will exist inside of the hashMap. That return statement is returning the value of “currentValue” inside of the hashmap. And currentValue is equal to 12, and 12 in the hashmap has the value of 1. So what is being returned is the numbers 1, and 4, which is the value for the variable i in this iteration.

Hashmaps are great tools for solving problems with optimal time complexity. If you want to learn more about Map and other standard built in Objects, I recommend MDN Web Docs article on them.