Implement a HashMap Algorithm
Every language gives you a built-in hash map. But building one from scratch teaches you what's actually happening under the hood — and why performance can...
10 Apr 2024
Every language gives you a built-in hash map. But building one from scratch teaches you what's actually happening under the hood — and why performance can vary so wildly.
What a HashMap Does
It stores key-value pairs. You give it a key, it returns the value. Average O(1) for get, set, and delete.
Under the hood: a hash function converts the key into an array index. The value goes into that slot. Collisions (two keys landing in the same slot) are handled by chaining — storing a list at each slot.
The Implementation
class HashMap {
constructor(size = 53) {
this.buckets = new Array(size);
this.size = size;
}
_hash(key) {
let hash = 0;
const prime = 31;
for (let i = 0; i < key.length; i++) {
hash = (hash * prime + key.charCodeAt(i)) % this.size;
}
return hash;
}
set(key, value) {
const index = this._hash(key);
if (!this.buckets[index]) {
this.buckets[index] = [];
}
const existing = this.buckets[index].find(([k]) => k === key);
if (existing) {
existing[1] = value;
} else {
this.buckets[index].push([key, value]);
}
}
get(key) {
const index = this._hash(key);
const bucket = this.buckets[index];
if (!bucket) return undefined;
const pair = bucket.find(([k]) => k === key);
return pair ? pair[1] : undefined;
}
delete(key) {
const index = this._hash(key);
const bucket = this.buckets[index];
if (!bucket) return false;
const i = bucket.findIndex(([k]) => k === key);
if (i === -1) return false;
bucket.splice(i, 1);
return true;
}
keys() {
const result = [];
for (const bucket of this.buckets) {
if (bucket) {
for (const [key] of bucket) {
result.push(key);
}
}
}
return result;
}
}
const map = new HashMap();
map.set("name", "Ehsan");
map.set("role", "engineer");
map.set("lang", "TypeScript");
console.log(map.get("name")); // "Ehsan"
console.log(map.get("role")); // "engineer"
map.delete("lang");
console.log(map.keys()); // ["name", "role"]Complexity
| Operation | Average | Worst |
|---|---|---|
| get | O(1) | O(n) |
| set | O(1) | O(n) |
| delete | O(1) | O(n) |
Worst case happens when all keys hash to the same bucket. A good hash function and proper table sizing prevent this.
What's Missing
A production hash map also handles:
- Resizing — when the load factor (items / buckets) gets too high, double the bucket array and rehash everything. This keeps chains short.
- Better hashing — the simple polynomial hash works for strings but a production implementation uses more sophisticated algorithms.
- Non-string keys — you'd need a way to hash numbers, objects, etc.
The Trade-off
Hash maps are the go-to for fast lookups by key. But they use more memory than arrays, don't maintain insertion order (though JavaScript's Map does), and can't do range queries. If you need sorted access, use a balanced BST instead.