AI Hints
DSA in Python · Lesson 19 of 132

Hash Tables

The magic behind dict and set.

⏱ 2 min read▶ Video at 21:53🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Hash Tables
From the video: Hash Tables
  • 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.

Hash functionkey → number
Number → bucketindex into an array
Storeput it in that bucket
Findhash again, go straight there

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.

hashing.pypython
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}")
Output
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
Next up: Collisions — when two keys share a bucket