Collision chains store pairs
Updated
When two keys land in the same bucket, that bucket holds a chain of (key, value) pairs. Get walks the chain and compares keys with equals, not just hashes. A matching hash that fails equals is the next pair, not a hit.
What to focus on
1 and 9 both hash to bucket 1 when B=4. The chain might be (1,8) then (9,3). get(9) skips 1 because 1≠9, then returns 3. Size is still 2 keys, not 1 bucket.
Worked examples
shared bucket
m = {1:8, 9:3}, k = 9- both % 4 = 1
- chain is (1,8) then (9,3)
Result: get(9)=3 after one equals-miss
equals not hash
m = {1:8, 9:3}, k = 1- hash lands in the bucket
- first pair key 1 equals
Result: 8 — stop, do not return 3
other bucket
m = {1:8, 9:3}, k = 4- 4 % 4 = 0
- bucket 0 is empty
Result: miss, do not walk bucket 1
Try it
Write get(m, k). m is the hash map of key to value. k is the key to look up. Hash k to a bucket, walk that chain, and return the value whose key equals k. Do not walk other buckets. m = {1:8, 9:3}, k = 9 → get(9)=3 after one equals-miss. m = {1:8, 9:3}, k = 1 → 8 — stop, do not return 3. m = {1:8, 9:3}, k = 4 → miss, do not walk bucket 1.
keys are integers. hash(k)=k. B=4. 1 and 9 share bucket 1.