Beginners Guide: Hash Tables
Tags: javascript
Published: 2020-03-16 01:41:45



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](https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed) 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](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map). 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.

![create](https://i.imgur.com/3yoqeZY.png)

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.

![log](https://i.imgur.com/sWMyDGx.png)

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

![search](https://i.imgur.com/GMXU74K.png)

###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. 

####Research Resources

[@beiatrix YouTube channel](https://www.youtube.com/watch?v=QuFPIZj55hU)  
[Basics of Hash Tables](https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/)