Data structures
Hash Table Visualiser
Turn a key into a bucket number and look in that one bucket.
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
- Hash the key: combine its character codes into a number, then take the remainder by the number of buckets.
- 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.
- set replaces the value if the key is already there, and appends the pair if it is not.
- 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
| set | O(1) average, O(n) worst |
|---|---|
| get | O(1) average, O(n) worst |
| delete | O(1) average, O(n) worst |
| Extra space | O(n) |
| Keeps order | Not 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.