Question bank — Python dict and set internals

False. It is O(1) on average when hashes spread out, but worst case is O(n) when many keys share the same low $k$ bits (or an adversarial hash) so every insert probes a long chain.

False. CPython uses open addressing: colliding entries live inside the same array (the row of boxes above), found by probing other slots, which is cache-friendly.

True. The equality contract "==if a == b then hash(a) == hash(b)==" spans types: 1 (int), 1.0 (float) and True (bool) all compare == and are numerically 1, so CPython deliberately makes their hashes all 1.

False. It becomes a ==DUMMY== marker; setting it to EMPTY would break probe chains that pass through that box, making later keys report "not found".

False. Only dict (since 3.7) preserves insertion order, via a separate entry list — not by the hash slots. set gives no order guarantee.

False. By the definition above, $\alpha =\text{fill}/m$ where fill = active entries plus DUMMY slots, so a table crowded with dummies can resize even with few live keys.

True. That is exactly why $h\&(m-1)$ works as the index: with $m=2^k$ the mask $m-1$ keeps the lowest $k$ bits, equalling $h\mathrm{mod}m$ but faster.

True. The index $h\&(m-1)$ depends on $m$; when $m$ changes the low-$k$-bit mask changes, so every key must be rehashed into a new slot.

True. A tuple of immutable items is itself hashable, so its hash never changes after insertion — unlike a list, which is unhashable.

True. Any two keys with the same low $k$ bits collide at $i_0$ even with different full hashes; the perturbed probe then scatters them apart.

False. A resize is a genuine O(n) event; "amortized" means its cost is spread over the ~$m$ inserts that preceded it, averaging to O(1).

Error: they are the same key, so length stays 1 and the value is last-write-wins; only the first key object is kept.

Half-error: h % m is correct, but CPython relies on power-of-two $m$ precisely so it can replace % with the faster h & (m-1); the two agree only when $m=2^k$.

Error: linear probing causes clustering; CPython uses the perturbed probe $i_{n+1}=(5i_n+1+\text{perturb})\&(m-1)$ that folds in the high hash bits (via perturb) to break clusters.

Error: $0.625<0.6\overline{6}$, so fill has not crossed $\frac{2}{3}\cdot 8\approx 5.33$; resize needs fill to reach 6.

Error: during search a DUMMY is treated as occupied — probing skips over it; only during insertion may a DUMMY be reused.

Error: the language forbids it at the type level — mutable objects like list raise TypeError on hash(), so you can never insert one in the first place.

Error: they enter through perturb on later probes, guaranteeing the sequence visits every slot so no key is ever lost.

Because a key inserted after the deleted one may sit further down the same probe chain; if a search stopped at the dummy it would wrongly report "not found".

Dummies lengthen probe chains without holding live data, so counting them in $\alpha =\text{fill}/m$ forces an earlier cleansing resize that purges every dummy.

The multiplier-plus-shift mixes the high bits of $h$ (carried in perturb) into the index gradually, scattering colliding keys and guaranteeing the sequence eventually covers all $m$ slots.

Each probed slot is occupied with probability $\approx \alpha$, so needing $\ge k$ probes needs the first $k-1$ to be full, probability ${\alpha }^{k-1}$; the expected count is $E={\sum }_{k\ge 1}{\alpha }^{k-1}$.

Because ${\sum }_{k\ge 1}{\alpha }^{k-1}=1+\alpha +{\alpha }^2+\cdots$ is a geometric series with ratio $\alpha <1$; multiplying $S$ by $(1-\alpha )$ telescopes to $1$, so $S=1/(1-\alpha )$.

At $\alpha =2/3$ the expected probe count is $1/(1-2/3)=3$ — a small constant that keeps lookups fast; letting $\alpha \to 1$ makes $1/(1-\alpha )$ blow up.

A tree is O(log n) and needs an ordering, while a hash jumps (almost) straight to the slot in O(1) average using only equality and a hash.

O(n): all keys pile into one probe chain, so the "constant number of probes" guarantee collapses into a linear scan.

Slot $i_0=h\&(m-1)$ is EMPTY, so no probing occurs and the entry lands immediately in one step.

Yes — if the accumulated dummies pushed fill past $\frac{2}{3}m$ earlier, a resize fires and rebuilds a clean table with the dummies purged.

It stops at the first EMPTY slot in the probe sequence and reports "not present" — a DUMMY alone can never terminate a search.

They are stored as one entry; the table keys on equality plus equal hash, so equal keys always overwrite rather than coexist.

Correct — frozenset is immutable and hashable, while set is mutable and unhashable, so only the frozen version can be a key.

No — order comes from a separate compact entry array iterated in insertion order; the hash slots themselves scatter keys unpredictably.