Using a Hash Map

Photo by GeoJango Maps on Unsplash

In programming, we often have to take a set of data and traverse through it to find a given value or perform an action. For us beginners, the first thing that usually comes to mind is using a loop; we go through every element of our data until we get a solution that matches our conditions. This works great for most small-scale searches and basic computations, but when the data set gets too big, or we need to backtrack to values we have already passed in our loop we can see some of the shortcomings of the traditional loop.

If you have been learning about programming, you most likely have seen or heard of hash maps at some point, they are everywhere. When I first started learning I was confused about what a hash map was as if it was some mystical data type I hadn’t discovered yet or something that only exists in certain languages. I felt confused about it and didn’t seem to need it so I just kept trucking. I wrote another post here about building a binary tree data structure and how we can use that to manage large data sets; well it turns out a binary tree is an implementation of a hash map!

So what is a hash map? In short, it is a data structure that uses key-value pairs to keep track of values that have been passed in our iteration. Here is a simple example to show the concept.

const arrayToMap = [3,6,4,12,1,23,8,10,26]
//I am manually entering the elements here for the hash map
//the key will be the valueand the value is the index
const hashMap = {3:0, 6:1, 4:2, 12:3, 1:4, 23:5, 8:6, 10:7, 26:8}

Above we have an unordered array and a hash map of the array's values. We can see the value followed by its corresponding index from the original array. We can now order the hash map by values and still retain the position within the original array. This prevents us from having to manage how to add new values in the correct place. We just push them to the array and can manage position in the hash. Below is the same hash but ordered by value instead of by index.

const hashMap = {1:4, 3:0, 4:2, 6:1, 8:6, 12:3, 10:7, 23:5, 26:8}

This can be really powerful! Now we have our original data in the array left totally untouched and all the info we need from it to perform our actions, AND since we have retained the original indexes as the keys in our hash we CAN manipulate the original array very easily. We just need to find the value in our hash and use its key to access that value in the original array.

arrayToMap[0] //this returns 3 since our value at index 0 is 3
arrayToMap[0] = 20 //changes the value from 3 to 20

Pretty simple right!?

Now we can use this structure to try and solve a problem. Let's look at the problem of TwoSums. This problem asks us to take an array of numbers and find the TWO values that add up to a given target number. When I looked at this problem I immediately jumped into using loops and set up a brute force solution.

const twoSum = (array, target) => {
    let indexes = []

    for(let i = 0; i < array.length; i++){
       for(let j = i + 1; j < array.length; j++){
          if (array[i] + array[j] === target) {
            indexes.push(i);
            indexes.push(j);
          }
       }
    }
    return indexes;
}

This takes the first value of the array and adds it to every other value in the array then checks if it is equal to the target number. It’s a fine solution and works well if the data set isn’t too large, but there is a better way. Below we will implement a hash map to keep track of the values we have passed already, and I’ll explain why that’s important after we look at the function.

const twoSum = (array, target) => {
  const hashMap = {}
  for (let i = 0; i < array.length; i++) {
     hashMap[array[i]] = i;
    }
  for (let i = 0; i < array.length; i++) {
    let diff = target - array[i]
    if (hashMap[diff] !== undefined && hashMap[diff] !== i) {
      return [hashMap[diff], i]
    }
  }
}

In this function, we first create our hash map by iterating through the array and assigning the key-value pairs the hashMap variable. Since we have ALL of our values inside that hash map we can easily just check for the number that we need. We determine the number that would be necessary by subtracting the current value from the target number, then we check if that value is in our hash map. We can search for a value in the hash map using the same syntax we would for accessing an index of an array, and we don't have to iterate through every element to find it.

hashMap[x] //x = the number you are searching for

We can do this since we set all of the keys to the actual values and the value to the index!

By implementing a hashing method we reduce our overhead significantly. Now instead of comparing each element from the array to one number at a time and testing if it meets our condition, instead we just find out what number is needed to meet the condition and check if we have that number in our dataset via the hash map. This means much less iterating, and still very readable code. Understanding different data structures can give us more options for efficiently managing our data, and many structures build on this concept of a hash map, now we just need to practice using it.