Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Data structures

Hash Table Visualiser

Turn a key into a bucket number and look in that one bucket.

Operations

A hash table turns a key into a bucket number, so a lookup goes straight to one of 8 short lists instead of searching all the keys.

Keys stored
0
Buckets sharing
0
Pairs examined
0
Operations run
0
class HashTable {
constructor(size = 8) {
this.buckets = Array.from({ length: size }, () => []);
}
hash(key) {
let h = 0;
for (const ch of key) {
h = h * 31 + ch.charCodeAt(0);
}
return h % this.buckets.length;
}
set(key, value) {
const bucket = this.buckets[this.hash(key)];
const pair = bucket.find((p) => p[0] === key);
if (pair) pair[1] = value;
else bucket.push([key, value]);
}
get(key) {
const bucket = this.buckets[this.hash(key)];
const pair = bucket.find((p) => p[0] === key);
return pair ? pair[1] : undefined;
}
delete(key) {
const bucket = this.buckets[this.hash(key)];
const index = bucket.findIndex((p) => p[0] === key);
if (index === -1) return false;
bucket.splice(index, 1);
return true;
}
}

The highlighted line is the one that produced the picture on the left.

What Hash Table does

A hash table turns a key into a number, and uses that number as an address. Because the address is computed rather than searched for, a lookup goes straight to one short list of pairs no matter how many keys are stored — which is what makes Map, Set and plain objects feel instant.

How it works, step by step

  1. Hash the key: combine its character codes into a number, then take the remainder by the number of buckets.
  2. Go to that bucket and compare keys within it. Two different keys can land in the same bucket — that is a collision, and it is normal.
  3. set replaces the value if the key is already there, and appends the pair if it is not.
  4. get and delete do the same lookup and then read or splice out the pair.

What to watch for

  • "dog" and "owl" both land in bucket 4. The table is not broken: a collision costs one extra comparison, nothing more.
  • The pairs-examined counter stays at one or two however many keys are stored. That flatness is the O(1) average.
  • Keep adding keys and the buckets fill up. If every key landed in one bucket, a lookup would be a linear scan — which is the O(n) worst case, and why real tables grow and rehash as they fill.
  • The hash is deterministic: the same key always gives the same bucket, which is the only reason a lookup can find what a set put there.

Cost

setO(1) average, O(n) worst
getO(1) average, O(n) worst
deleteO(1) average, O(n) worst
Extra spaceO(n)
Keeps orderNot by key; JavaScript Map keeps insertion order

When to reach for it

Whenever you look things up by key, count occurrences, or need to ask “have I seen this before?”. It is the structure behind nearly every “use a hash map to make it O(n)” answer in interview problems.

Read more