Unit 23: Hash Tables
How dictionaries really work.
Unit 23 of 31 in Python for kids. Its 4 lessons are Turning Words Into Numbers, Buckets, When Two Land Together and Hash Master — below is everything each one explains, and a question or two from it to try.
Every sample on this page was run through real Python before it shipped, and prints exactly what it says it prints.
This unit opens with a fortnight’s trial of everything — no card needed — or with a family plan, bought in the iPhone app. The first two units of every track are free for ever. Try it in the app.
🔢 Turning Words Into Numbers
The problem a dictionary solves
Finding a name in a list means checking each one in turn. A dictionary finds it instantly, however many there are. The trick is turning the key itself into a *position*.
Python
ages = {"Ada": 9, "Sam": 11}
print(ages["Sam"])It prints
11
A hash is a word squashed into a number
A hash function turns anything into a number. Here we add up the letter codes — ord gives each letter its number.
Python
def hash_text(text):
return sum(ord(c) for c in text)
print(ord("a"))
print(hash_text("cat"))It prints
97 312
Then squeeze it into the shelf you have
The number is far too big for a small table, so % folds it into range. With 10 buckets you always get a slot from 0 to 9.
Python
def slot(text, size):
return sum(ord(c) for c in text) % size
print(slot("cat", 10))
print(slot("dog", 10))It prints
2 4
Python’s own hash is scrambled on purpose
Python has a built-in hash(), but for text it mixes in a different random number every time your program starts — so the same word gives a different hash each run. That is a safety measure, and it is why we use our own predictable one for learning.
Python
print(hash("cat") == hash("cat"))
print(hash(42))It prints
True 42
Try it yourself
Why use % on the hash number?
- To make it smaller to read
- To fold it into the number of buckets the table actually has
- To make it positive
- It is not needed
Answer it in the app
🪣 Buckets
A shelf of buckets
A hash table is a list of buckets. To store something you work out its slot and drop it in that bucket. To find it again you work out the same slot and look there — no searching.
Python
size = 5
buckets = [[] for _ in range(size)]
def slot(text):
return sum(ord(c) for c in text) % size
buckets[slot("cat")].append(("cat", 9))
print(slot("cat"))
print(buckets[slot("cat")])It prints
2
[('cat', 9)]
Looking one up
Go to the right bucket, then check the few things in it. Because each bucket holds hardly anything, this is almost instant no matter how big the table gets.
Python
size = 5
buckets = [[] for _ in range(size)]
def slot(text):
return sum(ord(c) for c in text) % size
buckets[slot("cat")].append(("cat", 9))
def get(key):
for k, v in buckets[slot(key)]:
if k == key:
return v
return None
print(get("cat"))
print(get("cow"))It prints
9 None
Try it yourself
Why is looking something up in a hash table so fast?
- The list is sorted
- The key itself says which bucket to look in, so almost nothing is searched
- Computers are fast
- It checks every bucket quickly
What does this print?
Python
size = 4
buckets = [[] for _ in range(size)]
buckets[1].append(("a", 1))
buckets[1].append(("b", 2))
print(len(buckets))
print(len(buckets[1]))Answer them in the app
💥 When Two Land Together
Collisions are normal
Two different keys can easily land in the same slot — that is a collision. It is not a bug, and with more keys than buckets it is unavoidable.
Python
def slot(text, size):
return sum(ord(c) for c in text) % size
print(slot("ab", 5))
print(slot("ba", 5))It prints
0 0
Keep both in the same bucket
The usual fix is chaining: the bucket holds a little list, so both fit. That is why the lookup still checks the key after finding the bucket.
Python
size = 5
buckets = [[] for _ in range(size)]
def slot(text):
return sum(ord(c) for c in text) % size
buckets[slot("ab")].append(("ab", 1))
buckets[slot("ba")].append(("ba", 2))
print(buckets[0])It prints
[('ab', 1), ('ba', 2)]
Too few buckets makes it slow again
With only one bucket every key collides, and the "instant" lookup becomes a plain search through everything. Real dictionaries grow themselves a bigger table when they fill up, to keep buckets short.
Python
size = 1
buckets = [[] for _ in range(size)]
for word in ["cat", "dog", "hen"]:
buckets[0].append(word)
print(len(buckets[0]))It prints
3
Try it yourself
Why must a lookup still compare the key after finding the bucket?
- To be safe
- Because something else may have collided into the same bucket
- To count the items
- It does not have to
Answer it in the app
🏆 Hash Master
Try it yourself
What does this print?
Python
def slot(text, size):
return sum(ord(c) for c in text) % size
print(slot("a", 10))
print(slot("b", 10))Answer it in the app