Hash Maps

Damely Tineo
4 min readJan 15, 2021
https://en.wikipedia.org/wiki/Hash_table

Note: JavaScript’s Map object is the equivalent of a Hash Map (not to be confused with the map function).

Hash maps (also known as hash tables, hashes and or dictionaries), similar to arrays, are data structures that can be used to store large quantities of data but with a faster and more efficient lookup time.

What’s wrong with arrays?! I like arrays. Really! They're neat, ordered, familiar…but here’s the problem…

Mock technical interview problem (Interview Cake):

You’ve built an inflight entertainment system with on-demand movie streaming. Users on longer flights like to start a second movie right when their first one ends, but they complain that the plane usually lands before they can see the ending. So you’re building a feature for choosing two movies whose total runtimes will equal the exact flight length. Write a function that takes an integer flight_length (in minutes) and a list of integers movie_lengths (in minutes) and returns a boolean indicating whether there are two numbers in movie_lengths whose sum equals flight_length.

When building your function:

  • Assume your users will watch exactly two movies
  • Don’t make your users watch the same movie twice
  • Optimize for runtime over memory

When first approaching this problem my initial thought was “OK, I will loop through the array, combining each element with subsequent elements in the array until I find two that amount to the total duration of the flight. I created a loop within a loop or a nested loop:

flight_length = 120; 
movie_lengths = [150, 50, 70, 20, 40]
function inFlightMovies(flight_length, movie_lengths){
for (let i = 0; i < movie_lengths.length; i++){
for (let j = i + 1; j < movie_lengths.length; j++){
if movie_lengths[i] + movie_lengths[j] == flight_length(){
return true;
}
}
}
return false;
}

While this works it’s not the best approach. Why? The run-time complexity for this solution is O(n²). The outer loop’s runtime is O(n), the inner loop’s is O(n-i), giving us a total runtime of n * n-i (discarding i) => O(n²). Not ideal.

What if there was a more efficient way of solving our problem? While this a short list of elements so the difference in solution doesn't make much of a difference, imagine having a list of 100K movie length times, 500K?, 1M? It might take a while. Engineers are problem solvers and part of solving problems is coming up with the best viable solution which in this case happens to be using a Hash Map or Hash Set.

“Hash Maps are built on arrays…Think of a hash map as a ‘hack’ on top of an array to let us use flexible keys instead of being stuck with sequential integer ‘indices.’” — InterviewCake

Hash maps are characterized by key-value pairs. When using hash maps, we use a key with which to search for elements in our our array, this key corresponds to a value or data associated with the key. Hashing functions help us translate or convert these keys into numbers. These number are then stored in a storage bucket. Now when performing a search operation instead of having to inspect and compare each element of our array, our key, which is now tied to a number pointing to a specific location within our bucket (underlying array), will tell us exactly where our element can be found. This results in a constant number of operations or O(1) for each new search. Remember, retrieving elements at a given index takes O(1) time, regardless of the length of the array.

const flight_length = 120;
const movie_lengths = [150, 50, 70, 20, 40];
function inFlightMovies(flight_length, movie_lengths) {
let set = new Set();
for (let i = 0; i < movie_lengths.length; i++) {
if (set.has(flight_length - movie_lengths[i])) {
return true;
}
set.add(movie_lengths[i]);
}
return false;
}

Hash Set :

A Set, also known as a Hash Set, is very similar to a hash map in both implementation and functionality with the main difference being that hash maps have a key-value pair while a hash set only cares about keys. In the above example I created a Set in which I add the movie length values I want to keep track of. Instead of comparing each value against every other value, like in the nested loop solution, here I just have to check to see if the value in question is already included in the hash set. The value in question being the remaining time difference between the flight length and the current movie. If I do not find matching element, I make sure to add the current movie time to the hash set before I move on to the next movie length time in the array. Yes, I am still iterating through the array but only once resulting in a worst case runtime of O(n).

List of Big O runtimes using hash map/set:

To learn more about hash maps visit: https://en.wikipedia.org/wiki/Hash_table

Thank you for reading!

--

--