My First Data Structure: Hash Tables

If you have any coding experience, I’m guessing you’ve probably heard of a hash table before, though you might know it by a different name. If you’re a JavaScript developer, you’d know them as Objects. If you know Ruby, you’d simply call them hashes. In Python, they are called dictionaries. In other languages, they’re known as hash maps, maps, unordered maps, etc.

What I’m trying to say is that if you have any coding experience, regardless of the language you’re coding in, you’ve definitely heard of/seen/probably used a hash table before. And, if you are studying for a technical interview, you are going to want to be familiar with hash tables, how to use them, and most importantly, why you want to use them over another data structure like an array.

eeeeep

Hash Tables: The Basics

In basically every coding language (or at least those I’m familiar with!), hash tables are denoted by curly braces: {}. This data structure allows us to map keys to values. Very basically, a hash table (aka an object in JS) can look like this:

let michael = {
  age: 45,
  hobbies: ['ice hockey', 'improv'],
  manager: true,
  catchphrase: function() {
    console.log('that's what she said!')
  }
}

In theory both keys and values can be any type of data. In a basic JS object, however, a key must be a string (although ES6 has introduced both Maps and Sets which function similarly to a basic JS object and allow you to store any data type as a key!).

Hash Tables: The Pros and Cons

There are a lot of benefits of using Hash Tables. In comparison to an array, for example, where searching requires a loop and can take a comparatively long time (O(n)), hash tables are much faster to search through (O(1)), making them much more useful for databases. Similarly, inserting and deleting data from a hash table is also very quick (O(1)) in comparison to other data structures such as arrays where inserting and deleting can be much slower (O(n)).

Unfortunately, there are some issues with hash tables. One major issue with hash tables is the possibility of collisions. Since computers have limited memory, occasionally, when creating a hash, a single spot in a computer’s memory can be used to store multiple pieces of data.

hash collision

Here, the computer is attempting to store two pieces of data (the info for both Sandra Dee and John Smith) in one “bucket” or space in memory. This is a collision.

Although collisions are an issue and can slow our hash tables down quite a bit (O(n)), fortunately for us, there are lots of way to resolve collisions.

Using a Hash Table: First Recurring Char

The problem statement: Given an array, find the first recurring character.

Basically, what we want to do in this problem is take our given array, such as [‘michael’, ‘jim’, ‘pam’, ‘jim’, ‘phyllis’, ‘stanley’, ‘michael’], and figure out which character (lol) is repeated first/which character whose index of second occurrence is smallest. To be clear, in our example, we are looking to return ‘jim’.

Here is my first attempted solution to this problem:

recChar = (a) => {
  
  let charMap = {}
  for (let char of a) {
    if (charMap[char]) {
      charMap[char] += 1
    } else {
      charMap[char] = 1
    }
  }
  
  for (let i = 0; i < a.length; i++) {
    if (charMap[a[i]] > 1) {
      return a[i]
    }
  }
}

I thought this solution was great, when I first wrote it, and it actually worked on my first test case, however there is an issue. If you try running this code in a repl, you will probably see that you are returning ‘michael’ and not ‘jim’.

While ‘michael’, like ‘jim’, does recur in this array and while ‘michael’ is in the smaller index than jim, we are looking for the smallest index of second occurrence, not the smallest index of first occcurrence. Thus, the answer we want to get is ‘jim’.

Although this solution is wrong, I though it might be helpful to see the idea of creating a charMap. What our charMap does, is keep track of the number of times a character is repeated throughout the array. If a character already exists in our charMap, it will increment each time we come across that character again. If not, it will add that character to our charMap with a value of one. Again, while this solution is not giving us exactly what we want, I thought showing the construction of our charMap/object/hash table would be really helpful in understanding my ultimate solution to this problem.

First Recurring Character: My Solution

recChar = (a) => {
  let map = {}
  
  for (let i = 0; i < a.length; i++) {
    if(map[a[i]]) {
      return a[i]
    } else {
      map[a[i]] = 1
    }
  }
}

You might be thinking that this solution looks very similar to my incorrect solution from up above and you’re right! These two solutions are quite similar, however, in this one we are not incrementing when we come across a recurring character as we did above. Instead, we know that once we reach a recurring character, then we can immediately return as that will be our first instance of recurrence in our array.

hash browns!

I hope you found this basic introduction to hash tables useful! When I was first learning to solve algorithms, I was, for some reason, really confused by the idea of a hash table. Even though, I had used objects in writing JS code before, I could quite understand why they’d be helpful in solving algorithms, or even in general coding. Hopefully, you can now see why they are useful and avoid the same confusion that I did!

Happy coding!