Why would you want to create a hash table in JavaScript / TypeScript? You wouldn't. So don't. So then why am I teaching you how to write one then, other than to add content? Really just so you know how they work so you can better your programming knowledge, understanding, and technical skills. Perhaps you can use parts of this in some other project. Look I don't know you, you do what you want. JavaScript

What's a Hash Table Anyway?

Before we mosey on down to the implementation path, let's chitchat a bit about what a hash table is. It's a data structure that allows you to store and retrieve values based on a key. Think of it like a magical bookshelf (yep, the one from Narnia) where you put in a book with a unique title and the shelf tells you exactly where to find it. Neat, huh?

Why Bother with a Hash Table?

O91) Access: When you've got thousands, heck, millions of items to sift through, a hash table can get the value in constant time.
Unique Keys: Every item's got its own spot. No two items can claim the same space.

Let's Code!

Alright, now to the meat and potatoes. TypeScript, that snazzy superset of JavaScript, will be our tool of choice today.

Setting the Stage

Before diving in, remember - a good coder is like a good chef. You gotta prep before you cook.


class HashTable {
    constructor(size: number) {
        this.table = new Array(size)
        this.size = size 
    }
    private table: any[]
    private size: number
}

We've got our HashTable class with a generic type for keys (K) and values (V). The items object will store our key-value pairs. The count keeps track of the number of items, and capacity is the maximum number of items our table can hold.

The Magic of Hashing

The heart and soul of our hash table is the hashing function. It turns our key into a string that points to a specific spot in our table.


private hash(key: K): string {
    return key.toString().split('').reduce((acc, char) => acc + char.charCodeAt(0), 0) % this.size;
}

This simplistic hashing function converts our key into a string and then sums up the character codes. The modulus (%) operation ensures we don't overshoot our table's capacity.

Storing and Retrieving Like a Pro

With our hash function in tow, let's add the methods to add items and fetch 'em back.


public set(key: string, value: any) {
	const index = this.hash(key)

	const bucket = this.table[index]
	if (!bucket) {
		this.table[index] = [[key, value]]
		return
	} else {
		const sameKeyItem = bucket.find((item: any) => item[0] === key)
		if (sameKeyItem) {
			sameKeyItem[1] = value
			return
		} else {
			bucket.push([key, value])
			return
		}
	}
}

public get(key: string) {
	const index = this.hash(key)

	const bucket = this.table[index]
	if (bucket) {
		const sameKeyItem = bucket.find((item: any) => item[0] === key)
		if (sameKeyItem) {
			return sameKeyItem[1]
		}
	}
	return undefined
}

We can now store and fetch items with ease. Now we will create some methods to show the keys and values:


public keys() {
	const keysArray = []
	for (let i = 0; i < this.table.length; i++) {
		if (this.table[i]) {
			keysArray.push(i)
		}
	}
	return keysArray
}

public values() {
	const valuesArray = []
	for (let i = 0; i < this.table.length; i++) {
		if (this.table[i]) {
			valuesArray.push(this.table[i])
		}
	}
	return valuesArray
}

Now if you `console.log(myHashTable.keys())` or `console.log(myHashTable.values())`, you will get either the keys or values respectively.

Tt'd also be pretty handy to have a display function that will log the keys and values together.


    public display() {
		for (let i = 0; i < this.table.length; i++) {
			if (this.table[i]) {
				console.log(i, ":", this.table[i])
			}
		}
	

public hasKey(key: K): boolean {
    const hashedKey = this.hash(key);
    return this.table.hasOwnProperty(hashedKey);
}

We should also add the ability to remove keys as well:


public remove(key: string) {
	const index = this.hash(key)
	const bucket = this.table[index]
	if (bucket) {
		const sameKeyItem = bucket.find((item: any) => item[0] === key)
		if (sameKeyItem) {
			bucket.splice(bucket.indexOf(sameKeyItem), 1)
			return sameKeyItem[1]
		}
	}
}

Putting it all Together


class HashTable {
	constructor(size: number) {
		this.table = new Array(size)
		this.size = size
	}

	table: any[]
	size: number

	hash(key: string) {
		let total = 0
		for (let i = 0; i < key.length; i++) {
			total += key.charCodeAt(i)
		}

		return total % this.size
	}

	public set(key: string, value: any) {
		const index = this.hash(key)

		const bucket = this.table[index]
		if (!bucket) {
			this.table[index] = [[key, value]]
			return
		} else {
			const sameKeyItem = bucket.find((item: any) => item[0] === key)
			if (sameKeyItem) {
				sameKeyItem[1] = value
				return
			} else {
				bucket.push([key, value])
				return
			}
		}
	}

	public get(key: string) {
		const index = this.hash(key)

		const bucket = this.table[index]
		if (bucket) {
			const sameKeyItem = bucket.find((item: any) => item[0] === key)
			if (sameKeyItem) {
				return sameKeyItem[1]
			}
		}
		return undefined
	}

	public remove(key: string) {
		const index = this.hash(key)
		const bucket = this.table[index]
		if (bucket) {
			const sameKeyItem = bucket.find((item: any) => item[0] === key)
			if (sameKeyItem) {
				bucket.splice(bucket.indexOf(sameKeyItem), 1)
				return sameKeyItem[1]
			}
		}
	}

	public display() {
		for (let i = 0; i < this.table.length; i++) {
			if (this.table[i]) {
				console.log(i, ":", this.table[i])
			}
		}
	}

	public keys() {
		const keysArray = []
		for (let i = 0; i < this.table.length; i++) {
			if (this.table[i]) {
				keysArray.push(i)
			}
		}
		return keysArray
	}

	public values() {
		const valuesArray = []
		for (let i = 0; i < this.table.length; i++) {
			if (this.table[i]) {
				valuesArray.push(this.table[i])
			}
		}
		return valuesArray
	}
}

Wrapping Up

Now that you've learned how to make a Hash Table in TypeScript, you can now never use it! Good for us. Instead use map, or objects. Or take your knowledge and use it in a language that needs it.

Data Structures - Hash Table in TypeScript