Data Structure: Hash Table

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.

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

JavaScript
TypeScript

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

Step #3: Set data in the Hash Table

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

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

Step #4: Get data from the Hash Table

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

Step #5: Get all Keys

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

JavaScript
TypeScript

Step #6: Get all Values

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

JavaScript
TypeScript

Full Source Code

Here is the full source code of Hash Table implementation-

JavaScript
TypeScript

Demo

Use the following code to check the implementation-

JavaScript
TypeScript

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

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-