Skip to main content
ZhimaYuandi

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

Inspect the model manually

Each action changes a controlled sample. This does not execute student Python, read disks or certify mastery from clicks or model state.

Public teaching hash with chained collisions

hash(key) = sum(character_code_points) % bucket_count

The same lookup also scans entries in ascending stable-record-ID order. Compare full-key comparisons; build/rehash counts are shown separately.

Keys are lowercase ASCII examples and values represent stable record IDs. Student input is not Python-normalized. With four buckets, a and e both enter bucket 1 while remaining distinct full keys.

These are pending build/rehash parameters. Edits invalidate the previous model check; buttons apply them to the index. Inputs and model state are both saved locally.

  1. Bucket 0: ∅
  2. Bucket 1: a → doc_00000000000000000000000000000001 (h=1) · e → doc_00000000000000000000000000000002 (h=1) ·
  3. Bucket 2: b → doc_00000000000000000000000000000003 (h=2) ·
  4. Bucket 3: ∅

Fixed keys a, e and b are built; a and e collide with four buckets. · Current model invariants: Consistent

Operation counts and model scope

Checks keys, IDs, buckets and lookup results. The linear baseline uses ascending stable IDs; key-comparison counts exclude sorting to reconstruct that view and UI copies. Build costs are separate; this does not prove Python dict performance.

Total hashes
3
Total key comparisons
1
Total sequential comparisons
0
Total entry writes/removals
3
Builds/rebuilds
1
Explicit lookups
0
Build hashes
3
Build key comparisons
1
Build entry writes
3
Entries
3
Bucket slots
4
Stored key/value pairs
3
Longest collision chain
2
Last hashes
3
Last key comparisons
1
Last sequential comparisons
0
Last entry writes/removals
3

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.

Counts follow the model definition, not browser elapsed time. Copies for displaying and saving model state are not counted as underlying container operations.

Execution trace (up to 40 recent events)

  1. Fixed keys a, e and b are built; a and e collide with four buckets.

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.

Download this lab’s starter

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