D03 · PREDICT · OPERATE · EXPLAIN YOUR CHOICE
Hash Table Lab: Collisions, Lookup, Index Keys and Costs
Repeated ID lookup and title checks scan every record. After adding a hash index, different keys in one bucket are mistaken for identical titles. A collision does not mean equality.
Back to the practice route →Make a prediction first
- The teaching hash is the sum of character code points modulo bucket count, with chaining. Lookup still compares complete keys. This public simplification is not Python dict internals.
- The local project maintains by_id and Python strip().casefold() title indexes. Synchronize add, edit, remove and undo; rebuild from records after loading rather than saving redundant indexes separately.
- Web keys are ASCII teaching examples, not Python normalization of arbitrary titles. Old keys must miss after renaming. Test absence, collisions, duplicate keys and consistency after reload separately.
This is a deterministic teaching model. State checks inspect model invariants, not your prediction or Python code, and do not establish mastery. Model operation counts, browser time and Python implementation costs are different measures.
Controlled data-structure model
This checks model state only. It does not execute your Python or grade your prediction.
Unchecked or invalidated
Progressive learning hints
Hints are fixed teaching content. Their use is recorded.
Hint 1
Compute buckets for a and e with four buckets. Does sharing a bucket prove equal keys?
Hint 2
A bucket narrows the candidates; compare full keys within the chain. Validate a renamed key before removing the old one and inserting the new one, retaining the record ID.
Hint 3
Assert existing, missing and colliding distinct keys, plus the old key after rename. Count build hashes, chain comparisons and storage rather than proving complexity from one animation’s timing.
My Python draft
Save and export your draft here. Code is not executed or synced to the starter. Draft, input or strategy edits invalidate earlier model results and self-reports.
Local learning records
Saved only in this browser; export is available. No cross-device sync or proof of mastery. Earlier F01 and six-task records are preserved through migration.
- D03 opened: —
- Model check: Unchecked or invalidated
- Local tests (self-reported): —
- Highest hint level: 0/3
- Reference viewed: —
- Unaided variant (self-reported): —
Implement it in the same Campus Resource Organizer
class DocumentIndex:
def rebuild(self, documents):
raise NotImplementedError
def lookup_id(self, identifier):
raise NotImplementedError
def lookup_title(self, title):
raise NotImplementedError
An independent snapshot adds only this lab’s fault to the M1 baseline. The M2 starter contains all three labs’ unfinished parts. Keep reference answers separate from your own work.
python check_environment.py python -m unittest tests.test_d03 -v python -m unittest discover -s tests -v
Use Python 3.11+ and its standard library. Extract into a new directory. See the package’s exact intentional-failure list. A passing reference validates materials; you still need to run your own code.
Independent variant
Independently implement challenges.word_counts(words). State that keys are normalized words and values are counts. Use strip().casefold() in Python; test repetitions, case, Straße/STRASSE and whitespace. The page does not simulate arbitrary Unicode casefold.
python -m unittest tests.test_m2_variants -v
Replace the skipped placeholder in tests/test_student_counterexamples.py with your own counterexample and explanation. Attempts using hints or references are not recorded as unaided.
Costs and model boundaries
With suitable hashing and load assumptions, lookup is near O(1) on average but can be O(n) in the worst case, plus key-processing cost. Builds/rebuilds process all keys and chain comparisons. Extra storage includes buckets and entries. The same lookup also scans in stable-record-ID order; compare both comparison counts and separate build costs. Counts are not Python dict timings.
Reference explanation and answer
View reference explanation (records answer use)
Hashing maps keys to buckets; chaining still compares entries to resolve collisions. Renaming is not merely replacing a value: invalidate the old key and preserve record identity. Do not infer Python dict layout or performance from this model. Verify indexes against current records.
Download this lab’s reference (answer) · Version and source digest
Course references and related experiments
- F03: stable-ID lookup
Keep a correct linear-lookup baseline first.
- F04: title rules
Index optimization must preserve normalization and failure rules.
- Stack Lab: Undo Mistakes in a Campus Organizer
- Queue Lab: Process Jobs in Order and Inspect Ring Buffers