Chaining — linked lists in buckets, load factor, resizing: Question bank

Definition Symbols used on this page (read first — nothing below uses a letter not defined here)

Before any trap, pin down every letter the traps lean on:

$n$ = the number of keys currently stored in the table.
$m$ = the number of buckets (the length of the array of head pointers).
$α = \frac{n}{m}$ = the load factor, the average number of keys per bucket. Small $α$ = short chains = fast; large $α$ = long chains = slow. This is the single knob the whole topic turns on.
$h$ = the hash function, a rule that takes a key $k$ and spits out a bucket index $h (k) \in {0, 1, \dots, m - 1}$ . It's "which box does this letter belong in?" made into arithmetic (e.g. $h (k) = k mod m$ ). See Hash Functions.
$U$ = the universe of keys, the set of all possible keys the table might ever be asked to store (e.g. every possible string, or every 64-bit integer). It is almost always astronomically larger than $m$ : $∣ U ∣ ≫ m$ .
$m^{'}$ = the new bucket count after a resize. When we double, $m^{'} = 2 m$ ; every key is re-placed with $h (k) mod m^{'}$ .
Simple Uniform Hashing (SUH) = the modelling ==assumption that $h$ scatters keys evenly==: each key is equally likely to land in any of the $m$ buckets, independently of the others. Under SUH the expected chain length works out to exactly $α$ . A real hash only approximates this; a bad one breaks it.

This bank targets the four misconception zones the parent note raised — worst case vs expected, the load factor knob, resizing math, and the $α \leq 1$ myth — plus the boundary cases (empty table, single bucket, $α = 0$ , adversarial hash) that the parent only hinted at.

The picture behind every trap

Everything below circles back to two facts, so anchor them visually first.

Figure — Chaining — linked lists in buckets, load factor, resizing

Intuition How to read Figure s01

Left panel — how SUH distributes keys. The four pastel cells are the buckets $T [0] \dots T [3]$ . Each white node hanging off a cell is a stored key; the arrows are the linked-list pointers of a chain. Notice the coral bucket $T [1]$ holds a chain of three ( $13 \to 9 \to 5$ ) while $T [0]$ and $T [3]$ are empty — under SUH keys are expected to spread with average chain length $α = n / m$ , but on any given day one bucket can be tall and others empty. That gap between "expected $α$ " and "the unluckiest bucket" is what the worst-case traps exploit. Right panel — why doubling is cheap. Each lavender bar is one resize, labelled by the array size copied ( $2^{0}, 2^{1}, \dots$ ). The bars grow, but the total height (the coral annotation) collapses to $2 n - 1 < 2 n$ — the geometric sum derived just below. That single fact is the whole "amortized $O (1)$ " story.

The doubling sum, spelled out

True or false — justify

Every prompt below is a claim. Decide true/false, then give the why.

A chained hash table guarantees

O (1)

lookup in the worst case.

False.

O (1)

is the expected cost under simple uniform hashing (SUH); if every key collides into one bucket the chain has length

n

, so worst-case lookup is

O (n)

If the load factor

α

2

, the hash table is "full" and must reject inserts.

False. That's Open Addressing thinking. Chaining has no "full" —

α = 2

just means buckets average two items; it slows gracefully, it does not break.

Doubling

m

and adding a fixed

100

slots per resize both give amortized

O (1)

insert.

False. Only multiplicative growth works: doubling makes resizes exponentially rare, so the copy work is the geometric

\sum 2^{i} = 2 n

. Adding a constant forces a resize every

100

inserts, giving

Θ (n^{2})

total, i.e.

Θ (n)

per insert.

Choosing a very large

m

up front makes every operation strictly better.

False. Tiny

α

is fast but wastes

O (m)

memory and destroys cache locality; a mostly-empty array thrashes memory. You want

α

near a constant, not near zero.

Under simple uniform hashing, the expected length of any fixed bucket equals

α

True. SUH makes each of the

n

keys land in that bucket with probability

1/ m

independently, so the expected count is

n \cdot \frac{1}{m} = \frac{n}{m} = α

Insert into a chain is

O (1)

only if we prepend at the head.

True (with a caveat). Prepending to the head is

O (1)

; but if we must reject duplicates we first scan the chain, making it

O (1 + α)

. Cheap insert assumes we skip the duplicate check.

Rehashing during a resize reuses each key's old bucket index.

False. The bucket index becomes

h (k) mod m^{'}

with the new count

m^{'}

, so almost every key can move. That recomputation is exactly what splits long chains apart (left panel of Figure s01: a tall coral chain would scatter across the doubled array).

If the hash function

h

is perfect for the current keys, resizing is never needed.

False. Even a perfect

h

spreads

n

keys over

m

slots; once

n

grows past

m

α > 1

and chains lengthen regardless of hash quality. You still resize to keep

α

bounded.

Successful and unsuccessful searches have the same asymptotic cost.

True. Unsuccessful scans the whole chain (

1 + α

); successful stops at the target — on average about halfway, giving

1 + \frac{α}{2} - \frac{α}{2 n}

. Both are

O (1 + α)

; only the constant differs. (The correction term is derived in the "Why questions" section.)

The pigeonhole principle proves that some collision is unavoidable when

∣ U ∣ > m

True. With more possible keys in the universe

U

than slots

m

, at least two keys must map to the same slot — no hash function can dodge this, which is why chaining exists. See Pigeonhole Principle.

Spot the error

Each line contains a flawed statement. Name the flaw.

"Chaining has no collisions because each bucket is a separate list."

The list is the collision handler — items sharing a bucket already collided. Chaining doesn't prevent collisions; it stores them in the chain.

"Since insert is

O (1)

and delete is

O (1)

, chaining is fully

O (1)

Delete is

O (1)

only after you find the node; finding it is a search costing

O (1 + α)

. Delete is

O (1 + α)

expected, not

O (1)

"We resize whenever

α

exceeds

0.75

, so

α

can never go above

0.75

α

momentarily exceeds the threshold on the insert that triggers the resize; the resize then pulls it back down. The threshold is a trigger, not a hard ceiling maintained every instant.

"Total resize work is

1 + 2 + 3 + \dots + n = Θ (n)

That series is

Θ (n^{2})

— it's the adding-a-constant cost. Doubling gives the geometric series

1 + 2 + 4 + \dots + n = 2 n - 1 = Θ (n)

. The student mixed up arithmetic and geometric sums.

"With a bad hash, average cost is still

O (1 + α)

The

O (1 + α)

bound assumes simple uniform hashing. A bad

h

violates that assumption; it can pile keys into one chain, giving

O (n)

even on average. See Hash Functions.

"Chaining wastes no memory because lists only grow as needed."

The array of

m

head pointers is allocated regardless of how many keys exist, and every node carries pointer overhead. Chaining trades extra pointer memory for graceful degradation.

"Because we double

m

, a single insert can be

O (1)

worst case."

The insert that triggers a resize does

Θ (m)

rehashing work — its worst-case single cost is

O (n)

. Only the amortized cost over many inserts is

O (1)

; see Amortized Analysis.

Why questions

Answer the "why", not just the "what".

Why is chaining's cost written as

O (1 + α)

rather than just

O (α)

The "

1

" covers "always compute

h (k)

and touch one bucket" — this work happens even when the bucket is empty (

α \to 0

). Dropping it would wrongly say an empty-table lookup costs

0

Why does the successful search carry the extra

- α / (2 n)

term?

Averaging over all

n

stored keys, the

i

-th inserted key sits after on average

(i - 1) / m

keys in its chain; averaging

1 + (i - 1) / m

over

i = 1.. n

gives

1 + \frac{n - 1}{2 m} = 1 + \frac{α}{2} - \frac{α}{2 n}

. The tiny

- α / (2 n)

just corrects for the first key having no predecessors.

Why do we double

m

instead of tripling or adding a constant?

Any constant multiplier

> 1

(double, triple) gives a geometric series and

O (1)

amortized (the

\sum 2^{i} = 2 n - 1

collapse above); the specific choice trades memory slack against resize frequency. Adding a constant is the one thing that fails — it gives

Θ (n^{2})

Why does chaining tolerate

α > 1

while open addressing cannot?

Chaining stores keys outside the array in growable lists, so a bucket can hold unlimited items. Open addressing stores keys inside the array's slots, so once slots run out (

α = 1

) there is nowhere to probe.

Why does resizing "flatten" long chains?

The new count

m^{'}

redistributes keys across twice as many buckets via

h (k) mod m^{'}

, so keys that shared a slot under

m

often split into different slots under

m^{'}

. Longer array, shorter average chain — the left panel of Figure s01 shows the tall coral chain that resizing would break apart.

Why is the "simple uniform hashing" assumption necessary for the

O (1 + α)

claim?

SUH guarantees each key spreads independently and evenly, so expected chain length equals

α

. Without it, a hash

h

could correlate keys into one bucket and the expectation argument collapses.

Why is the longest chain

Θ (lo g n / lo g lo g n)

(not

α

) when

α

is a constant?

Throwing

n

keys into

n

bins, the chance a fixed bin gets

\geq k

keys is roughly

(k n) (1/ n)^{k} \leq 1/ k!

; setting

1/ k! \approx 1/ n

and using

k! \approx (k / e)^{k}

solves to

k \approx lo g n / lo g lo g n

. So expected chain is

α

, but the unluckiest bucket is a bit taller.

Why might a smaller

α

still hurt real-world speed despite fewer comparisons?

A sparse, large array has poor cache locality — the CPU fetches mostly-empty cache lines. Fewer comparisons on paper can lose to more cache misses in practice.

Why do we say resizing is

O (1)

amortized rather than average?

Amortized is a worst-case guarantee spread over a sequence — every

n

-insert run costs

\leq 2 n

total, no probability involved. "Average" would depend on randomness; amortization is deterministic accounting. See Amortized Analysis and the same trick in Dynamic Arrays.

Edge cases

The boundaries the topic quietly invites.

What is the expected search cost when the table is empty (

n = 0

, so

α = 0

O (1 + 0) = O (1)

: you still compute

h (k)

and check one (empty) bucket. The "

1

" is exactly why an empty lookup isn't free-but-zero.

With a single bucket (

m = 1

), what does chaining degenerate into?

Every key hashes to bucket

0

, so the table becomes one long linked list — search is

O (n)

. This is the worst-case collision scenario made structural.

An adversary knows your hash function

h

and feeds keys that all map to one slot — what happens and what's the fix?

All

n

keys form one chain, so every operation degrades to

O (n)

. The fix is a randomized hash chosen at runtime so the adversary cannot predict the target slot.

If you insert then immediately delete the same key repeatedly at the resize threshold, do you thrash resizes?

No — grow at

α > 0.75

but only shrink at a much lower threshold like

α < 0.25

. This gap (hysteresis) means a single insert/delete pair never crosses both boundaries, so you cannot oscillate resize/un-resize.

What exactly is the "lower threshold" that prevents shrink-thrashing, and why that value?

Shrink when

α

falls below, say,

0.25

(grow at

0.75

). Because grow-boundary and shrink-boundary are far apart, after either resize

α

lands safely in the middle (

\approx 0.375

–

0.5

), so many operations must pass before the next resize — total work stays amortized

O (1)

What is the load factor right after allocating a fresh table of

m

buckets with no keys?

α = 0/ m = 0

. The array of

m

head pointers exists but every chain is empty — memory allocated, zero keys stored.

Can the worst-case chain length exceed

α

badly even under uniform hashing?

Yes — expectation is

α

, but by chance one bucket can hold far more (the longest chain is about

Θ (lo g n / lo g lo g n)

when

α

is constant, from the balls-into-bins bound above). Expected-short does not mean uniformly-short.

h (k)

returns the same value for two equal keys but we allow duplicates, what does search return?

Both copies sit in the same chain; search finds the first match it reaches. Allowing duplicates means you may store and later find multiple identical entries.

Connections

Parent — the source topic these traps are built from.
Open Addressing — where the $α \leq 1$ rule actually applies.
Amortized Analysis — the deterministic accounting behind "amortized $O (1)$ ".
Dynamic Arrays — same doubling trap and fix.
Hash Functions — the quality of $h$ that makes uniform hashing hold.
Pigeonhole Principle — why collisions are unavoidable when $∣ U ∣ > m$ .
Linked Lists — what a bucket degenerates into.