Question bank — Load factor — when to resize, rehashing cost

False. In chaining $\alpha$ is the average chain length and can happily exceed 1; only open addressing is capped at $\alpha <1$ because each slot holds at most one key.

True. $\alpha =n/m$; if $n$ stays fixed and $m\to 2m$, then $\alpha \to \alpha /2$. That instant drop is exactly why one rehash buys many future cheap inserts.

False (see Figure 3). The bucket index is $h(k)\mathrm{mod}m$; when $m$ changes to the new count $m^{\prime }$, $h(k)\mathrm{mod}{m}^{\prime }$ generally differs, so every key must be re-placed. Copying by index would scatter keys to wrong buckets.

False. The rehash insert is $\Theta (n)$ — genuinely slow. Amortized $O(1)$ means the average over a sequence is constant; individual inserts can spike. See Amortized Analysis.

False (see Figure 1). Additive growth rehashes every 100 inserts, and total move work is $100+200+\cdots \approx n^2/200=\Theta (n^2)$, i.e. amortized $O(n)$. Only multiplicative growth gives $O(1)$.

False. Even with zero collisions, high $\alpha$ in open addressing means fewer empty slots to land in, and in chaining it costs memory patterns/cache misses. $\alpha$ controls occupancy independent of collision quality. See Hash Functions.

False. With grow and shrink thresholds nearly touching, a single insert/delete can bounce across both, triggering repeated $\Theta (n)$ resizes — thrashing. You need a gap (hysteresis), e.g. grow at 0.75, shrink at 0.25.

False (see Figure 2 and Figure 4). That bound comes from open addressing, where consecutive full slots form a probe cluster: a search must step past every full slot in the run before it finds an empty one. Chaining has no such run — each bucket owns its own list — so its expected cost is the gentle $O(1+\alpha )$, not the exploding $1/(1-\alpha )$.

False. Amortized $O(1)$ still pays $\approx 2n$ total move work over a bulk load; pre-sizing to fit all keys avoids every mid-load rehash, a real constant-factor win. See Dynamic Arrays.

Error: it's a geometric sum, not $n$ terms of size $\sim n$. $1+2+4+\cdots +n=2n-1$, which is $\Theta (n)$, not $\Theta (n\log n)$.

Error (see Figure 2): at $\alpha =0.99$ the expected unsuccessful probes are $1/(1-0.99)=100$. 'Finite' is not 'fast'; the cliff makes 0.7 the practical threshold.

Error: rehashes get exponentially rarer as the table doubles, so their total is $\le 2n$, not $n$ rehashes of size $n$. Total insert cost is $\Theta (n)$, amortized $O(1)$.

Error: deletes only lower $\alpha$, which makes lookups faster, not slower. Rehash on delete only when $\alpha$ falls below a shrink threshold, and even then respect hysteresis.

Error (see Figure 4): a plain empty would break the probe chain for other keys that passed through that slot. You need a tombstone (deleted marker), which also inflates effective $\alpha$ until a rehash clears them.

Error: it only holds for the current $n$. Keep inserting and $n$ grows past that $m$, so $\alpha$ climbs again and a resize is still needed. Pre-sizing delays, not eliminates, resizing.

(See Figure 2.) Chaining cost grows linearly as $1+\alpha$, gentle even past 1; open addressing cost is $1/(1-\alpha )$, which explodes as $\alpha \to 1$.

(See Figure 1.) Doubling means each rehash moves twice the previous one, so the sum is dominated by the last term ($\approx 2n$); additive growth makes each rehash bigger by only a fixed step, giving an arithmetic series that sums to $\Theta (n^2)$.

Each of $n$ keys lands in your bucket with probability $1/m$ independently, so the expected count sharing it is $n\cdot (1/m)=n/m=\alpha$.

(See Figure 3.) Because the new index depends on the new modulus $m^{\prime }$ (the new bucket count), which none of the old indices encode; every key must be recomputed against $m^{\prime }$ regardless.

(See Figure 2 for the sum.) Probe 1 always happens (weight $1$). You need probe 2 only if slot 1 was full — probability $\approx \alpha$ — so it contributes $\alpha$. You need probe 3 only if slots 1 and 2 were full — probability $\approx {\alpha }^2$ — contributing ${\alpha }^2$; in general probe $i$ carries weight ${\alpha }^{i-1}$. Because $\alpha <1$ these weights shrink geometrically, so ${\sum }_{i\ge 1}{\alpha }^{i-1}=1/(1-\alpha )$ is finite; at $\alpha \ge 1$ they do not shrink and the sum diverges — a full table has no empty slot to stop at.

A tiny factor like ×1.01 makes rehashes extremely frequent (every $\sim 0.01n$ inserts), so the constant behind $O(1)$ balloons; the factor must be a fixed number $>1$ meaningfully above 1 (2 or 1.5) for a small constant.

Because re-inserting is proportional to the number of live keys $n$, not the array size $m$; empty slots cost nothing to move, so $n$ is the true work driver.

$\alpha =0/m=0$; the grow condition $\alpha >{\alpha }_{\max }$ is false, so nothing triggers — correct, an empty table never resizes.

It becomes $1/0$, undefined — signalling a full table where an unsuccessful search never terminates. This is why open addressing must resize strictly before $\alpha =1$.

About ${\log }_{2}n$ rehashes (at sizes $1,2,4,\dots ,n$), each cheaper-then-costlier, summing to $\le 2n$ total move work.

Nothing useful — $\alpha$ assumes uniform spreading. A degenerate hash makes one chain length $n$ (or one probe cluster of $n$), so operations are $O(n)$ regardless of $\alpha$. The fix is a better hash function, not a resize.

Yes — you insert first (pushing $\alpha$ above the threshold), then check and rehash. So right after the insert and before the resize, $\alpha >{\alpha }_{\max }$ briefly; the resize restores it.

Define a minimum capacity $m_{\min }$ (a common default is the table's initial size, e.g. 16) below which you never shrink. Rule: shrink to $m/2$ only if $\alpha <0.25$ and $m/2\ge m_{\min }$; otherwise stay put. This stops pointless $\Theta (n)$ churn on near-empty tables while still reclaiming memory on large ones.

In a simple implementation, no — the rehash is a blocking $\Theta (n)$ pause. This is why latency-sensitive systems use incremental rehashing, spreading the moves across many operations.

The three ideas are: geometric vs arithmetic series ($2n$ vs $n^2$), the $1/(1-\alpha )$ cliff vs the $1+\alpha$ line, and index $=h(k)\mathrm{mod}m$ changing when $m$ changes.