How does a hash table work

Short answer. A hash table runs a key through a hash function, takes the result modulo the array size and stores the value in that slot. A lookup repeats the same steps, so it takes constant time on average. Collisions are handled by chaining or open addressing, and the table doubles its array past a load factor of about 0.75.

The core move

Keep an array of some size, say 16 slots.

Run the key through a hash function. You get a number. Take it modulo 16.

You have a slot. Put the value in it.

Looking it up repeats those steps and lands in the same place.

No searching happened. That is where constant time comes from.

The hash function has one job. Spread keys evenly across slots.

The hash function always gives the same answer for the same key.

Collisions

Two keys will land in the same slot.

With 16 slots and 20 keys it is guaranteed. Long before that it is likely.

Two standard fixes handle key collisions.

Chaining. Each slot holds a small list. Collide, and you append.

Lookup finds the slot, then walks a list. Normally one or two items.

Open addressing. Slot taken? Try the next one. Keep going until one is free.

No lists. Better cache behaviour. More delicate deletion.

Both are still fast, as long as the lists stay short.

Load factor and resizing

The load factor keeps the lists short. It is entries divided by slots.

Past roughly 0.75, collisions get common and lookups slow down.

The table allocates a bigger array, usually double. Then it rehashes every key into it.

That resize is O(n). One unlucky insert pays for it.

Averaged over all inserts, the cost is still constant. That is the honest meaning of amortised time.

What constant time means is in Big O explained simply.

Constant time explains a production surprise too. An insert that usually takes a microsecond occasionally takes far longer.

That matters if you hold a lock while it happens.

Why the worst case is O(n)

If every key hashes to the same slot, the table becomes one long list. Every lookup scans it.

With random data this does not happen. With chosen data it does.

Chosen-key collisions have been used as a collision attack. Send a server thousands of keys that collide on purpose, and watch the CPU burn.

Modern runtimes now seed the hash function randomly per process.

Your interview answer stays "O(1) average, O(n) worst case". They are checking that you know it is an average.

Two rules that now make sense

Do not mutate a key after inserting it. The slot came from the old contents.

Change it, and the entry sits in the wrong place. It is unreachable rather than lost, which is worse.

Equal keys must hash equally. In languages where you write both, override equality and leave the hash alone, and the map starts losing entries.

The bug appears months later.

When to use something else

A hash table has no order. That is the trade, not an oversight.

"All keys between 10 and 50" is a full scan. So is "the smallest key". So is "everything in order".

Those want a balanced tree. Log n per operation, ordered by construction.

Databases keep both. Hash indexes for exact matches, B-trees for ranges.

Where this sits

AlgoPath spends steps 14 to 17 building one.

Collisions and resizing become code you wrote, not a paragraph you read.

When to reach for one at all is in set vs map vs array.

The pattern that runs on it is hash set and map.

The first 33 steps are free.