Data Structure: Hash Table in JavaScript and TypeScript

Hash table data structure is used to store key-value data pairs. Main benefit of using a Hash Table is the performance improvements for set and get operation of data.

NOTE

In this article, we are discussing the implementation of Hash Table in JavaScript and TypeScript.

We are using the “Separate Chaining” method here, to store data if the hash function returns the same value for multiple dataset.

Check the link below to check the details of Hash Table-

Hash Table Details

Step #1: Hash Table Class

Here is how the stored data would look like when stored in array-

Create a class named HashTable.

Define a field “length” to store the max length of the hash table.

Declare a field named “data” to store data.

In the constructor accept the length and initialize the length and the data array.

JavaScript
TypeScript

class HashTable {
  constructor(length) {
    this.length = length;
    this.data = new Array(length);
  }
}

Step #2: Hashing function

Here we are using a hash function for demo purposes. This hash function can vary depending on your implementation.

Define function hash, which accepts an identifier.

Loop over the characters of the string identifier and get the sum of the UTF-16 code of the character.

Finally return the modulus of the sum by the length set in the constructor.

JavaScript
TypeScript

class HashTable {
  // ...

  // This is a sample hash function
  // just for demo purpose
  hash(identifier) {
    const total = [...identifier].reduce(
      (acc, curr) => acc + curr.charCodeAt(0),
      0
    );

    return total % this.length;
  }
  
 //...
}

Step #3: Set data in the Hash Table

This function is used to set key-value pair in the dataset.

Create a method named “set”.

Accept 2 parameters “key” and “value”.

Get the hash of the key.

If the key is not already set in the data array, then set it.

Push the key value in the data array in the key obtained from the hash.

JavaScript
TypeScript

class HashTable {
  // ...

  // Set a key value pair in the hash table
  set(key, value) {
    const keyHash = this.hash(key);

    if (!this.data[keyHash]) {
      this.data[keyHash] = [];
    }

    this.data[keyHash].push({
      key,
      value
    });
  }
  
  //...
}

Step #4: Get data from the Hash Table

Define a method named “get”.

Accept parameter “key”, which is a string.

Generate the hash of the key.

Check if the hash key exists in the dataset. If hash key exists then find the key inside that and return the key-value pair.

If the has key does not exist in data array, then return undefined.

If we can not find the key in the data set then also return undefined.

JavaScript

TypeScript

class HashTable {
  // ...

  // Get data by key from hash table
  get(key) {
    const keyHash = this.hash(key);

    if (!this.data[keyHash]) {
      return undefined;
    }

    const foundItem = this.data[keyHash].find(item => item.key === key);

    return foundItem;
  }
  
  // ...
}

Step #5: Get all Keys

Create a function named “keys”.

Loop through all the indexes of the data array and then return the keys.

JavaScript
TypeScript

class HashTable {
  // ...

  // Get all the keys
  keys() {
    return this.data.reduce((acc, curr) => {
      if (!curr) {
        return acc;
      }

      return [...acc, ...curr.map(item => item.key)];
    }, []);
  }
  
  // ...
}

Step #6: Get all Values

Create a function named “values”.

Loop through all the indexes of the data array and then return the values.

JavaScript
TypeScript

class HashTable {
  // ...

  // Get all the values
  values() {
    return this.data.reduce((acc, curr) => {
      if (!curr) {
        return acc;
      }
      
      return [...acc, ...curr.map(item => item.value)];
    }, []);
  }
  
  // ...
}

Full Source Code

Here is the full source code of Hash Table implementation-

JavaScript
TypeScript

// data-strctures/hash-table/ht.js

// Hash table implementation in JavaScript

class HashTable {
  constructor(length) {
    this.length = length;
    this.data = new Array(length);
  }

  // This is a sample hash function
  // just for demo purpose
  hash(identifier) {
    const total = [...identifier].reduce(
      (acc, curr) => acc + curr.charCodeAt(0),
      0
    );

    return total % this.length;
  }

  // Set a key value pair in the hash table
  set(key, value) {
    const keyHash = this.hash(key);

    if (!this.data[keyHash]) {
      this.data[keyHash] = [];
    }

    this.data[keyHash].push({
      key,
      value
    });
  }

