HashTable Data Structure in JavaScript

✋ What is Hash Table?

In this blog, I am going to explain Hash Tables, which are also known as Hash Maps, Maps, or Dictionaries.

A hash table is an associative array data structure that maps keys to values & it is capable to store a large amount of data and retrieving specific elements efficiently.
For Example, We want to create a Phone Number directory of all Users so in this case, the key would be User names & the value would be their phone numbers including other things like STD Code, Country Code, etc.

Notes: Objects in JavaScript are a type of Hash Tables as well.

✋ What is an Associative array?

Associated array is an array that uses strings as an Index so that you can establish a strong association between key and values. But there is no concept of Associative array in JavaScript, We use Object to create this.

const associativeArr =  {firstName: 'JSMount', lastName: 'Technology'};

And we can access values like below using keys as Index.

associativeArr.firstName; // JSMount
associativeArr['firstName'] // JSMount

✋ What is Hash function?

Keep in mind that Array indexes are whole numbers, not strings, so how will we use Array to create Hash Table? And Answer is Hash Function that turns keys into numbers.

Hash function performs a vital role here. it takes key and bucket size as an argument & performs any arithmetic operations on it and returns a hash value that is used as an Index to store key-value pair elements in storage.

💡 Let’s see some algorithms of the hash function.

There are tons of complex hash functions available over the internet, so no need to write your own custom hash function. You can find any of them and use them. Make sure it should be consistent for one hash table implementation. Let's see some examples of the hash functions.

• 💎 A simple hash function would be a function that adds all the ASCII values (Char Code) of the input string all characters and mod by bucket size.

function hash(key, size) {
    let hasCode = 0;
    for (let index in key) {
      hasCode += key.charCodeAt(index);
    }
    return hasCode % size;
  }

***** Output *****
hash('FirstName', 10) // 10 is a bucket (array) size.
5
hash('PhoneNumber', 10)
3

• 💎 counts characters of the string and then divide total to the size of the hash table and return the remainder.

function hash(key, size) {
    let len = key.length; // get count of characters
    return len % size; // mod by size and return.
  }

********Output**
hash('America', 20) // 20 is storage size. It can be any number.
7
hash('India', 20)
5

✋ What is Collision?

It may be possible that the same hashCode can be generated for different keys by the hash function, which means two different data are going to store on a single index. This scenario is referred to as a hash collision.

Collisions are a problem because every slot in a hash table is supposed to store a single element only.

• For a large scenario, we use a complex hash function to avoid the collision.
• Here We have taken a very small bucket size but in real scenarios, size is always a big prime number to Avoid Collision.

💡 There are mainly 4 ways to handle this Collision.

1. Linear probing – (explained this with diagram)
2. Separate Chaining – (explained algorithm for this method)
3. Resizing the Array or List – (explained algorithm for this method)
4. Double hashing – (only Definition)

💡 Linear probing –

This is basically a method to walk down the array from the collided index until you find the next free slot in the bucket. We can clearly understand by its Flow diagram.

💡 Chaining –

This is the most used method in the Hash table. In the separate chaining strategy, each slot of the hash table (array) holds a pointer to another data structure such as a linked list, tree. We can also use an array of array to contains elements in this strategy as well.

Chaining allows us to map multiple key-value pairs at the same index in constant time. This strategy greatly increases performance but takes more space to store data.
The First Flow Diagram of this post is an example of Chaining. Please refer to that.

💡 Resizing the Array or List –

In this strategy, We can set a threshold limit and once it is crossed, we create a new table that is double the size of the original then copy all elements from the previous table to this new table.
Mostly we set this threshold limit to 60% of the table is filled and resize operation needs to take place when this limit crossed.

💎 What is Load Factor?

If we have a total of n entries in the hash table and size of the table is m, so
"n / m" is called Load Factor.

loadFactor() {
  return this.length / this.size;
}

*** If this Load factor is greater then 60% , called resizing function.
if (loadFactor() > 0.6) {
 // call resize() function. 
}

💡 Double hashing –

In this strategy, there are two has functions. If the first Hash Function produces an index that causes Collision, in that case, second has function comes into action and use to create an offset value. Double hashing can find the next free slot faster than a linear probing approach.

const hashIndex = (firstHashFunction(key) + i * secondHashFunction(key)) % size;

***** Let’s Start Coding ****************

We will see hash table creation using two methods in this article. One is Chaining and the Second is Array resizing. These two methods are mostly used and also asked in the interview.

💻 Let’s see Hash Table Collision Program

/**
 * hash function - Get all CharCode and add them then take mod by bucket size
 */
