loading
loading
loading
loading
Key → value lookup in O(1) average time, by turning keys into array indexes with a hash function.
A hash table runs each key through a hash function to pick a bucket in an underlying array, giving O(1) average insert, lookup, and delete. Two keys can land in the same bucket — a collision — handled by chaining (a small list per bucket) or open addressing (probe for the next free slot). Keeping the load factor low and resizing when it grows is what keeps operations fast.
Step through hash tables live, one move at a time — this becomes a fully interactive visualizer.
Coming soonindex = hash(key) % capacity.function firstUnique(s) {
const counts = new Map(); // hash table
for (const ch of s) {
counts.set(ch, (counts.get(ch) ?? 0) + 1);
}
for (const ch of s) {
if (counts.get(ch) === 1) return ch;
}
return null;
}
// Two O(n) passes instead of the O(n²)
// compare-every-pair approach.When you need ordering: range queries ('all keys between A and M'), sorted iteration, or nearest-key lookups. A balanced BST gives those in O(log n); a hash table can't do them at all without a full scan.
The bucket is chosen from the key's hash at insert time. If the key mutates afterward, its hash changes and the entry is stranded in the wrong bucket — lookups will miss it.
Chaining is simpler and tolerates high load factors; open addressing (e.g. linear probing) has better cache behavior and no per-node allocation but degrades sharply as the table fills. Most standard libraries pick one and tune it heavily.
Share what clicked for you and see notes from other learners on this topic.
Coming soon