Quiz
Warm-up from lesson 1-1: looking up a key in a 10,000-entry dict took 1 check while the list scan took 10,000. What did this course promise to explain later?
From key to index
Arrays taught us the fastest possible lookup: compute an address, jump there, O(1). But array indexes are numbers 0..n−1, and dict keys are things like "ana". A hash table bridges the gap with two pieces:
- an ordinary array of n slots, called buckets
- a hash function: a deterministic recipe that turns any key into a number, which
% nthen squeezes into a valid bucket index
Deterministic means the same key always yields the same number, so the bucket you stored into is the bucket you will look in. A classic recipe for strings: run through the characters, and for each one multiply the running total by 31 and add the character's code (ord(ch)).
Store ("ana", 91): hash "ana" → bucket 4, drop the pair there. Look up "ana": hash it again → 4, jump straight to bucket 4. No scanning of the other buckets, ever.
Code exercise · python
Run this hash function on four names with 8 buckets. Same input, same bucket, every single run. Note ben and cai land in the SAME bucket: that is a collision, and it is next lesson's problem to solve.
Code exercise · python
Your turn: implement `bucket_of` (the multiply-by-31 recipe from the demo) and `find_collisions`, which files each name under its bucket and returns only the buckets holding 2+ names. Notice that with 11 buckets these six names happen to spread out perfectly — and that every bucket number CHANGES when the bucket count changes, because bucket = hash % buckets. That is why resizing a table (next lesson) must re-file every key.
Quiz
Why must a hash function be deterministic (same key → same number every time)?