function hash(key, size) {
  let hasCode = 0;
  for (let index in key) {
    hasCode += key.charCodeAt(index);
  }
  return hasCode % size;
}

class HashTable {
  constructor() {
    // In real scenario, bucket size always a big prime number
    this.size = 3;
    this.length = 0; // number of elements
    // Create an array of above size and initally fill all slot by null value
    this.values = new Array(this.size).fill(null);
  }

  add(key, value) {
    const hashIndex = hash(key, this.size);
    console.log(hashIndex);
    this.values[hashIndex] = [[key, value]];
    this.length++; // increase length size
  }
}

//create object of type hash table
const ht = new HashTable();

ht.add("Taylor", "222-222"); // hasCode is 2
ht.add("Krish", "333-333"); // hasCode is 0
ht.add("Mike", "666-666"); // hasCode is 0

// Mike overrides Krish element because of same Index

console.log(ht);

💻 HashTable Create, Insert, Delete & Search Program using Chaining Method with Array Data Structure

/**
 * hash function - Get all CharCode and add them then take mod by bucket size
 * @param {*} key - input string
 * @param {*} size - bucket size
 */
function hash(key, size) {
  let hasCode = 0;
  for (let index in key) {
    hasCode += key.charCodeAt(index);
  }
  return hasCode % size;
}

// Created Class HashTable using class keyword, You can use function keyword as well.

class HashTable {
  constructor() {
    this.size = 5;
    this.values = new Array(this.size).fill(null);
    this.length = 0;
  }

  add(key, value) {
    const hashIndex = hash(key, this.size);
    // check data exists or not
    if (!this.values[hashIndex]) {
      this.values[hashIndex] = [[key, value]];
      this.length++; // increase length size
    } else {
      let isKeyUpdated = false;
      // get all keys on a hashIndex and loop over
      const arrKeys = this.values[hashIndex];
      for (let i = 0; i < arrKeys.length; i++) {
        // if key found, replace its value
        if (arrKeys[i][0] === key) {
          arrKeys[i][1] = value;
          isKeyUpdated = true;
        }
      }
      // if same Key does not exist, push new [Key value]
      if (!isKeyUpdated) {
        this.values[hashIndex].push([key, value]);
        this.length++; // increase length size
      }
    }
  }

  search(key) {
    const index = hash(key, this.size);
    const slot = this.values[index]; // find slot in bucket array
    // check if slot does not exist
    if (!slot) {
      return false;
    } else {
      for (let i = 0; i < slot.length; i++) {
        if (slot[i][0] === key) {
          // match key
          return this.values[index][i][1]; // return value
        }
      }
    }
  }

  remove(key) {
    const index = hash(key, this.size);
    const slot = this.values[index]; // find slot in bucket array
    if (!slot) {
      return "Key not found";
    } else {
      for (let i = 0; i < slot.length; i++) {
        if (slot[i][0] === key) {
          slot.splice(i, 1);
          this.length--;
          return true;
        }
      }
    }
  }
}

//create object of type hash table
const ht = new HashTable();
//add data to the hash table ht
ht.add("John", "111-111-111");
ht.add("Taylor", "222-222");
ht.add("Krish", "333-333");
ht.add("Mack", "444-444");
ht.add("Den", "555-555");
ht.add("Mike", "666-666");
ht.add("John", "111-111-222");

console.log(ht);

Search and Remove an Item:

💻 HashTable Create, Insert, Delete & Search Program using Chaining Method with Linked List Data Structure.

function hash(key, size) {
  let hasCode = 0;
  for (let index in key) {
    hasCode += key.charCodeAt(index);
  }
  return hasCode % size;
}

// Create a Node class
class Node {
  constructor(key, value) {
    this[key] = value;
    this.next = null; // initially it is null
  }
}

// Create List Clas with head, next and Count properties
class List {
  constructor(node) {
    this.head = node;
    this.next = null;
    this.count = 0;
  }
}

class HashTable {
  constructor() {
    this.size = 5;
    // Initially fill bucket with null value
    this.values = new Array(this.size).fill(null);
    this.length = 0;
  }

