Two words on one page
Collisions
The analogy
Sometimes two different words land on the same page. You do not panic — you write both on that page and read the short list to see which one you wanted. Collisions are normal; you just need the lists to stay short.
Visualizer
Two words on one page
step 1 / 19[0]
[1]
[2]
[3]
[4]
Only 5 pages this time, to force the problem into the open.0 entries / 5 pages — load factor 0.00
buckets = [[] for _ in range(5)]
def put(k, v):
i = my_hash(k, len(buckets))
buckets[i].append((k, v)) # chain, do not overwrite
def get(k):
i = my_hash(k, len(buckets))
for key, val in buckets[i]: # scan the short chain
if key == k:
return valCheck yourself
Two keys hash to bucket 3. The map…