3.3.2 · D5Hashing
Question bank — Hash table — structure, open addressing vs chaining
True or false — justify
Every hash table lookup is .
False. Only the average case is ; the worst case is when every key collides into one bucket (chaining) or forms one long probe run (open addressing).
A good hash function guarantees no collisions.
False. By the pigeonhole principle there are more possible keys than slots, so collisions are unavoidable; a good hash only makes them rare and evenly spread, never zero.
In separate chaining the load factor must stay below .
False. Chaining stores overflow in linked lists outside the array, so can exceed freely — buckets just hold longer lists.
In open addressing can safely exceed .
False. Every key lives inside the array, so you can never store more than keys; as the expected probes explode toward infinity.
Doubling the capacity always halves the current load factor.
True. ; doubling with fixed gives . That is exactly why rehashing resets the table to a comfortable density.
Rehashing can reuse the old indices, just copied into the bigger array.
False. Index depends on via ; changing changes almost every index, so you must recompute each key's slot and reinsert it.
Two keys with the same hash code always land in the same slot.
True. The slot is ; equal codes give equal remainders. The converse is false — different codes can still share a slot after .
A collision means two keys are equal.
False. A collision means two different keys map to the same slot; the keys themselves stay distinct, which is exactly why you still compare keys after probing to the bucket.
Using a larger prime capacity makes the hash function itself stronger.
False. A prime only improves the compression step ( mixes bits better); a weak hash code that ignores order (like a character sum) stays weak regardless of .
Open addressing is always faster than chaining.
False. It wins on cache locality (contiguous memory, no pointer chasing) when is controlled, but chaining tolerates high load and heavy deletion far better.
Spot the error
"To delete key 22 from open-addressing slot 3, I just set slot 3 to empty."
Broken. A later search for a key that probed through slot 3 will hit the empty slot and stop early, concluding the key is absent — the probe chain is severed. Use a tombstone instead.
"Tombstones are just empty slots, so insertion should skip them."
Wrong. For search a tombstone means "keep probing," but for insertion it means "free to reuse" — insert must place the new key there, otherwise the table slowly fills with dead markers.
"I'll hash strings by summing their character codes — simple and fast."
Broken. Sum ignores order, so anagrams like
"ab" and "ba" collide. The polynomial rolling hash fixes this by weighting each character by a power of ."Quadratic probing with will eventually check every slot."
Wrong in general. For arbitrary it may cycle through only a subset and miss free slots; it visits all slots only under conditions like prime and .
"With and , keys spread out nicely."
Error. A power-of-two keeps only the low bits of , so keys differing only in high bits collide; primes (or good bit-mixing) are preferred for compression.
"Since chaining never fills up, load factor is irrelevant for it."
Wrong. Average list length equals , and search cost is ; a huge turns each lookup into a long list scan even though nothing "overflows."
"Search must stop at the first non-matching key in an open-addressing probe."
Broken. Insertion placed the key by following the whole probe sequence past occupied slots; search must follow the identical sequence and only stop at a genuinely empty slot.
"Rehashing every insert keeps perfectly low, so it's the best policy."
Wrong. Rehashing is ; doing it constantly destroys performance. You resize only when crosses a threshold, so the cost is spread out — see amortized analysis.
Why questions
Why does the expected unsuccessful-search cost equal and not something linear in ?
Each probe independently hits an occupied slot with probability , so probes form a geometric series ; the chain of "still full" events compounds multiplicatively, which is why it blows up near .
Why is a common base in string hashing?
It's a prime larger than the alphabet size (spreads bit patterns well) and , so the multiply is one shift and one subtract — cheap on hardware.
Why do collisions appear far sooner than "half the slots filled" suggests?
The birthday paradox: collisions depend on the number of pairs of keys, which grows like , so with slots you expect a clash after only ~23 keys, not ~183.
Why does open addressing get cache-friendlier than chaining?
Its keys sit contiguously in one flat array, so a probe walk reads neighbouring memory the CPU already prefetched; chaining chases pointers to scattered list nodes, causing cache misses.
Why must the probe function be deterministic per key?
Search and insert must retrace the exact same slot sequence; if probing were random, a search could take a different path and miss a key that insertion placed elsewhere.
Why does a two-stage design (hash code, then ) exist instead of hashing straight to ?
Separating concerns lets the hash code focus on mixing bits from the key, while compression adapts to whatever the table currently has — crucial because changes on rehash.
Why is primary clustering specific to linear probing?
With , any key landing near a filled run joins and extends that run, so occupied blocks snowball; quadratic and double hashing scatter the probe positions, breaking the contiguity.
Why can chaining tolerate heavy deletion while open addressing struggles?
Chaining deletes by unlinking a node — the rest of the list is untouched; open addressing can't truly empty a slot without breaking probe chains, so deletions leave tombstones that must be garbage-collected via rehash.
Edge cases
What happens to open-addressing insert when (table exactly full)?
There is no empty slot, so the probe loop never terminates — insertion must fail or trigger a rehash before reaching ; this is why open addressing keeps a strict .
What is the load factor of an empty table, and is it defined?
(well defined as long as ); every lookup then finds an empty slot immediately, so search is a single probe.
Can the capacity be zero?
No — is undefined at ; a hash table must start with at least one slot, usually a small prime or power of two.
If every key hashes to the same slot, what do chaining and open addressing degenerate to?
Chaining becomes one long linked list ( scan); open addressing becomes one long probe run (). Both collapse to linear search — the degenerate worst case.
What if a key equal to one already present is inserted (duplicate)?
In a map you overwrite the existing value at that slot/node; you do not create a second entry, so stays the same and is unchanged.
A tombstone-filled table where is small but tombstones fill the rest — what's the danger?
Effective occupancy (real keys + tombstones) approaches , so probe sequences grow long even though few real keys exist; a rehash that discards tombstones restores fast lookups.
With quadratic probing and just above , what boundary can bite you?
The half-full guarantee lapses, so probing may cycle without visiting a free slot and report "full" while empty slots exist — a silent insertion failure at the edge.
Recall One-line summary of the traps
Traps :::- "Average " is not "always "; collisions are guaranteed, not preventable; open addressing needs and tombstones; index depends on so rehash recomputes; and order-insensitive hashes (character sums) are broken.