Algorithms from zero
Hashing: multiple-choice review
Crux Multiple-choice synthesis across the hashing unit: hash functions, collisions, chaining, load factor, amortized resize, and the patterns built on hash maps and sets.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the skySix 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.
Goal
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.
Quiz
Completed
A hash set gives O(1) average lookup. What single fact is that average actually resting on?
Heads-up A hash set stores nothing in sorted order, and iteration is unordered. The O(1) comes from computing an index directly, not from any search over sorted data.
Heads-up O(1) is the AVERAGE under uniform spreading and a bounded load factor. With a bad hash function or adversarial keys it degrades to O(n) — the average is a claim about typical inputs, not a guarantee.
Heads-up The engine helps with constants, but the asymptotic guarantee still rests on uniform hashing and a managed load factor. Pathological key distributions degrade any implementation.
Quiz
Completed
Two different keys hash to the same bucket index. Under separate chaining, what happens, and what does it cost?
Heads-up That would silently lose data. Chaining stores both — the bucket is a list, and lookup compares the full key, not just the index, so colliding keys coexist.
Heads-up A single collision does not trigger a resize. Resize is driven by the overall load factor crossing a threshold, not by any one collision; collisions are expected and handled in-place by the chain.
Heads-up The index is shared but the stored key is not. Lookup scans the chain and matches on the actual key, so it returns the correct value despite the collision.
Quiz
Completed
A table holds 10 items in 5 buckets and never resizes. As you keep inserting without resizing, what happens to lookup cost, and why?
Heads-up O(1) holds only while alpha is bounded. With buckets fixed and items growing, alpha grows without limit and chains lengthen — lookup degrades toward O(n).
Heads-up More items in fixed buckets means longer chains and more comparisons per lookup, not fewer. The load factor is the driver, and it is going up.
Heads-up Collisions get MORE frequent as alpha rises — fewer free buckets per item. A fuller table means more crowding, not less.
Quiz
Completed
Inserting into a hash table is called O(1) amortized, yet a single insert can cost O(n). How are both true at once?
Heads-up Amortized is not best case — it is the average over a sequence, and it explicitly INCLUDES the O(n) resizes. They are counted, then spread across the cheap inserts via the doubling geometry.
Heads-up Copying and rehashing n items is genuinely O(n) — every item is re-placed. Amortization does not make that step cheap; it makes it rare enough that the average stays O(1).
Heads-up Deletion does not break the insert amortization. The doubling-on-growth argument stands on its own; the amortized bound is about the geometric resize schedule, not deletes.
Quiz
Completed
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?
Heads-up A frequency map works but is overkill. Membership needs only presence (a set), and two-sum needs a map from value to index of what you have already seen — neither needs full counts.
Heads-up Sorting is O(n log n) and destroys the index information two-sum needs. The hash approaches are O(n) single passes and preserve original indices.
Heads-up It is the reverse pairing: presence-only detection wants a set, and complement lookup wants a map (value to index) so you can return the pair. A bare set cannot return the matching index for two-sum.
Quiz
Completed
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?
Heads-up Chaining handles collisions correctly but not cheaply when they all land in one bucket — the chain becomes length n and lookups are O(n). Correctness survives; performance collapses.
Heads-up Resizing redistributes by the same deterministic hash, so adversarial keys recollide after the resize. A smaller threshold does not help when the attacker controls the hash inputs; you need an unpredictable seed.
Heads-up Open addressing changes how collisions are stored, not whether the attacker's keys collide. With a predictable hash they still cluster; the defense is a randomized hash, independent of the resolution scheme.
Recap
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.