COMP9123 — Data Structures & Algorithms
Week 7: Hashing
Week 7 asks a very practical question: how do we keep map operations near constant time when the key space is huge, sparse, or made of strings and objects rather than tiny integers? The answer is hashing, but the real lesson is that fast lookup depends on both a good hash function and a careful collision strategy.
A good Week 7 answer sounds like a systems designer: you justify the table layout, the collision plan, and the resizing rule together.
Why Hashing Exists: Direct Access Is Wonderful Until the Key Space Explodes
The lecture starts with network routers because the motivation is real, not decorative. A router needs destination-based get(k) and routing-table put(k, c) at high speed. In the abstract, this is just the map ADT. The challenge is implementing that map when keys are large, sparse, or not naturally tiny integers.
| Idea | Why it is tempting | Why it breaks |
|---|---|---|
| Unsorted list map | Easy to store key-value pairs and iterate over them. | get, put, and remove can all degrade to a full scan. |
| Direct-address array | If keys lie in [0, N-1], then the key itself can be the array index and access is true worst-case O(1). |
Space becomes absurd when the possible key universe is much larger than the number of stored items, like nine-digit student IDs. |
| Hash table | Preserves array-style indexing without demanding a tiny key space. | Different keys can now land on the same slot, so collisions become the central design problem. |
Map recap
Week 7 still lives inside the map ADT: get, put, remove, iteration, size, emptiness.
Professor move
When a lecture suddenly returns to an old ADT, it is usually preparing a new implementation comparison, not repeating content.
Key insight
Hashing is what you choose when direct addressing is too wasteful and ordered structures are slower than the workload wants.
Useful exam sentence: direct addressing is fast because there are no collisions, but it is often impractical because the table size must match the full key universe rather than the number of stored items.
Hash Design: From Arbitrary Keys to Apparently Random Slots
A hash function does not need to be magical. It needs to be deterministic, fast, and good at dispersion. The lecture makes an important conceptual split here: usually we first convert the key into an integer hash code, then compress that integer into the table range.
| Step | Role | Week 7 example |
|---|---|---|
| Hash code \(h_1\) | Turn the original key type into an integer. | A string, image, or tuple is reduced to a number first. |
| Compression \(h_2\) | Map that integer into the legal slot range [0, N-1]. |
Modulo division such as k mod N. |
| Final goal | Spread keys so the table looks random enough that no bucket becomes a hotspot. | Uniform collision behavior matters more than “clever-looking” formulas. |
Simple modular division
For integer keys, h(k)=k mod N is easy to compute and easy to reason about by hand.
Bad tuple idea
Summing components can collide on permutations, so mate, meat, tame, and team can all receive the same code.
Universal hashing
Choose a random function from a 2-universal family so the collision probability between distinct keys stays at most \(1/N\).
The lecture's random linear form \(h(k)=((ak+b)\bmod p)\bmod N\) injects controlled randomness into the compression stage.
That makes it much harder for a structured key set to line up with one especially unlucky deterministic pattern.
The clean takeaway is probabilistic: for distinct keys, collision probability is bounded by \(1/N\), and the expected number of collisions against a fixed key in a set of \(n\) keys is at most \(n/N\).
mate, meat, tame, and team all collide under a sum-of-components hash code?Separate Chaining: Let Each Slot Own a Small Collection
Separate chaining handles collisions by admitting that one array cell may need to represent several entries. Instead of forcing everything into a single slot, each slot points to a bucket, commonly a linked list or small secondary structure.
| Question | Answer in chaining | Why students should care |
|---|---|---|
| What happens on a collision? | The entry is appended to the bucket for that slot. | The table itself stays simple; the complexity moves into bucket scans. |
| How does load factor matter? | \(\alpha=n/N\) is the expected bucket size under uniform hashing. | The expected cost becomes \(O(1+\alpha)\), which is why resizing matters. |
| What is the weakness? | If too many keys pile into one bucket, worst-case time becomes \(O(n)\). | This is the “average fast, worst-case fragile” theme of classical hashing. |
Why chaining is easy to delete from
Removing a key only changes its bucket. There is no global search path to preserve, unlike linear probing.
Why rehashing still matters
If \(\alpha\) keeps growing, buckets stop being tiny. The lecture explicitly ties performance back to keeping the load factor bounded.
The lecture's practical note is worth remembering: Java's HashSet keeps the load factor below about 0.75 and even upgrades very large buckets away from plain linked lists.
Open Addressing: Keep Everything in the Table and Probe for Space
Open addressing stores all keys inside the table itself. With linear probing, a collision at h(k) means: try the next slot, then the next, wrapping around as needed. This often feels elegant at first because the memory layout is compact, but the invariants are much more delicate.
| Operation | Key idea | Implementation consequence |
|---|---|---|
get(k) |
Start at h(k) and follow the probe sequence until you find the key, a truly empty slot, or you have probed \(N\) cells. |
Search must keep moving past DEFUNCT cells. |
put(k,v) |
Search like get, but also remember the first DEFUNCT or empty slot that could host the new item. |
Insertion depends on the same probe path as lookup. |
remove(k) |
Replace the found entry with DEFUNCT rather than clearing it outright. | Deletion is a correctness issue, not just a bookkeeping issue. |
Suppose a later key collided earlier and was placed farther down the same probe chain.
If you turn a removed slot into a truly empty cell, future lookups may stop there and incorrectly conclude the later key is absent.
DEFUNCT preserves the search corridor: lookup skips over it, while insertion may reuse it.
Python's dict is the lecture's real-world reminder that open addressing is not a toy. It is fast in practice because memory locality is excellent, but it only stays fast when the load factor is kept comfortably below full.
get(k) do when it reaches a DEFUNCT slot?Cuckoo Hashing: Two Homes Per Key, Stronger Lookups, Trickier Inserts
Cuckoo hashing answers the main complaint against ordinary hash tables: bad worst-case lookup behavior. Each key gets two candidate locations, one in each of two tables. Lookup becomes tiny and predictable, but insertion can trigger an eviction chain.
Two legal homes
For key k, only T1[h1(k)] and T2[h2(k)] are ever relevant.
Evict on collision
If the target cell is occupied, kick out the old item and move it to its alternate home.
Watch for cycles
If evictions start repeating, insertion has entered a cycle and the implementation must bail out or rehash.
| Operation | Why the bound is attractive | Lecture message |
|---|---|---|
| Lookup / remove | Worst-case \(O(1)\), because only two locations ever matter. | This is the big upgrade over chaining and linear probing. |
| Insert | Expected \(O(1)\), not worst-case \(O(1)\). | The hard work has been moved into eviction management. |
| Table sizing | The lecture states expected \(O(n)\) for \(n\) inserts when \(N > 2n\). | Low occupancy is part of the guarantee story. |
The tutorial pushes you to think operationally here: cycle detection can be done by counting evictions or by flagging visited entries. Both methods are really answering the same question, namely whether the insertion path has started repeating.
Sets, Multisets, and Multimaps: Reuse the Map Idea Instead of Reinventing It
The end of the lecture is deceptively important. It shows how once you trust a fast map, several other ADTs fall out almost for free. This is the kind of abstraction reuse that shows up repeatedly in tutorials and interviews.
| ADT | Map-based implementation idea | Why Week 7 cares |
|---|---|---|
| Set | Store each element as a key and ignore the value. | contains(e) becomes ordinary map lookup. |
| Multiset / bag | Use the element as the key and store its occurrence count as the value. | count(e) becomes one map query instead of a full scan. |
| Multimap | Map each key to a small collection of associated values. | The tutorial's \(O(1+s)\) target is exactly this pattern. |
Intersection in expected \(O(n+m)\)
Hash the smaller array into a set, then scan the other array and report matches. The extra-space bound follows because you only store the smaller side.
Most frequent value in expected \(O(n)\)
Use a frequency map while scanning once, then track the best count seen so far.
Birthday collision question
The tutorial's stated O(1) wording is clearly a typo in context; the intended design is a one-pass hash-based duplicate detector.
Professor lens: once a map gives expected constant-time membership, a huge class of “have I seen this before?” problems collapse into one-pass scans.
Tutorial & Code Lens: Week 7 Is About Operational Precision
This is one of the most implementation-heavy weeks in the unit. The tutorial is not just asking you to recite definitions. It is asking you to reason with exact probe behavior, exact storage overhead, and exact failure modes.
Tutorial patterns to practice
- Warm-up 1: compare chaining and open addressing when the hash function is disastrously poor.
- Warm-up 2: prove that collisions can be forced on a huge dataset no matter how good the advertised range looks.
- Warm-up 3: use a hash set to compute \(A \cap B\) in expected linear time.
- Warm-up 4–5: turn cuckoo cycle detection into concrete implementation logic.
- Problems 6–10: use maps to preserve insertion order, count frequencies, build multimaps, detect duplicates, and tally k-grams.
What the code bundle is testing
SeparateChaining.py asks you to implement the clean bucket version first. open_addressing.py adds the DEFUNCT invariant and iteration helpers. cuckoo.py forces you to think about two tables, two hash functions, and controlled eviction.
# Skeleton pressure points across the three files put(key, value) get(key) remove(key) size() capacity() is_empty() entries()
Best way to study the code this week
Do not start by coding all three classes at once. Implement and test chaining first, because it is the cleanest collision story. Then move to linear probing and write down the search rules for EMPTY, OCCUPIED, and DEFUNCT before touching code. Leave cuckoo for last and trace a few eviction sequences on paper before implementing put.
Quiz Hub & spaced review
Your local checks should now feel surgical rather than random: one for weak hash codes, one for DEFUNCT, and one for cuckoo cycle detection. Use the external tools next to mix those ideas with earlier weeks.
Recommended sequence. Finish the tutorial sheet, then return to the three inline checks from this page, then use flashcards or the Quiz Hub to see whether you can still explain the trade-offs without the tables in front of you.