Hash Tables
The magic behind dict and set.
How can a dictionary find one key among millions, instantly, without searching? The answer is a hash table. It's the most useful data structure in everyday programming, and Python's dict and set are both built on one.

- Find one key among millions
- Instantly, no searching
- dict and set use hash tables
How a hash table works
A hash table is an array of buckets. To store a key, Python runs it through a hash function, which turns the key into a big number. That number picks a bucket. To find the key later, Python hashes it again, and goes straight to the same bucket. No searching. That's why lookups are O of one on average.
Hashing for real
Python's hash function is built in. The same key always gives the same number, while the program runs. Then the remainder after dividing by the number of buckets picks a bucket. Here we use eight buckets. Run it. Each name lands in a bucket between zero and seven, and you could find it again instantly.
names = ["Priya", "Sam", "Alex", "Jo"]
buckets = 8
for name in names:
h = hash(name) % 1000003
print(f"{name:<6} hash ends ...{h:>7} bucket {h % buckets}")Priya hash ends ... 276970 bucket 2 Sam hash ends ... 841478 bucket 6 Alex hash ends ... 970532 bucket 4 Jo hash ends ... 583896 bucket 0
Summary
A hash table turns each key into a number, and that number picks a bucket. Finding a key means hashing it again. Next, what happens when two keys want the same bucket.
Key takeaways- key → hash → bucket
- Lookups are O(1)
- dict and set use it