Open addressing can store more items than it has slots.
False. Every key lives inside the array, so once all m slots are full you cannot insert without rehashing — unlike chaining, which can keep hanging nodes off a bucket forever.
Linear probing has the best cache locality of the three schemes.
True. It walks slots +1 at a time, so probed slots are contiguous in memory — the CPU cache prefetches the next slots for free. Quadratic and double hashing jump around, defeating prefetch.
Quadratic probing eliminates all clustering.
False. It kills primary clustering (keys with different homes no longer merge into one run) but creates secondary clustering: two keys with the same home still follow the identical jump sequence 1,4,9,…. The two clustering types are contrasted in the figure below.
Reading the figure.Top row (Linear, primary): the amber slots form one solid block — a key homing anywhere inside it is pushed to the block's right end, so neighbouring runs fuse into a single ever-growing traffic jam. Bottom row (Quadratic, secondary): the amber slots are spread out (they sit at offsets 1,4,9,… from home), so no solid block forms — but any other key sharing that same home retraces this exact scatter, which is the leftover "secondary" clustering.
Double hashing can suffer secondary clustering.
False (essentially). Two keys share a probe path only if they agree on both the home h1(k) and the step h2(k); that near-never happens, so the "same home ⇒ same path" defect of quadratic probing disappears.
If m is prime, quadratic probing is guaranteed to find an empty slot no matter how full the table is.
False. Prime m only guarantees the first ⌈m/2⌉ probes are distinct, so the guarantee holds only while the load factor α=n/m≤0.5. Past half-full, quadratic probing can loop among occupied slots forever.
Deleting a key by marking its slot EMPTY is safe as long as no other key ever collided with it.
True but fragile. If truly nothing probed through that slot the chain is intact — but you rarely know that, so in practice you must use a tombstone. It's a correctness landmine.
A higher load factor α always means slower searches.
True for open addressing. Expected unsuccessful probes are 1/(1−α), which grows monotonically and explodes as α→1 (derivation sketched in the "Why" section). See Load factor and rehashing.
For double hashing, h2(k)=0 is a valid step size.
False. A step of 0 means every probe returns to the home slot h1(k) — an infinite loop on a single occupied slot. That's why h2 is forced into [1,m−1], e.g. h2(k)=1+(kmod(m−1)).
Using a power-of-two table size makes double hashing simpler and safer than a prime size.
False. With m=2p you must also force h2(k) to be odd (odd numbers are the ones coprime to a power of two). A prime size lets anyh2∈[1,m−1] work — fewer constraints.
Tombstones cost nothing once you have them.
False. Searches must pass through tombstones as if occupied, so a table clogged with tombstones behaves like a fuller table — probe chains lengthen. You periodically rehash to sweep them away.
"Linear probing uses f(i)=i (jump i slots past home), so after m probes it may still miss some slots."
Wrong. Adding 1 each step cycles through allm residues mod m — it's a guaranteed full permutation. Linear probing's flaw is clustering, not unreachable slots.
"Quadratic probing with f(i)=i2 and m=8 is fine because 8 is even, keeping arithmetic cheap."
Wrong. With composite m, i2modm hits very few distinct residues, so most slots are unreachable and inserts fail early. The residue map below shows i2mod8 reaching only slots {0,1,4} — five slots are invisible. Quadratic probing wants a primem.
Reading the figure. Slots 0 to 7 sit in a row; each is coloured amber ("hit") only if some i makes i2mod8 land on it. Only 0,1,4 light up because 02,12,22,…mod8 cycles through just {0,1,4,1,0,1,4,1} — the five dark slots labelled "MISS" can never be reached, so a nearly-empty table can still refuse an insert.
"To delete in open addressing, find the key and set the slot to EMPTY, then shift later keys back one."
Wrong on two counts. (1) There is no simple "shift back" — later keys were placed by their own probe rules, not along a straight line, so sliding them left would put them where their own probe sequence never visits. (2) An EMPTY marker looks identical to "never used," so a later search for a key placed past the hole stops early and reports "absent." The fix is a tombstone: a third state meaning "was occupied, now deleted." A search treats it as "keep going" (so the chain past it survives), while an insert may reuse it. This keeps probe chains intact — the exact before/after is drawn in the Edge cases diagram.
"Double hashing needs only h1 to be a good hash function; h2 just has to be nonzero."
Wrong.h2 must also be coprime to m (share no factor with m), otherwise the step size divides evenly into the table and the probe sequence visits only m/gcd slots — never all of them.
"Since 1/(1−α) is the cost, a table at α=0.99 takes about twice as long as α=0.5."
Wrong.α=0.5 gives 2 probes; α=0.99 gives 1/(0.01)=100 probes — fifty times slower, not twice. The cost is nonlinear and blows up near 1.
"Quadratic probing's home computation h1(k)+i2 can be negative for large i, so we need abs()."
Wrong.i2 is never negative, and we always reduce mod m which yields a value in [0,m−1]. No abs() needed; the confusion comes from schemes using ±i2.
Why does open addressing forbid α≥1 while chaining allows α>1?
In open addressing each slot holds at most one key, so the key count n can't exceed the slot count m; chaining stacks multiple keys per bucket in a list, so α=n/m can freely exceed 1.
Why is the expected unsuccessful-search cost 1/(1−α), and what is the picture behind summing αi?
Picture the probe as a "survival" walk: you keep walking only while every slot so far is occupied. The chance of surviving to probe i (all i earlier slots full) is αi, a bar of shrinking height 1,α,α2,…. A neat fact about non-negative integer counts is E[probes]=∑i≥0P(survive past i) — the total area under those shrinking bars. Since each bar is α times the previous, their areas form a geometric pile that sums to 1−α1: a small α makes the bars vanish fast (few probes), while α→1 makes them barely shrink (a towering pile).
Why does primary clustering make big clusters grow faster than small ones?
A key whose home lands anywhere inside a cluster of length L gets appended to its end, so a cluster captures new keys in proportion to L — rich-get-richer, growth accelerates with size.
Why does double hashing beat quadratic probing even though both make large jumps?
Quadratic's jump pattern f(i)=i2 is fixed by i alone, so equal-home keys collide throughout; double hashing's step h2(k) is keyed, so equal-home keys diverge immediately.
Why do we insist h2(k) be coprime to m?
Repeatedly adding a step s mod m visits every slot iffgcd(s,m)=1; otherwise the sequence cycles early and some empty slots are permanently unreachable.
Why is deletion "the hidden trap" specifically in open addressing and not in chaining?
In chaining you just unlink a node and the list stays intact; in open addressing a key's presence is implied by an unbroken probe chain, so removing a middle key can silently sever the trail to keys placed after it.
Why does a prime m help double hashing more than it helps linear probing?
Linear probing already reaches all slots for any m; double hashing's guarantee depends on h2 being coprime to m, and a prime m makes everyh2∈[1,m−1] automatically coprime.
What happens in linear probing when the very last slot m−1 is the home and it's occupied?
The probe wraps: (m−1+1)modm=0, so it continues from slot 0. The mod makes the array circular — no "off the end" case exists.
What does quadratic probing do at i=0 regardless of the constants?
The probe offset f(0)=0, so the first probe is always the home slot h1(k) — the contract f(0)=0 guarantees we try home before jumping.
For double hashing with h2(k)=1+(kmod(m−1)), what is the smallest possible step size and why can't it be 0?
The smallest is 1 (when kmod(m−1)=0); the leading +1 makes 0 impossible, so we never get the infinite-loop step of returning to home forever.
Show what a tombstone actually does to a probe chain when a middle key is removed.
A deleted middle slot marked EMPTY breaks the chain (later keys become unreachable), while a tombstone keeps searches walking through — the two outcomes are drawn below.
Reading the figure. Both rows show the same chain: A at home, then the deleted key, then B which was placed after it. Top (EMPTY): the middle slot reads EMPTY, so a search for B reaches it, sees "never used," and stops — the amber arrow marks where B is lost. Bottom (TOMB): the middle slot holds a tombstone; the cyan arrow shows the search passing straight through it and reaching B. Same chain, one marker's difference between a bug and correctness.
If every slot in the table is a tombstone (all keys deleted but never rehashed), what does an unsuccessful search cost?
Roughly m probes — searches treat tombstones as pass-through, so they walk the entire probe sequence before concluding "absent." This is exactly why you rehash to clear tombstones.
How do tombstones degrade a successful search, not just an unsuccessful one?
A successful search must still march through every tombstone lying before its target on the probe path, so those dead markers pad the walk even when the key is present. Effectively the search behaves as if the load factor were α′=(n+t)/m where t is the tombstone count — the key is found, but later than a freshly-rehashed table would find it.
What is the expected number of probes at α=0 (empty table), and does the formula agree?
One probe — the home slot is free. The formula 1/(1−0)=1 agrees, confirming the base case.
In quadratic probing with m prime and α=0.5 exactly, is a free slot still guaranteed?
Yes — the first ⌈m/2⌉ probes are distinct, and at α=0.5 at most half the slots are full, so one of those distinct probes must land on an empty slot.
What breaks if you pick h2(k)=kmodm (allowing 0) for double hashing?
Any key with kmodm=0 gets step 0 and loops on its home slot forever on the first collision — an infinite insert loop. Always force h2≥1.
Recall Self-check
Grade yourself: for any item you missed the reason on (not just the verdict), reread that section of the parent note before moving on.
