Hashing: multiple-choice review
Multiple-choice synthesis across the hashing unit: hash functions, collisions, chaining, load factor, amortized resize, and the patterns built on hash maps and sets.
Six questions that cut across the whole unit. Each one is a decision you make when you reach for a hash map under interview pressure or in real code — not a definition to recite, but a tradeoff to defend.
Confirm you can connect the hash function, collision handling, load factor, and amortized resize to the everyday patterns — seen, frequency, grouping — that the individual lessons built toward.
A hash set gives O(1) average lookup. What single fact is that average actually resting on?
Two different keys hash to the same bucket index. Under separate chaining, what happens, and what does it cost?
A table holds 10 items in 5 buckets and never resizes. As you keep inserting without resizing, what happens to lookup cost, and why?
Inserting into a hash table is called O(1) amortized, yet a single insert can cost O(n). How are both true at once?
You must detect whether any value repeats in a stream and, separately, find two numbers that sum to a target. Which hashing pattern fits each?
A service hashes user-supplied strings into a table, and an attacker floods it with inputs all crafted to collide into one bucket. What is the failure, and what is the real fix?
The through-line of the unit is one chain of reasoning: a hash function turns a key into an index for O(1) average access; collisions are inevitable and chaining stores them in per-bucket lists; the load factor sets average chain length, so the table resizes — doubling and rehashing — to keep it bounded, O(n) per resize but O(1) amortized; and on top of this sit the everyday patterns — seen, complement, frequency, grouping. The same machinery degrades to O(n) when the hash is poor or adversarial, which is why a randomized hash matters for untrusted input.
Something unclear?
Ask a question about this lesson. Questions are anonymous and go straight to the author to make the lesson better.