Beginners Guide: Hash Tables

#javascript

As humans, we associate two concepts, ideas, or values with a definition. For example, Heather is a name. I can then say, 'my name is Heather'. Another way to write this association might be Name: Heather.

In programming, we call this a key-value pair. Key values pairs are used when we want to store a value and then reference that value by a key name that we give it.

In JavaScript we use objects to store key-value pairs. To make an object in JavaScript we can simply use curly braces {}. Objects were written into JavaScript for use. But how were they created? The hash table data structure is the foundation or blueprint for JavaScript objects.

Hash Table Data Structures

A hash table is a data structure that associates values with a label(what we refer to as a key in objects). These label value pairs are stored in a table of a predetermined length. The storage table is an array that contains another storage element at each index. This element is referred to as a bucket.

This post will show how you can use JavaScript ES6 Map object as the bucket storage container. Before we can talk about storing label value pairs in a bucket, we need to go over how they are assigned to a numerical index.

Hashing Functions

To store a value in our hash table we need to place it at an index in our storage array. The number that determines the index will come from hashing our label using a hashing function. A hashing function takes two inputs, any data type, and a number. The number is the length of our hash table as the function can only return numbers as long as the length of the array.

Do not worry about needing to know how to create a hash function. This Software Engineering Stack Exchange discusses various hashing functions and their desirability. A preferred hashing function will provide speed and limit the possibility of collisions.

There is a possibility of getting two keys that hash to the same index which is called a collision. Collisions can slow down your lookup methods and should be avoided.

Example of a hashing function:

const hash = (key, size) => {
  let hashedKey = 0;

  for(let i = 0; i < key.length; i++){
    hashedKey = key.charCodeAt(i);
  }

  return hashedKey % size;
}

Creating a Hash Table with Map

Let's walk through the steps of implementing a hash table.

class HashTable {
  constructor() {
    this.size = 20;
    this.storage = Array(this.size);

    for(let i = 0; i < this.storage.length; i++){
      this.storage[i] = new Map();
    }

  }

Here we create a hash table using ES6 instantiation pattern. Notice this.size is hardcoded as hash tables have a pre-determined length. We set our storage array this.storage to the size property. We then loop through our storage array and create a bucket at each index which will be a new instance of Map.

Map object was introduced with ES6 and iterates its elements in insertion order. Map also stores key value pairs.

insert(key, value) {
      let idx = hash(key, this.size);
      this.storage[idx].set(key, value);
  }

  remove(key) {
    let idx = hash(key, this.size);
    let deleteKey = this.storage[idx].delete(key);
    this.storage[idx].delete(key);
    return deleteKey;
  }

  search(key) {
    let idx = hash(key, this.size);
    return this.storage[idx].get(key);
  }

Hash tables have three main methods, insert, remove, and search. Our hash function is used for all three methods. This is because when we insert a key-value pair we need a number and when we give a hash table a key to look up or delete it needs to hash the key and use the number to find the value. Notice set, get, and delete in our implementation code, they are built-in methods of the Map object.

Hash Table in Action

We create a new hash table called nolaFoodieBucketList and assign a label of food items to try to a value of places to have them.

When we log the hash table we can see all the label-value pairs have gone to various buckets. We can also see collisions at bucket 1.

When we search for 'hurricane' we receive 'Pat O'Brien's' back, even though there were multiple label-value pairs at bucket 1.

Time Complexity

Hash tables are a favored data structure because on average they provide a time complexity of constant time for insertion, deletion, and search. Hash tables don't need to look through every bucket for a value because it is associated with a key. All the hash table will need is the key to directly find its value. The time complexity of constant time is average due to the possibility of multiples key-value pairs hashing to the same bucket.

Time complexity makes hash tables a preferred choice for data structure when code requires a fast run time to search through data.