Building a HashMap
from scratch
No objects. No Map. Just an array of buckets, a hash function, and collision chaining. Add keys below and watch them slot into buckets in real time.
Insert, lookup, and watch collisions
Each key gets hashed to a bucket index (0–15). When two keys land in the same bucket, that's a collision — they chain together. Try the "Force collisions" preset to see it clearly.
HashMap vs Map vs Object
JavaScript gives you three key-value structures. They look similar but behave differently in ways that matter for interviews — and for production code.
| HashMap (ours) | Map | Object | |
|---|---|---|---|
| Key types | string / number / boolean | any (objects, functions, etc.) | string / Symbol |
| Insertion order | ✕ not preserved | ✓ preserved | ~mostly preserved |
| Size | .size — O(1) with counter | .size — O(1) | Object.keys().length — O(n) |
| Iteration | .keys() / .values() | for...of / .forEach() | for...in / Object.keys() |
| Performance | O(1) amortized | O(1) amortized | O(1) amortized |
| Prototype pollution | ✕ not possible | ✕ not possible | ⚠ possible |
| Serialization | manual | manual | JSON.stringify() |
| Default keys | none | none | toString, constructor, etc. |
Use Object for simple string-keyed config or JSON data. Use Map when you need non-string keys, guaranteed insertion order, frequent additions/deletions, or when you need .size without counting. Use Set when you only care about unique keys, not values — it's essentially a HashMap where value is always true.
"Are object property lookups O(1)?" — Yes, V8 uses hidden classes and inline caching for known shapes, making property access effectively constant time. But deleting properties with delete obj.key is slow because it forces a shape transition. For frequent add/delete patterns, use Map.
The full implementation
Generic, type-safe, with a prime-multiplier hash function and collision chaining. No built-in objects or Maps used internally — just arrays.
class HashMap<K extends string | number | boolean, V> {
private _buckets: [key: K, value: V][][];
private _size: number = 0;
constructor(private bucketCount: number = 16) {
this._buckets = Array.from({ length: bucketCount }, () => []);
}
hash(key: K): number {
let hash = 0;
const str = key.toString();
for (let i = 0; i < str.length; i++) {
hash = (hash * 31 + str.charCodeAt(i)) % this.bucketCount;
}
return hash; // key → number → bucket index
}
set(key: K, value: V) {
const bucketIndex = this.hash(key);
const bucket = this._buckets[bucketIndex];
const existing = bucket.findIndex((el) => el[0] === key);
if (existing >= 0) {
bucket[existing] = [key, value]; // update existing
} else {
bucket.push([key, value]); // insert new
this._size++;
}
}
get(key: K): V | undefined {
const bucketIndex = this.hash(key);
return this._buckets[bucketIndex].find((el) => el[0] === key)?.[1];
}
delete(key: K): boolean {
const bucketIndex = this.hash(key);
const bucket = this._buckets[bucketIndex];
const index = bucket.findIndex((el) => el[0] === key);
if (index === -1) return false;
bucket.splice(index, 1);
this._size--;
return true;
}
has(key: K): boolean {
const bucketIndex = this.hash(key);
return this._buckets[bucketIndex].some((el) => el[0] === key);
}
get size(): number { return this._size; }
keys(): K[] { return this._buckets.flat().map((el) => el[0]); }
values(): V[] { return this._buckets.flat().map((el) => el[1]); }
}