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.
Step #1: Hash Table Class
Here is how the stored data would look like when stored in 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.
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.
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
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
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
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
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-