How to implement the Hash Table Data Structure in JavaScript

The hash table is an integral part of JavaScript. So fundamental even that many of us fail to consider how it works. Well, fail to consider no more…

Hash Table Characteristics

In order to build our implementation of a Hash Table, we first need to define the characteristics which we need to replicate.

1. A Hash Table stores information using a key and value pair. In other words, when adding information to a Hash Table you must provide both a key and a value.
2. A Hash Table restricts the keys to be strings, the value can be of any type.
3. O(1) lookup time. If you are unfamiliar with Big O notation, O(1) means that as the number of items in the object increases the lookup time remains constant.
4. O(1) insertion time.

Hash Table Implementation

First, let’s create a new function. In JavaScript, we can make custom data structures by using the `function` keyword and invoking our function with the `new` keyword.

function HashTable(n) {
  this.n = n
}

You can see I’ve added an argument n. In our implementation, we define the initial space complexity of the Hash Table. The native implementation of a Hash Table in JavaScript doesn’t require this argument because it resizes the internal data structures as needed in the background. For simplicity, we will define it when we create the Hash Table.

Next, we will create an empty array to hold our data:

function HashTable(n) {
  this.n = n
  this.data = new Array(n)
}

and then we will fill the array with empty arrays:

function HashTable(N) {
  this.N = N
  this.data = new Array(N)
  for (let i = 0; i < this.data.length; i++) {
    this.data[i] = []
  }
  //this.data = [ [],[],[],[],...,[],[],[] ]
}

Now we have an array of length n, filled with empty arrays.

Now we need to map our key:value pairs to our this.data array. To do this, we use a hash function. The hash function will map our keys to indexes in the array. I chose to use the function below:

function createHash(string, N) {
  const arrOfChars = string.split('')
  const sumOfChars = arrOfChars.reduce( (sum, char) => {
    const output = char.charCodeAt(0) + sum
    return output
  }, 0)
  const output = sumOfChars % N
  return output
}

This is BAD hash function for many reasons, however, if fulfills our basic needs. That is, it maps a string of any length to the numbers 0 through N.

This function converts the letters from a string to numbers, adds them to find a sum, then divides that number by n. The remainder from that division will always be 0 through N, which is what we use for the index of the array.

Now, this is what our Data Structure looks like:

function HashTable(N) {
  this.N = N
  this.data = new Array(N)
  for (let i = 0; i < this.data.length; i++) {
    this.data[i] = []
  }
  this.createHash = function(string, N) {
    const arrOfChars = string.split('')
    const sumOfChars = arrOfChars.reduce( (sum, char) => {
      const output = char.charCodeAt(0) + sum
      return output
    }, 0)
    const output = sumOfChars % N
    return output
  }
}

From here we need to add two methods. The first will add key:value pairs, the second will retrieve the value using the key.

Our add method will push a key value pair to the empty array at a given index:

add = function(key, value) {
  this.data[this.createHash(key, this.n)].push([key, value])
}

You’ll notice that if there are two keys which both map to the same index, they are now both stored in the array at that index.

Next, our get method will retrieve the value based on a given key. If the key does not exist, we return undefined:

get = function(key) {
  const arrOfPotentialKeyValuePairs = this.data[this.createHash(key, this.n)]
    for (i = 0; i < arrOfPotentialKeyValuePairs.length; i++) {
      if (arrOfPotentialKeyValuePairs[i][0] === key) {
        return arrOfPotentialKeyValuePairs[i][1]
      }
    }
  return undefined
}

Now, our finished Hash Table looks like the following:

function HashTable(N) {
  this.N = N
  this.data = new Array(N)
  for (let i = 0; i < this.data.length; i++) {
  this.data[i] = []
  }
  this.createHash = function(string, N) {
  const arrOfChars = string.split('')
  const sumOfChars = arrOfChars.reduce( (sum, char) => {
  const output = char.charCodeAt(0) + sum
  return output
  }, 0)
  const output = sumOfChars % N
  return output
  }
  add = function(key, value) {
    this.data[this.createHash(key, this.n)].push([key, value])
  }
  get = function(key) {
    const arrOfPotentialKeyValuePairs = this.data[this.createHash(key, this.n)]
    for (i = 0; i < arrOfPotentialKeyValuePairs.length; i++) {
      if (arrOfPotentialKeyValuePairs[i][0] === key) {
        return arrOfPotentialKeyValuePairs[i][1]
      }
    }
    return undefined
  }
}