Vibe Engines
YouTube

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

Algorithm · Data Structures

The Instant Lookup.

Watch the explainer

Don't memorize the hash table — watch it drop keys into buckets. A hash function turns each key into an array index, so lookups jump straight to the right slot in O(1). Then two keys land in the same bucket — a collision — and you see exactly why they chain, and why a full table slows down.

hash function · buckets · collisions · chaining · load factor
HASH FUNCTION

Turns a key into a bucket index — the same key always maps to the same slot.

BUCKET

One slot of the backing array. Ideally it holds just one entry.

COLLISION

Two keys hash to the same bucket. Unavoidable — so it must be handled.

LOAD FACTOR

Entries ÷ buckets. Too high and chains grow, so the table resizes.

hash-table.sim — insert 8 keys into 7 buckets
Ready

Seven empty buckets, eight keys to insert. Press Insert to hash the next key and drop it into its bucket — and watch what happens when two keys want the same slot.

hash(key) = (Σ char codes) mod 7
0
Inserted
0
Collisions
0.00
Load factor

Why lookups are instant

A plain array is fast if you know the index and slow if you have to search for a value. A hash table gives you the best of both: it computes the index from the key. Store “Guido”, and the hash function turns it into bucket 0; ask for “Guido” later, hash it again, get 0, and jump straight there. No scanning — that's the O(1).

01

Hash the key

Run the key through a hash function to get a number, then take it mod the bucket count to land inside the array.

02

Drop it in the bucket

Store the entry at that index. Insert, search and delete all start by hashing to the bucket — so all three are average O(1).

03

Handle collisions

When two keys share a bucket, keep a small list there (separate chaining). Lookups check that short list — still tiny, as long as the hash spreads keys evenly.

04

Resize before it's full

As the load factor climbs, chains lengthen. Past a threshold (~0.75) the table allocates a bigger array and rehashes everything, restoring short chains and O(1).

Search / Insert / Delete
O(1) avg
Worst case (all collide)
O(n)
Space
O(n)
Resize threshold
~0.75

The catch: a hash table has no order. Iterating it gives keys in bucket order, not sorted order — if you need sorted keys or range queries, reach for a balanced tree instead. And O(1) is an average: a bad hash function or an adversarial set of keys can pile everything into one bucket and drop you to O(n).

The picture: eight keys, seven buckets, uneven chains

0GuidoDennis12Alan3Ada45Linus6GraceKenBjarne bucket = (sum of character codes) mod 7 8 keys / 7 buckets = load factor 1.14; 2 buckets empty, 1 holds 3
The page’s eight keys inserted in order. Shaded entries are collisions: they landed in a bucket that already held something and were chained behind it. Bucket 6 collected three keys while buckets 1 and 4 stayed empty, which is what a hash function that looks random actually produces.

Worked example, step by step

The hash is sum of character codes mod 7, and the keys arrive in the order Ada, Alan, Grace, Linus, Guido, Ken, Dennis, Bjarne. Each insert computes the bucket, then appends to that bucket’s chain.

InsertChar-code sumSum mod 7Chain length afterOutcome
Ada26231empty bucket
Alan38021empty bucket
Grace48261empty bucket
Linus52351empty bucket
Guido50401empty bucket
Ken28662collision with Grace
Dennis60902collision with Guido
Bjarne59463collision with Grace, Ken

The first five keys each found an empty bucket; the next three did not. Pigeonhole made this unavoidable: once 8 keys go into 7 buckets, at least one bucket holds two. Now price a lookup. Finding a key costs one probe per entry up to and including it in its chain: Guido 1, Dennis 2, Alan 1, Ada 1, Linus 1, Grace 1, Ken 2, Bjarne 3. That is 12 probes for 8 keys, 1.5 on average. Still cheap, but Bjarne already costs three times what Ada does, and the cost grows with chain length, not with table size. A deletion is the same walk. This is also a poor hash: Alan and Anal have the same character sum, so every anagram of a word lands in the same bucket.

Complexity and trade-offs

CaseTimeSpaceWhy
Hash table, insert / lookup / deleteO(1) average, O(n) worstO(n)Average assumes a well-spread hash and a bounded load factor. All keys in one bucket is a linear scan.
Resize (rehash everything)O(n) once, amortized O(1) per insertO(n) extra while copyingDoubling the bucket array each time the load factor crosses its limit means n inserts cost about 2n rehashes in total.
Sorted array + binary searchO(log n) lookup, O(n) insertO(n)About 20 comparisons for a million keys, but supports order, ranges and nearest key.
Balanced tree (red-black, B-tree)O(log n)O(n)Slower than a hash on a single key, but sorted iteration and range scans come free.
Unsorted listO(n) lookup, O(1) appendO(n)Fine for a few dozen entries, where hashing overhead is more than the scan.

