Unit 5 · Heavy
Lookup by key instead of by position. Hashing is the first place where average and worst case diverge sharply, which makes stating the case a required part of every answer.
What a strong answer looks like
A strong Unit 5 answer says which case it is describing and names the assumption about the hash function that makes the average case hold.
Know
A set stores membership without duplicates; a map stores key-to-value associations. Both are specifications, implementable by hashing or by a tree.
Apply
Choose a set when only membership matters and a map when each key carries data.
Watch out
Assuming iteration order. A hash-based structure gives no ordering guarantee.
Study move
Pick a problem for each and say why the other would be the wrong fit.
Know
A hash function maps a key to a bucket. A good one spreads keys evenly, which is exactly the assumption behind constant average lookup.
Apply
State the even-distribution assumption whenever you quote constant-time behavior.
Watch out
Quoting constant time as if unconditional. With every key colliding, lookup is linear.
Study move
Describe a hash function that performs badly on a realistic key set and explain why.
Know
Chaining hangs a secondary structure off each bucket; open addressing probes for another slot. Linear probing suffers primary clustering, where occupied runs lengthen future probes.
Apply
Compare the two by memory behavior and by how gracefully they degrade as the table fills.
Watch out
Treating a collision as an error. Collisions are expected and handled, not prevented.
Study move
Insert a small set of colliding keys under both strategies and compare the probe counts.
Know
Load factor is entries divided by buckets, and rising load predicts more collisions. Implementations resize past a threshold, rehashing every key.
Apply
Explain resizing as an amortised cost: occasional linear work spread across many insertions.
Watch out
Ignoring load factor when reasoning about performance, which makes the constant-time claim unfalsifiable.
Study move
State what happens to load factor and to cost when a table doubles its buckets.
Connections and techniques that receive extra attention in this unit.
Related topics some schools attach to this unit and others leave out. Covered on request rather than assumed.
Modeling drill
Design the key for a map storing student records so that lookups stay fast, and say what would go wrong with a poorly chosen key.
