Hash a map key to a bucket
Updated
A hash map does not scan every key. It hashes the key to an integer, then takes that integer modulo the table size to pick a bucket. Put, get, and delete all start at that same bucket index.
What to focus on
For integer keys we can pretend hash(k)=k. With B=4, key 4 goes to 4%4=0, key 1 to 1%4=1, key 9 to 9%4=1. The bucket is an address, not the stored value.
Worked examples
place 4
k = 4, B = 4, hash(k)=k- 4 % 4 = 0
Result: bucket 0
place 1
k = 1, B = 4, hash(k)=k- 1 % 4 = 1
Result: bucket 1
place 9
k = 9, B = 4, hash(k)=k- 9 % 4 = 1
Result: bucket 1 — shares with 1
Try it
Write bucketOf(k, B). k is the map key. B is the number of buckets. Return k % B, using hash(k)=k. k = 4, B = 4 → bucket 0. k = 1, B = 4 → bucket 1. k = 9, B = 4 → bucket 1 (shares with 1).
k is an integer. hash(k)=k. B=4.