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.

Hash Table
Hash Table

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-

Step #1: Hash Table Class

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

Hash Table data stored in Array
Hash Table data 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.
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.
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.
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.
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.
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.
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-

// 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-

// 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’.

// 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

OperationComplexity
InsertO(1)
DeleteO(1)
Access/GetO(1)

Source Code

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

Related Data Structures

CommandDetails
Binary Heap Binary Heap

Other Code Implementations

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

Leave a Comment


The reCAPTCHA verification period has expired. Please reload the page.