The hash table trades order for speed: you get the fastest average point lookup of the five, and lose “smallest key”, “next key” and “everything between a and b”. The load factor is the dial. At 0.75 (a common limit) chains average under one entry; at the page’s 1.14 they already average over one. Chaining degrades smoothly past 1.0, while open addressing, which probes for the next free slot, gets sharply worse as it approaches a full table.

Common mistakes

  • A hash that ignores order or structure

    Summing character codes, as this page does for clarity, sends all anagrams to one bucket: "listen" and "silent" collide always. Real hashes mix position in (multiply by a prime, rotate, xor) so that small input changes scatter widely.

  • Mutating a key after inserting it

    If a key’s hash depends on its contents and you change those contents, the entry sits in the old bucket while lookups go to the new one. It is silently unreachable. This is why Python refuses to hash a list (TypeError: unhashable type) and why Java map keys should be immutable.

  • Equal objects with different hashes

    Overriding equals without hashCode in Java breaks the contract that equal keys hash equally. Two “equal” objects land in different buckets, so map.get returns null for a key you just put.

  • Negative modulo

    In C, C++ and Java, hash % buckets can be negative when the hash is: −7 % 5 is −2, an invalid index. Mask the sign bit, use Math.floorMod, or work in unsigned arithmetic. Python’s % always returns a non-negative result for a positive modulus.

  • Never resizing

    A fixed 7 buckets is fine for 8 keys and hopeless for 1,000: chains average 143 entries, so every lookup is a linear scan with extra steps. Track the load factor on insert and rebuild with a larger array when it crosses the limit.

Where this shows up

  • Language built-ins

    Python’s dict and set, Java’s HashMap, JavaScript’s Map and Go’s map are hash tables. Since Java 8, a HashMap bucket that grows long converts its chain to a balanced tree once the table is large enough, capping the worst-case lookup.

  • Hash-flooding defences

    An attacker who knows the hash can send keys that all collide and turn each request into a linear scan. This was demonstrated against web frameworks in 2011, and Python 3.4 switched to the keyed SipHash function for strings in response.

  • Redis keyspace

    Redis stores its keys in a hash table and grows it with incremental rehashing: it keeps old and new tables side by side and migrates a few buckets per operation, so no single command pays the full O(n) resize.

  • Database hash joins and compilers

    A hash join builds a table on the smaller input and probes it with each row of the larger one. A compiler’s symbol table maps every identifier to its declaration the same way.

SOLVE IT YOURSELF

Solve it: first unique character

This one is yours to write — in Python or TypeScript, running for real in your browser. Edit the stub below, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.

YOUR TASK

Implement first_unique(s): return the index of the first character in the string that appears exactly once, or -1 if there is none. Count characters with a hash map, then scan once more — O(n), two passes.

HINTS — 4 IDEAS
  1. A hash map of char → count tells you, in O(1), how many times any character appears.
  2. First pass: walk the string and tally every character into the map.
  3. Second pass: walk again and return the index of the first character whose count is 1.
  4. If no character has a count of 1, return -1.
CPython · WebAssembly
▶  Watch it explained

Hash Table: Time and Space Complexity, From First Principles

Check yourself

1 · Why is a hash-table lookup O(1) on average?

Hashing the key gives the index straight away — you jump to the bucket instead of scanning, which is the whole point.

2 · What is a collision?

Because there are more possible keys than buckets, different keys sometimes map to the same slot — resolved by chaining or probing.

3 · What happens as the load factor gets too high?

More entries per bucket means longer chains and slower lookups, so the table grows its array and rehashes to bring the load factor back down.

Questions

Where are hash tables actually used?

Everywhere: Python dict/set, JavaScript Map/objects, Java HashMap, database indexes, caches, de-duplication, counting frequencies, and the two-sum interview classic. Any time you need “does this exist?” or “what's the value for this key?” fast, it's a hash table.

Chaining vs open addressing?

Chaining stores a list per bucket — simple and degrades gracefully. Open addressing keeps everything in the array and probes for the next free slot on a collision — more cache-friendly but needs careful deletion and a lower load factor. Both are widely used.

What makes a good hash function?

It spreads keys uniformly across buckets, is fast to compute, and is deterministic (same key → same bucket). Poor hashes that clump keys into a few buckets turn your O(1) table into an O(n) list.

You just built instant lookup.

Hash to a bucket, chain on collisions, resize before it fills. The structure behind every dictionary you've ever used.

Finished this one? 0 / 99 Algorithms done
NextSift Up, Sift Down: Heap & Priority Queue Next on the “The four containers” ladder · rung 4 of 4

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Algorithms