How Hash Maps Work 🗺️
Why a dictionary can find a key in roughly one step.
A hash map (dict, hash table) stores key-value pairs and finds any key in roughly O(1) time. The trick is turning the key into an array index.
The core idea
1. A hash function converts your key into a number.
2. That number maps to a bucket (an index in an internal array).
3. The value gets stored in that bucket — so lookup goes straight there.
def bucket_index(key, size):
return hash(key) % size # turn key into an array index# Conceptually:
buckets = [[] for _ in range(8)]
def put(key, value):
buckets[bucket_index(key, 8)].append((key, value))Collisions
Two keys can land in the same bucket. Maps handle this by chaining (storing a small list per bucket) or open addressing (probing for the next free slot). With a good hash function, collisions stay rare and lookups stay fast.
When it slows down
If too many keys crowd into too few buckets, lookups degrade toward O(n). Real implementations resize (rehash into a bigger array) once they get too full, keeping operations near constant time on average.
Get Marcelo Domingues’s stories in your inbox
Join Medium for free to get updates from this writer.
TL;DR: A hash map turns keys into array indices via a hash function, giving average O(1) lookup — collisions and resizing are the details that keep it honest.
Reach for a dict whenever you find yourself scanning a list to find one item.
