Straight to the right page
Hash Maps as Dictionaries
The analogy
To find "otter" in a dictionary you do not start at page 1 — the word itself tells you roughly where to go. A hash map does the same trick with maths: it turns the key into a page number, then looks only at that page.
Visualizer
Straight to the page
step 1 / 15[0]
[1]
[2]
[3]
[4]
[5]
[6]
7 empty pages. Nothing is sorted, and we will never scan looking for a key.0 entries in 7 pages — load factor 0.00
def my_hash(key, n_buckets):
total = 0
for ch in key:
total += ord(ch)
return total % n_buckets
d = {"cat": 1, "dog": 2}
d["dog"] # straight to the bucket — O(1)Check yourself
Average lookup cost in a well-sized hash map?