COMP9123 — Week 7
Foundations & proof moves
Week 7 foundations turn the hashing lecture into the analysis statements you actually need to say out loud: what load factor measures, what universal hashing guarantees, why DEFUNCT is logically necessary, and how hashing solves one-pass set and counting problems.
Load Factor: The Single Number That Predicts Crowding
The load factor \(\alpha = n/N\) is the lecture's compression of “how crowded is the table?” It is not a decorative symbol. It is the bridge between how much you store and how much extra work collisions force on future operations.
| Quantity | Meaning | Interpretation |
|---|---|---|
| \(n\) | Number of stored entries | How much actual data the map holds |
| \(N\) | Table capacity | How many base slots the structure owns |
| \(\alpha=n/N\) | Average occupancy | The first diagnostic to inspect when performance degrades |
| Chaining cost | \(O(1+\alpha)\) expected | Average bucket size is the right mental model |
Chaining can tolerate \(\alpha\) above 1 because buckets can hold multiple items. Open addressing is far more fragile: as \(\alpha\) approaches 1, finding an empty slot becomes increasingly expensive and clustering becomes severe.
Hash Design: Good Dispersion Beats Cute Formulas
A good hash function should be deterministic, fast, and resistant to obvious structural patterns in the keys. The lecture's universal-hashing section gives the cleanest formal statement of that idea.
Deterministic
The same key must always land in the same place for the current table and chosen function.
Uniform
Distinct keys should behave as if scattered randomly enough that no slot is repeatedly overloaded.
Efficient
If computing the hash is expensive, you have destroyed the whole point of array-style access.
If \(H\) is 2-universal, then for distinct keys \(i \neq j\), choosing \(h\) uniformly at random from \(H\) guarantees \(\Pr[h(i)=h(j)] \le 1/N\). This is the formal way to say “collisions remain unlikely even against unlucky inputs.”
The random linear family \(h(k)=((ak+b)\bmod p)\bmod N\) is the lecture's model example. It is not just another formula to memorize; it is the first place the unit asks you to trust random choice as an analysis tool.
Deletion Invariants: Empty and DEFUNCT Mean Different Things
Open-address deletion questions are almost always disguised search-correctness questions. Once the table uses a probe sequence, every future lookup depends on past insertions and deletions leaving the right traces behind.
Lookup in linear probing stops only when it reaches a truly empty cell, because that is the first proof that no later slot in the same probe sequence could contain the key.
A deleted cell is not genuine evidence that the key is absent; another colliding key may have been pushed past it earlier.
Therefore deletion must mark the slot as DEFUNCT so lookup continues but insertion still knows the slot is reusable.
Rehashing belongs here too. Once the load factor crosses a chosen threshold, the table is rebuilt into a larger array so the probe lengths or bucket lengths do not keep drifting upward.
Cuckoo Guarantees: Tiny Lookups, Controlled Insert Risk
Cuckoo hashing gives the cleanest worst-case lookup statement of the week. A key has only two candidate homes, so get and remove inspect at most those two positions. The price is that insertion may trigger a relocation chain and occasionally a rebuild.
| Claim | Reason |
|---|---|
| Worst-case lookup is \(O(1)\) | The key can only be in two known places. |
| Worst-case removal is \(O(1)\) | Removal also only needs to inspect those two candidate positions. |
| Insertion is expected \(O(1)\) | Most eviction sequences are short, but pathological cycles can still happen and force rehashing. |
Tutorial Patterns: What Hashing Lets You Do in One Pass
The later tutorial problems are pattern-recognition training. They are asking you to notice when “fast membership” or “fast counting by key” collapses a problem that would otherwise require sorting or repeated scanning.
| Problem | Hashing pattern | Time idea |
|---|---|---|
| Set intersection | Hash the smaller side as a set | One pass to build, one pass to test membership |
| Most frequent value | Map value \(\to\) count | Every element updates one counter in expected constant time |
Multimap get(k) |
Map key \(\to\) collection of values | Lookup cost becomes \(O(1+s)\) where \(s\) is the output size |
| Birthday duplicate detection | Hash seen birthdays | Report the first repeat during a single scan |
| k-gram frequencies | Map each k-gram \(\to\) count | Slide a window and update counts incrementally |
How to review this page well
The three checks are now inline on purpose. Each one lives directly under the concept it tests: expected cost, collision guarantees, and tutorial-space trade-offs. If one feels shaky, re-read only that section and say the explanation out loud before moving on.
Tutorial review
Open the tutorial PDF after finishing the study guide, not before. The point is to make the questions feel like applications of ideas you already own rather than new definitions to decode under time pressure.
Tutorial 7 checklist. You should be able to explain the effect of a weak hash function, compare chaining against probing under bad dispersion, justify DEFUNCT formally, sketch one cycle-detection method for cuckoo insertion, and spot when a set, multiset, or multimap is the intended modeling choice.