Implement a Hash Table in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital I write about tech topics and teach…

Implement a Hash Table in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital I write about tech topics and teach engineers to have solid foundations that will help them get ahead in their career. I also build awesome products for digital nomads — check it out!

JavaScript eBook

I’ve written an eBook on JavaScript that will take you from beginner to professional. Having been in your shoes moving to making over $200,000 per year in just a few years as a software engineer, I know exactly what it takes to get there. Check out the ebook now!

A hash table, also known as a hash map, is a data structure that stores key-value pairs in an efficient manner. It uses a hashing function to map keys to indices in an array, allowing for fast insertion and retrieval of data.

In JavaScript, the built-in Map object serves as a hash table. It has a set() method to add a new key-value pair and a get() method to retrieve a value based on its key. It also has a has() method to check if a key exists in the map and a delete() method to remove a key-value pair.

One advantage of using a hash table over other data structures such as an array or object is its constant time performance for insertion and retrieval. This means that the time it takes to perform these operations does not depend on the size of the data set, making it efficient for large data sets.

However, there are some trade-offs to consider when using a hash table. One is the potential for collisions, which occur when two keys hash to the same index in the array. This can be mitigated by using a larger array or a more sophisticated hashing function.

Another consideration is the cost of resizing the hash table when it becomes too full. This requires rehashing all the keys and can be a time-consuming process.

Here is a basic implementation of a hash table in JavaScript:

class HashTable {
this.keyMap = new Array(size);
}
let total = 0;
let WEIRD_PRIME = 31;
for (let i = 0; i < Math.min(key.length, 100); i++) {
let char = key[i];
let value = char.charCodeAt(0) - 96;
total = (total * WEIRD_PRIME + value) % this.keyMap.length;
}
 
 
return total;
}
set(key, value) {
let index = this._hash(key);
if (!this.keyMap[index]) {
 
this.keyMap[index].push([key, value]);
}
get(key) {
let index = this._hash(key);
if (this.keyMap[index]) {
for (let i = 0; i < this.keyMap[index].length; i++) {
if (this.keyMap[index][i][0] === key) {
return this.keyMap[index][i][1];
}
}
}
return undefined;
}
keys() {
let keysArr = [];
for (let i = 0; i < this.keyMap.length; i++) {
if (this.keyMap[i]) {
for (let j = 0; j < this.keyMap[i].length; j++) {
if (!keysArr.includes(this.keyMap[i][j][0])) {
keysArr.push(this.keyMap[i][j][0])
}
}
}
}
return keysArr;
}
values() {
let valuesArr = [];
for (let i = 0; i < this.keyMap.length; i++) {
if (this.keyMap[i]) {
for (let j = 0; j < this.keyMap[i].length; j++) {
if (!valuesArr.includes(this.keyMap[i][j][1])) {
valuesArr.push(this.keyMap[i][j][1])
}
}
}
}
return valuesArr;
}


This implementation includes the following methods:

constructor(size): Initializes a new hash table with a given size. The default size is 53. - _hash(key): Hashes a given key and returns an integer representing the index at which the key/value pair should be stored in the keyMap array. - set(key, value): Stores a key/value pair in the hash table. - get(key): Returns the value associated with a given key, or undefined if the key is not found in the hash table. - keys(): Returns an array of all keys in the hash table. - values(): Returns an array of all values in the hash table.

Overall, the hash table is a useful data structure for efficient insertion and retrieval of key-value pairs in JavaScript. It is particularly useful for large data sets and has the added benefit of being part of the built-in Map object in the language.

JavaScript eBook

I founded Higglo Digital and we can help your business crush the web game with an award-winning website and cutting-edge digital strategy. If you want to see a beautifully designed website, check us out.

I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!

class HashTable { this.keyMap = new Array(size); } let total = 0; let WEIRD_PRIME = 31; for (let i = 0; i < Math.min(key.length, 100); i++) { let char = key[i]; let value = char.charCodeAt(0) - 96; total = (total * WEIRD_PRIME + value) % this.keyMap.length; } return total; } set(key, value) { let index = this._hash(key); if (!this.keyMap[index]) { this.keyMap[index].push([key, value]); } get(key) { let index = this._hash(key); if (this.keyMap[index]) { for (let i = 0; i < this.keyMap[index].length; i++) { if (this.keyMap[index][i][0] === key) { return this.keyMap[index][i][1]; } } } return undefined; } keys() { let keysArr = []; for (let i = 0; i < this.keyMap.length; i++) { if (this.keyMap[i]) { for (let j = 0; j < this.keyMap[i].length; j++) { if (!keysArr.includes(this.keyMap[i][j][0])) { keysArr.push(this.keyMap[i][j][0]) } } } } return keysArr; } values() { let valuesArr = []; for (let i = 0; i < this.keyMap.length; i++) { if (this.keyMap[i]) { for (let j = 0; j < this.keyMap[i].length; j++) { if (!valuesArr.includes(this.keyMap[i][j][1])) { valuesArr.push(this.keyMap[i][j][1]) } } } } return valuesArr; }