What you'll learn
A hash table is the structure behind dictionaries, sets, and maps in every language. It gives O(1) average-time insert, lookup, and delete — by using a hash function to turn a key directly into an array index.
By the end you'll be able to:
- Explain how hashing turns a key into a bucket index
- Describe what makes a good hash function
- Define the load factor and why it matters
The hashing idea
An array gives O(1) access if you know the index. A hash table's insight: run the key through a hash function to compute the index. bucket = hash(key) % capacity. Then insert, lookup, and delete all jump straight to the right bucket — no searching.
Key idea
Good hash functions
A good hash function is:
- Deterministic — the same key always hashes to the same value.
- Fast — computing it is cheap.
- Uniform — it spreads keys evenly across buckets, minimizing collisions.
When two different keys land in the same bucket, that's a collision — unavoidable once you have more keys than buckets. Below, separate chaining handles them by keeping a small list per bucket.
Watch it fill
The load factor
The load factor is α = entries / capacity — how full the table is. As it climbs, chains get longer and operations slow down. Hash tables keep α below a threshold (often 0.75) by resizing: allocate a bigger array and re-hash everything into it. That keeps operations O(1) on average.
| Operation | Average | Worst case |
|---|---|---|
insert | O(1) | O(n) (all keys in one bucket) |
lookup | O(1) | O(n) |
delete | O(1) | O(n) |
| Space | O(n) | O(n) |
Note
O(n) — every key colliding into one bucket. A good hash function and a bounded load factor make that vanishingly unlikely, which is why we quote the average case for hash tables.In code
# Python dicts and sets ARE hash tables
phone = {}
phone["alice"] = "555-1234" # insert: hash the key -> bucket
print(phone["alice"]) # lookup: O(1) average
print("bob" in phone) # membership: O(1) average
del phone["alice"] # delete: O(1) average
# a hash function turns a key into an int
print(hash("alice"))Recap & quick check
Key takeaways
- A hash table maps arbitrary keys to values by hashing the key into an array index.
- Insert, lookup, and delete are O(1) on average.
- A good hash function is deterministic, fast, and spreads keys uniformly.
- Collisions (two keys, one bucket) are inevitable; chaining stores a list per bucket.
- Load factor α = entries/capacity; resizing keeps α low and operations O(1).
Quick check
1. How does a hash table find where to store a key?
2. Average-case lookup in a hash table is:
3. What is a collision?
4. What does the load factor measure?
Collisions are inevitable — so how exactly do we handle them? That's the whole next module. Next up: Module 15 — Collisions & Load Factor.