AlgoDaily 09: Implement a Hash Map

“Can you implement the JS Map class from scratch? Only two methods are necessary – get and set. Do not use JS Objects ({} notation) for this exercise.

For the two methods you’ll define:

get(key: string) should be given a key, and return the value for that key.

set(key: string, val: string) should take a key and a value as parameters, and store the pair.

Additionally, we’ve supplied the below hashing function hashStr. It tries to avoid collision, but is not perfect. It takes in a string value and returns an integer.”

We can implement this with an underlying array, and determine the positions of keys using the hash function.

As we’ve been given the hash function, the only difficulty is dealing with collisions.

One way to handle the collisions is to store an array of tuples at each position in the overall array. Each tuple is a pair of the original string key and the value. Then when retrieving a given key, we iterate through those tuples to find the one with the matching key.

Overall this means the worst-case running time for get can in theory still be O(n) if we’re iterating over all the keys at a position, which is no better than just using an array. In practice, though, the average running time should be O(1) as collisions are rare so we won’t need to iterate.

There are other caveats. This implementation doesn’t deal with duplicate set calls, and lets the first set win as later tuples in the array at that position with the same key won’t be reached. This could waste space with duplicate keys and values, and also lose data if client code attempts to change the value for a previously set key.

class HashMap {
	constructor() {
		this.content = [];
	}

	set(key, value) {
		const index = this.hashStr(key);
		if (!this.content[index]) {
			this.content[index] = [];
		}
		this.content[index].push([key, value]);
	}

	get(key) {
		const index = this.hashStr(key);
		if (!this.content[index]) {
			return undefined;
		}
		for (let keyValue of this.content[index]) {
			if (keyValue[0] === key) {
				return keyValue[1];
			}
		}
		return undefined;
	}

	hashStr(str) {
		let finalHash = 0;
		for (let i = 0; i < str.length; i++) {
			const charCode = str.charCodeAt(i);
			finalHash += charCode;
		}
		return finalHash;
	}
}

This is pretty much exactly the solution suggested by AlgoDaily.

Tech mentioned

• JavaScript