  // Get data by key from hash table
  get(key) {
    const keyHash = this.hash(key);

    if (!this.data[keyHash]) {
      return undefined;
    }

    const foundItem = this.data[keyHash].find(item => item.key === key);

    return foundItem;
  }

  // Get all the keys
  keys() {
    return this.data.reduce((acc, curr) => {
      if (!curr) {
        return acc;
      }

      return [...acc, ...curr.map(item => item.key)];
    }, []);
  }

  // Get all the values
  values() {
    return this.data.reduce((acc, curr) => {
      if (!curr) {
        return acc;
      }
      
      return [...acc, ...curr.map(item => item.value)];
    }, []);
  }
}

export default HashTable;

Demo

Use the following code to check the implementation-

JavaScript
TypeScript

// hash-table/demo.js

import HashTable from "./ht.js";

// Create a new HashTable
let bigBoxHashTable = new HashTable(12);

console.log("\n---------- Hash Table - Set example -----------\n");

bigBoxHashTable.set('Red', 'FF0000');
bigBoxHashTable.set('Green', '00FF00');
bigBoxHashTable.set('Blue', '0000FF');
bigBoxHashTable.set('Yellow', 'FFFF00');
bigBoxHashTable.set('Cyan', '00FFFF');
bigBoxHashTable.set('Magenta', 'FF00FF');
bigBoxHashTable.set('Black', '000000');
bigBoxHashTable.set('White', 'FFFFFF');
bigBoxHashTable.set('Gray', '808080');
bigBoxHashTable.set('Brown', 'A52A2A');
bigBoxHashTable.set('Orange', 'FFA500');
bigBoxHashTable.set('Purple', '800080');
bigBoxHashTable.set('Pink', 'FFC0CB');
bigBoxHashTable.set('Turquoise', '40E0D0');
bigBoxHashTable.set('Lime', '00FF00');
bigBoxHashTable.set('Indigo', '4B0082');
bigBoxHashTable.set('Maroon', '800000');
bigBoxHashTable.set('Teal', '008080');
bigBoxHashTable.set('Olive', '808000');
bigBoxHashTable.set('Navy', '000080');


console.log(bigBoxHashTable.data);

console.log("\n---------- Hash Table - Get example -----------\n");

console.log("Find 'Pink' in hash table: ", bigBoxHashTable.get('Pink'));
console.log("Find 'Black' in hash table: ", bigBoxHashTable.get('Black'));
console.log("Find 'Blue' in hash table: ", bigBoxHashTable.get('Blue'));
console.log("Find 'Green' in hash table: ", bigBoxHashTable.get('Green'));
console.log("Find 'Maroon' in hash table: ", bigBoxHashTable.get('Maroon'));

console.log("Find 'Unknown or wrong color name' in hash table: ", bigBoxHashTable.get('Unknown or wrong color name'));

console.log("\n---------- Hash Table - Get all keys example -----------\n");

console.log("All keys: ", bigBoxHashTable.keys());

console.log("\n---------- Hash Table - Get all values example -----------\n");

console.log("All values: ", bigBoxHashTable.values());

Output:

Here is the output of above demo code-

---------- Hash Table - Set example -----------

[
  [ { key: 'Yellow', value: 'FFFF00' } ],
  <1 empty item>,
  [ { key: 'Indigo', value: '4B0082' } ],
  <1 empty item>,
  [
    { key: 'Brown', value: 'A52A2A' },
    { key: 'Orange', value: 'FFA500' }
  ],
  [
    { key: 'Green', value: '00FF00' },
    { key: 'Magenta', value: 'FF00FF' },
    { key: 'Turquoise', value: '40E0D0' }
  ],
  [
    { key: 'Pink', value: 'FFC0CB' },
    { key: 'Teal', value: '008080' },
    { key: 'Navy', value: '000080' }
  ],
  [
    { key: 'Red', value: 'FF0000' },
    { key: 'Gray', value: '808080' },
    { key: 'Lime', value: '00FF00' },
    { key: 'Olive', value: '808000' }
  ],
  [
    { key: 'Blue', value: '0000FF' },
    { key: 'Purple', value: '800080' },
    { key: 'Maroon', value: '800000' }
  ],
  [
    { key: 'Black', value: '000000' },
    { key: 'White', value: 'FFFFFF' }
  ],
  <1 empty item>,
  [ { key: 'Cyan', value: '00FFFF' } ]
]

