A hash table (Python calls it a dict) stores key-value pairs and finds any key almost instantly. The trick is a hash function: it turns a key into a number, and that number tells you exactly which slot to look in. No scanning, no sorting — you jump straight to the answer. This is the data structure behind dictionaries, sets, caches, and database indexes.
Step through the animation on the right. Watch each key get hashed to a bucket, then land there. When two keys pick the same bucket — a "collision" — the second one chains onto the first. The highlighted line of code shows what is happening at each step.
The idea
You have an array of empty slots called buckets. To store a key, run it through a hash function to get a big number, then take that number mod the array size to land on a bucket index. Store the entry there. To look a key up later, hash it the same way — you get the same bucket, so you go straight to it.
Because the bucket is computed directly from the key, both storing and finding take a fixed number of steps on average — they do not depend on how many keys are already in the table. That is the magic: O(1) average time.
Walk through it
Press Play on the right, or step with Next / Back. We insert four keys:
- "cat" hashes to 8, and
8 % 5 = 3, so it goes in bucket 3. - "dog" hashes to 11, and
11 % 5 = 1, so it goes in bucket 1. - "fish" hashes to 21, and
21 % 5 = 1— the same bucket as "dog". That is a collision. - "bird" hashes to 19, and
19 % 5 = 4, so it goes in bucket 4.
When "fish" collides with "dog", we do not overwrite "dog". Instead we chain the two entries together, so bucket 1 becomes a tiny list. This fix is called separate chaining. At the end we look up "cat": hash it, get bucket 3, and find it in one hop.
The code, line by line
class HashMap:
def __init__(self, n=5):
self.buckets = [[] for _ in range(n)] # n empty lists
def put(self, key, value):
i = hash(key) % len(self.buckets) # pick a bucket
bucket = self.buckets[i]
bucket.append((key, value)) # chain if not empty
def get(self, key):
i = hash(key) % len(self.buckets) # same bucket
for k, v in self.buckets[i]: # scan that short chain
if k == key:
return v- Each bucket is itself a list (a chain), starting empty.
putcomputes the bucket index, thenappends the entry. If the bucket already had an entry, the new one simply joins the chain — that is how a collision is handled, with no special case.getcomputes the same index, then scans only that one bucket's chain. Since chains stay short, this is fast.
Complexity
| Case | Time | Notes |
|---|---|---|
| Insert | O(1) (fast) | average — hash, then append |
| Lookup | O(1) (fast) | average — hash, then scan a short chain |
| Worst | O(n) (moderate) | every key collides into one bucket |
O(n) (moderate)On average the keys spread evenly across buckets, so each chain holds just one or two entries — a constant amount of work. The worst case is O(n): if every key hashes to the same bucket, one chain holds all n entries and a lookup must scan the whole thing. A good hash function plus keeping the table from getting too full keeps you in the average case.
When to use / pitfalls
Reach for a hash table whenever you need fast lookups by key: counting things, de-duplicating, caching, or checking membership. In an interview, "use a set/dict to make it O(1)" turns many O(n²) brute-force solutions into O(n). Just remember the O(1) is an average — say so, and mention collisions, to show you understand the trade-off.
Hash tables have no order. Do not rely on getting keys back in insertion or sorted order — for that you need a sorted structure. Also, the keys must be hashable (immutable): in Python you can use a string or tuple as a key, but not a list.
Practice
We insert a key that hashes to 17, into a table with 5 buckets. Which bucket does it land in?
1. Why is a hash-table lookup O(1) on average?
2. What is a collision?
3. If "dog" hashes to 11 and the table has 5 buckets, which bucket holds it?
4. When does a hash-table lookup degrade to O(n)?