Unit 1.5 · about 4 h
92 / 324Hash tables: collisions, load factor, resizing and tombstones
Hash maps are the default index, counter and cache. Their average is excellent and their worst case is a security incident; both follow from the load factor.
- explain
- implement
You can now
- Explain chaining and open-addressing costs in the load factor, including the \(1/(1-\alpha)\) blowup.
- Implement a hash table that resizes at a stated load factor, with deletion that preserves lookup.
- Predict adversarial degradation and name the defense (randomized hashing).
Covers
- Hashing, collisions, load factor, resizing and tombstones
Study, in this order
4 steps
- Hash maps and hash setsDSA Handbook - Foundations and linear patterns
What invariant the average-case bound depends on (\(\Theta(1+\alpha)\)); LC 1 value-to-index; LC 49 signature keys; LC 242 counters; What it actually costs (the double-plus-rehash resize contract)
- Hash collisions and the load factorDSA Handbook - Foundations and linear patterns
Two strategies, one contract; What it costs to grow; When the contract breaks: LC 128 in two complexities; How the 28C3 attack worked, and what fixed it (SipHash, PEP 456); A second example: LC 380's pointer-redirection trick
Depth · Treat the CPython probing recurrence as a reading guide for the source item below, not as a substitute for it.
- Lecture 5: Hash Tables, Sections 5.1 to 5.5 and 5.8 to 5.10Algorithms lecture notes - amortized analysis and hashing
5.2 The Importance of Being Random; 5.3 universal and near-universal definitions; 5.4 Chaining (expected \(O(1+\alpha)\)); 5.5 multiplicative hashing with Theorems 1 and 2; 5.8 Open Addressing (expected at most \(1/(1-\alpha)\)); 5.9 Linear and Binary Probing
Depth · Read the statements of 5.6 Balls and Bins and 5.7 Perfect Hashing; skip their proofs.
- CPython dict internalsCPython source - list and dict objects
USABLE_FRACTION(currently two-thirds) with its definition comment; the perturbation-probing comment (j = (5*j) + 1 + perturb);dummy(tombstone) entries on deletionDepth · Find the three definitions; do not read the whole file.
Focus on
- \(\alpha = n/m\) governs everything: chaining \(\Theta(1+\alpha)\), open addressing \(1/(1-\alpha)\); CPython resizes past \(2/3\).
- Resize doubles and rehashes every entry: an \(O(n)\) event, amortized \(O(1)\) by the unit-2 argument.
- Deletion must leave a tombstone: marking the slot empty would cut probe chains and lose keys.
- Deterministic string hashing is attackable (the 2011 HashDoS); Python seeds SipHash per interpreter (PEP 456).
Reproduce closed-book
dict on Python 3.13.14, recording sys.getsizeof after each insert. The first insert allocates the 8-slot table; assert the later size steps at \(n\) = 6, 11, 22 and 43, confirming the two-thirds rule. Then delete two keys and assert the byte size and the remaining key order are unchanged.Traps
- Reading insertion order as sorted order; dicts remember arrival, not rank.
- Checking the map after storing on Two Sum style lookup: store-then-check matches an element with itself on inputs like
[3, 3]. - Assuming worst-case \(O(1)\): adversarial keys drive any fixed hash to \(O(n)\) chains.
Practice
Attempt cold with hidden tags. Implement put, get and remove with chaining or open addressing plus a load-factor resize. Add randomized put/get/remove histories checked against a dict oracle. Judge with the Example operation sequence.
After submitting, read the AlgoMaster Design HashMap write-up (https://algomaster.io/learn/dsa/design-hashmap) and the handbook hash-collisions chapter for the resize contract.
Self-test
-
Derive the expected cost of a chained lookup.
The key hashes to a uniform bucket plus a scan of its chain of expected length \(\alpha\): \(O(1) + O(\alpha)\). -
Why does CPython resize at the 6th insert into an 8-slot table?
The usable fraction is \(2/3\): \(8 \times 2/3 = 5.33\), so the 6th insert exceeds it and doubles the table. -
What breaks if deletion marks the slot empty instead of dummy?
Later keys that probed past the deleted slot become unreachable: their chain is cut and lookup wrongly reports absent. -
State universal hashing in one line and why it helps.
Draw the hash function at random from a family where each colliding pair has probability at most \(1/m\). The adversary cannot fix a bad input set in advance.
Completion criterion
Stop when
Your resize script asserts the 6/11/22/43 steps, and your HashMap passes 200 randomized histories against the dict oracle.
Leads to
- 1.8 Prefix sums, difference arrays and prefix plus hash Prefix counting turns hash maps into subarray oracles.
- 1.6 Stacks, queues, deques and monotone structures The LC 380 trick pairs a hash map with a dynamic array.
Comes after
- 1.2 Aggregate, accounting and potential amortized analysisTable resizing reuses the same doubling proof with the load factor as the trigger.
- 1.4 Arrays, strings, locality and linked structuresHash tables layer probing and chaining over the array layout.
Resources for this unit
- DSA Handbook - Foundations and linear patterns Study Part 0, Part 1, Part 3 and Part 4 in order, plus the Part 5 Linked-list fundamentals chapter. Use the routing-rule pages for arrays versus lists, map choice, stack versus queue, two pointers, sliding windows and prefix methods before seeing solved code.
- Algorithms lecture notes - amortized analysis and hashing Use note 9 Amortized Analysis for the summation, taxation, charging and potential-function proofs, and note 5 Hashing for chaining, universal hashing and open-addressing analysis, when the handbook treatment is too brief for a proof.
- CPython source - list and dict objects Read
list_resizeinObjects/listobject.cfor the growth formula and pattern comment, and theUSABLE_FRACTIONdefinition, perturbation-probing comment and dummy-entry handling inObjects/dictobject.c. Read the cited functions and comments only.
Also in this section
- AlgoMaster DSA - linear structures slice Attempt Design HashMap, Longest Substring Without Repeating Characters and Sliding Window Maximum cold. Hide tags, state the invariant first, and add randomized operation histories to Design HashMap.
- MIT 6.042J - asymptotics and invariants Use the asymptotics, state-machine invariants and proof-method readings when a cost or correctness argument is weak. Solve only the matching problems.
- Algorithmica - memory and data layout Read the memory hierarchy, cache and complexity-model chapters, then measure one contiguous-versus-linked and one hash-versus-ordered workload crossover.
- NeetCode - unseen linear problems Use only for two tag-hidden transfer problems after the AlgoMaster slice. Do not start another full roadmap or watch a solution before the attempt is complete.
- Hypothesis documentation - Quickstart and stateful testing Follow Quickstart for
@givenstrategies and the pytest combination, Configuring test settings formax_examplesandderandomize, then Rule-based state machines (rule,precondition,invariant,run_state_machine_as_test) for randomized operation histories againstdictanddequeoracles.