---------- Hash Table - Get example -----------

Find 'Pink' in hash table:  { key: 'Pink', value: 'FFC0CB' }
Find 'Black' in hash table:  { key: 'Black', value: '000000' }
Find 'Blue' in hash table:  { key: 'Blue', value: '0000FF' }
Find 'Green' in hash table:  { key: 'Green', value: '00FF00' }
Find 'Maroon' in hash table:  { key: 'Maroon', value: '800000' }
Find 'Unknown or wrong color name' in hash table:  undefined

---------- Hash Table - Get all keys example -----------

All keys:  [
  'Yellow',    'Indigo',
  'Brown',     'Orange',
  'Green',     'Magenta',
  'Turquoise', 'Pink',
  'Teal',      'Navy',
  'Red',       'Gray',
  'Lime',      'Olive',
  'Blue',      'Purple',
  'Maroon',    'Black',
  'White',     'Cyan'
]

---------- Hash Table - Get all values example -----------

All values:  [
  'FFFF00', '4B0082', 'A52A2A',
  'FFA500', '00FF00', 'FF00FF',
  '40E0D0', 'FFC0CB', '008080',
  '000080', 'FF0000', '808080',
  '00FF00', '808000', '0000FF',
  '800080', '800000', '000000',
  'FFFFFF', '00FFFF'
]

Testing

Here is the test cases for the Hash table implementation-

Tests are implemented with ‘vitest’.

JavaScript
TypeScript

// ht.test.js
import { describe, it, beforeEach, expect } from "vitest";
import HashTable from "./ht";

describe("Hash Table", () => {
  let hashTable;

  beforeEach(() => {
    hashTable = new HashTable(12);
    hashTable.set("Red", "FF0000");
    hashTable.set("Green", "00FF00");
    hashTable.set("Blue", "0000FF");
    hashTable.set("Yellow", "FFFF00");
    hashTable.set("Cyan", "00FFFF");
    hashTable.set("Magenta", "FF00FF");
    hashTable.set("Black", "000000");
    hashTable.set("White", "FFFFFF");
    hashTable.set("Gray", "808080");
    hashTable.set("Brown", "A52A2A");
    hashTable.set("Orange", "FFA500");
    hashTable.set("Purple", "800080");
    hashTable.set("Pink", "FFC0CB");
    hashTable.set("Turquoise", "40E0D0");
    hashTable.set("Lime", "00FF00");
    hashTable.set("Indigo", "4B0082");
    hashTable.set("Maroon", "800000");
    hashTable.set("Teal", "008080");
    hashTable.set("Olive", "808000");
    hashTable.set("Navy", "000080");
  });

  describe("Set data operation", () => {
    it("Should have correct length", () => {
      expect(hashTable.data.length).toBe(12);
    });

    it("Should have correct item count in the hash table index", () => {
      expect(hashTable.data[0].length).toBe(1);
      expect(hashTable.data[1]).toBeUndefined();
      expect(hashTable.data[4].length).toBe(2);
      expect(hashTable.data[5].length).toBe(3);
    });
  });

  describe("Get data operation", () => {
    it("Should dequeue correct item", () => {
      expect(hashTable.get("Green")).toMatchObject({
        key: "Green",
        value: "00FF00",
      });
      expect(hashTable.get("Purple")).toMatchObject({
        key: "Purple",
        value: "800080",
      });
      expect(hashTable.get("Black")).toMatchObject({
        key: "Black",
        value: "000000",
      });
      expect(hashTable.get("Some unknown")).toBeUndefined();
    });
  });

  describe("Get keys operation", () => {
    it("Should get correct number of keys", () => {
      expect(hashTable.keys().length).toBe(20);
    });
  });

  describe("Get values operation", () => {
    it("Should get correct number of values", () => {
      expect(hashTable.values().length).toBe(20);
    });
  });
});

Time Complexity

Operation	Complexity
Insert	O(1)
Delete	O(1)
Access/Get	O(1)

Source Code

Use the following links to get the source code used in this article-

Source Code of	Implementation Code	Demo Code	Test Code
JavaScript Implementation	GitHub	GitHub	GitHub
TypeScript Implementation	GitHub	GitHub	GitHub

Related Data Structures

Command	Details
Binary Heap	Binary Heap

Other Code Implementations

Use the following links to check the BFS implementation in other programming languages-