  add(key, value) {
    const hashIndex = hash(key, this.size);
    const node = new Node(key, value);
    if (!this.values[hashIndex]) {
      this.values[hashIndex] = new List(node);
    } else {
      let current = this.values[hashIndex].head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.values[hashIndex].count++;
    this.length++;
  }

  search(key) {
    const index = hash(key, this.size);
    const slot = this.values[index];
    let current = slot.head;
    if (current.hasOwnProperty(key)) {
      return current[key];
    }
    while (current.next) {
      if (current.next.hasOwnProperty(key)) {
        return current.next[key];
      } else {
        current = current.next;
      }
    }
    return "Data not found";
  }

  remove(key) {
    const index = hash(key, this.size);
    const slot = this.values[index];
    let current = slot.head;
    if (current.hasOwnProperty(key)) {
      slot.head = current.next;
      slot.count--;
      this.length--;
      return true;
    }
    while (current.next) {
      if (current.next.hasOwnProperty(key)) {
        current.next = current.next.next;
        slot.count--;
        this.length--;
        return true;
      } else {
        current = current.next;
      }
    }
    return false;
  }
}

//create object of type hash table
const ht = new HashTable();
//add data to the hash table ht
ht.add("John", "111-111-111");
ht.add("Taylor", "222-222");
ht.add("Krish", "333-333");
ht.add("Mack", "444-444");
ht.add("Den", "555-555");
ht.add("Mike", "666-666");
ht.add("John", "77-77");
ht.add("Jack", "88-88-88");
ht.add("Jimmy", "99-99");
ht.add("Harry", "121-121");
ht.add("Meet", "232-232");
ht.add("Miraj", "454-454");
ht.add("Milan", "567-567");

console.log("Den Found -", ht.search("Den"));
console.log("Miraj Found -", ht.search("Miraj"));
console.log("Drupel Found -", ht.search("Drupel"));

console.log("Krish Deleted - ", ht.remove("Krish"));
console.log("Mack Deleted - ", ht.remove("Mack"));
console.log("Meet Deleted - ", ht.remove("Meet"));
console.log("Taylor Deleted - ", ht.remove("Taylor"));
console.log("JsMount Deleted - ", ht.remove("JsMount"));

console.log(ht);

💻 HashTable Structure using Array Resizing Method

• Resizing bucket if Load Factor becomes greater than 60% means increase bucket size by double when 60% space is filled. We can also take this 80% as well.
• Create a new bucket & loop on a bucket all elements and push into a new bucket.
• And last assign this new bucket to the original bucket.

function hash(key, size) {
  let hasCode = 0;
  for (let index in key) {
    hasCode += key.charCodeAt(index);
  }
  return hasCode % size;
}

class HashTable {
  constructor() {
    this.size = 5;
    this.length = 0; // number of elements
    this.bucket = new Array(this.size).fill(null);
  }

  /**
   * Resizing bucket if Load Factor becomes greater then 60%
   * Means increase bucket size by double when 60% space is filled.
   * Loop on all bucket item and push into new bucket
   * And last assign this new bucket into origional bucket.
   */
  resize() {
    this.length = 0; // set length 0
    this.size = this.size * 2; // double size
    const newBucket = new Array(this.size).fill(null);

    this.bucket.forEach((element) => {
      if (element) {
        element.forEach((item) => {
          const [key, value] = item;
          const hashIndex = hash(key, this.size);
          if (!newBucket[hashIndex]) {
            newBucket[hashIndex] = [[key, value]];
          } else {
            newBucket[hashIndex].push([key, value]);
          }
          this.length++;
        });
      }
    });
    this.bucket = newBucket;
  }

  // Calculate laod factor  - Total elements / bucket size
  loadFactor() {
    return this.length / this.size;
  }

  add(key, value) {
    if (this.loadFactor() > 0.6) {
      this.resize();
    }
    const hashIndex = hash(key, this.size);
    if (!this.bucket[hashIndex]) {
      this.bucket[hashIndex] = [[key, value]];
    } else {
      this.bucket[hashIndex].push([key, value]);
    }

    this.length++; // increase length size
  }
}

//create object of type hash table
const ht = new HashTable();

ht.add("Mike", "666-666");
ht.add("John", "77-77");
ht.add("Jack", "88-88-88");
ht.add("Jimmy", "99-99");
ht.add("Harry", "121-121");
ht.add("Meet", "232-232");
ht.add("Miraj", "454-454");
ht.add("Milan", "567-567");
ht.add("Bobby", "111-111-111");
ht.add("Taylor", "222-222");
ht.add("Krish", "333-333");
ht.add("Mack", "444-444");
ht.add("Den", "555-555");

// Mike overrides Krish element because of same Index

console.log(ht);

HashTable Data Structure in JavaScript

******************************

You can find all code here:
https://github.com/msaxena25/HashTable-Data-Structure-In-JavaScript

Thank You everyone for reading this POST.

Read Permutation Algorithm in JavaScript
https://www.jsmount.com/javascript-string-permutation-program/

Trie Data Structure – Insert Search Delete & Print Program with JavaScript

HashTable Data Structure in JavaScript