Hash Maps (How dict Works)

Why this lesson matters

You have already used Python’s dictionary and set. Both let you look something up almost instantly no matter how much data they hold. That speed comes from one idea, the hash map, which is the machinery under dict and set.

Understanding the hash map matters for two reasons. First, it explains the rules you have been asked to follow, such as “keys must be immutable,” so they stop feeling arbitrary. Second, hash maps are the single most useful tool for making slow code fast: a huge number of programming problems turn from O(n²) into O(n) the moment you reach for one. This lesson builds the structure from scratch, so that by the end you can picture exactly what happens when you write d[key].

A quick reminder on notation. Big-O describes how the work of an operation grows as the data grows. O(1) means “constant time,” the work does not grow with the size of the collection. O(n) means “linear time,” the work grows in proportion to the number of items n. We will use these labels throughout, and we will be careful to separate the average case from the worst case.

The problem a hash map solves

Suppose you have a pile of name-to-phone-number pairs and you want to find one person’s number. If the pairs sit in a list, the computer has no choice but to walk through them one at a time, comparing each name to the one you asked for, until it finds a match or runs out. That is O(n): with a million pairs, a miss costs a million comparisons.

We want to do better. Imagine instead a long row of numbered boxes, called slots. If we had a rule that said “the pair for this name always lives in box number 47,” then finding it would take no searching at all. We would compute the box number, walk straight to it, and read the value. That is O(1), constant time, regardless of how many pairs exist.

The whole trick is inventing that rule: a reliable way to turn a name into a box number. That rule is the hash function.

The hash function

A hash function takes a piece of data, called the key, and returns a fixed-size number, called its hash. A good hash function has two properties. It is deterministic: the same key always produces the same number. And it spreads keys out: different keys tend to produce different, well-scattered numbers.

Python has a built-in hash function called hash.

print(hash("Alice"))   # -> some large integer, e.g. 6182644...
print(hash("Alice"))   # -> the SAME integer every time (within one run)
print(hash("Bob"))     # -> a different integer
print(hash(42))        # -> 42 (small ints hash to themselves)

The exact numbers do not matter and, for strings, they change between separate program runs for security reasons. What matters is that within a single run the hash is stable and different keys land on different numbers.

The hash by itself is usually a huge number, far larger than the number of boxes we have. To turn it into an actual box number, we take the remainder after dividing by the number of slots. That remainder, from the % operator, is always in range 0 to slots - 1, which is exactly the set of valid box numbers.

num_slots = 8
key = "Alice"
slot = hash(key) % num_slots
print(0 <= slot < num_slots)  # -> True (always a valid slot)

So the full path from a key to a box is: key -> hash function -> big number -> % num_slots -> slot index.

flowchart LR
    K["key: 'Alice'"] --> H["hash function"]
    H --> N["big number<br/>6182644..."]
    N --> M["% num_slots (8)"]
    M --> S["slot 4"]

Buckets and collisions

There is a catch. We are squeezing an unlimited number of possible keys into a limited number of slots, so sometimes two different keys land on the same slot. Two keys mapping to the same slot is called a collision. Collisions are not a bug or a rare accident; with more keys than slots they are guaranteed. A hash map is only correct if it has a plan for them.

The most common plan is called separate chaining. Instead of storing a single pair in each slot, each slot holds a small list, called a bucket. When two keys collide, both pairs sit in the same bucket. To look a key up, you compute its slot, then walk the short list in that bucket comparing keys until you find yours.

flowchart LR
    subgraph table["slots"]
        S0["slot 0"]
        S1["slot 1"]
        S2["slot 2"]
        S3["slot 3"]
    end
    S1 --> B1["('Alice', 31)"]
    S3 --> B3a["('Bob', 25)"]
    B3a --> B3b["('Eve', 40)"]

Here "Bob" and "Eve" collided into slot 3, so slot 3’s bucket holds both pairs in a little chain. Looking up "Eve" means going to slot 3 and checking two entries instead of one.

There is a second common plan, open addressing, where there are no side-lists at all. If a key’s slot is already taken, the map probes for the next free slot by a fixed rule and stores the pair there; lookup follows the same probe sequence until it finds the key or an empty slot. Python’s real dict uses a form of open addressing. For understanding the behavior, the important point is shared by both approaches: a collision means a little extra work beyond the single jump.

Why lookup is O(1) on average and O(n) at worst

Now we can be precise about the speed.

In the average case, a good hash function scatters keys evenly, so each bucket holds only a handful of entries no matter how large the map grows. Computing the hash is constant work, jumping to the slot is constant work, and scanning a bucket of near-constant length is constant work. Total: O(1) on average for lookup, insert, and delete. This is the number you rely on in practice.

In the worst case, imagine a broken or adversarial situation where every key hashes to the same slot. Then one bucket holds all n entries and the others are empty. Looking a key up degrades to scanning a list of length n, which is O(n). The map is still correct, just slow. Real implementations work hard to keep this from happening, but it is why the honest complexity is “O(1) average, O(n) worst.”

Here is a tiny model that makes the buckets visible. It is not efficient or complete, it exists only to show the mechanism.

class TinyMap:
    def __init__(self, num_slots=8):
        # each slot starts as an empty bucket (a list of [key, value] pairs)
        self.buckets = [[] for _ in range(num_slots)]

    def _slot(self, key):
        return hash(key) % len(self.buckets)

    def put(self, key, value):
        bucket = self.buckets[self._slot(key)]
        for pair in bucket:            # key already here? update it
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])    # new key: add to the bucket

    def get(self, key):
        bucket = self.buckets[self._slot(key)]
        for pair in bucket:            # scan only this bucket
            if pair[0] == key:
                return pair[1]
        raise KeyError(key)

m = TinyMap()
m.put("Alice", 31)
m.put("Bob", 25)
print(m.get("Alice"))  # -> 31
print(m.get("Bob"))    # -> 25

get never scans the whole map. It scans one bucket, and if keys are well spread that bucket is tiny. That is the source of the O(1) behavior.

Insert and delete, step by step

Watch the buckets change as a short sequence of operations runs. Take a TinyMap with only four slots so collisions show up quickly. The slot for each key comes from hash(key) % 4; the specific slots below are chosen for illustration (real hashes are randomized per run), but the mechanism is exactly what the code does.

Here is the full state after every step. Each column is one slot’s bucket.

Notice the three distinct behaviors an insert can have: a brand-new key in an empty slot (step 1), a collision that lengthens an existing chain (step 3), and a repeat key that overwrites rather than adds (step 4). The count of stored entries only grows in the first two.

Step 3 is the interesting insert, because "Eve" collides with "Bob" in slot 3. Before, slot 3 holds one pair; after, it holds a two-link chain, and nothing else in the table moves.

Before put("Eve", 40):

flowchart LR
    S3["slot 3"] --> B["('Bob', 25)"]

After put("Eve", 40):

flowchart LR
    S3["slot 3"] --> B["('Bob', 25)"]
    B --> E["('Eve', 40)"]

The new pair is appended to the end of the bucket. No existing pair is touched or moved; the only change is one extra link on the chain in slot 3.

Deleting works the same way in reverse: go to the key’s slot, find the pair in that bucket, and unlink it. Step 5 removes "Eve" from slot 3, and the before-and-after mirrors the insert.

Before delete("Eve"):

flowchart LR
    S3["slot 3"] --> B["('Bob', 26)"]
    B --> E["('Eve', 40)"]

After delete("Eve"):

flowchart LR
    S3["slot 3"] --> B["('Bob', 26)"]

Only slot 3’s bucket changes; "Bob" stays exactly where it was. Here is the delete method that produces this, added to TinyMap:

    def delete(self, key):
        bucket = self.buckets[self._slot(key)]
        for i, pair in enumerate(bucket):
            if pair[0] == key:
                bucket.pop(i)      # unlink this pair from the chain
                return
        raise KeyError(key)        # not in its bucket -> not in the map

Like get, it scans only one bucket, so a well-spread map deletes in O(1) on average.

Load factor and resizing

How full a hash map is directly controls how often collisions happen. The load factor is a single number that measures this: the count of stored entries divided by the number of slots.

# load factor = number of entries / number of slots
# entries in 8 slots -> 6 / 8 = 0.75

A low load factor means many empty slots and short buckets, so lookups stay near O(1) but memory is spent on empty space. A high load factor means crowded slots and long buckets, so lookups slow down. The map is trading memory against speed, and the load factor is the dial.

To keep that dial in a good range, a hash map resizes. When the load factor crosses a threshold (Python’s dict uses roughly two-thirds full), the map allocates a bigger array of slots, often about double, and rehashes: it recomputes every existing key’s slot for the new size and reinserts it. Rehashing must recompute slots because the slot came from hash(key) % num_slots, and num_slots just changed.

A single resize is O(n) because it touches every entry. That sounds expensive, but it happens rarely, only when the map crosses a threshold, and it roughly doubles capacity each time. Spread across all the insertions that triggered it, the average cost per insert stays O(1). This “occasionally expensive, usually cheap, cheap on average” pattern is called amortized O(1), and it is the honest description of dictionary insertion.

Big-O of every operation

Here is the whole cost model in one place. The average column is what you rely on in practice; the worst column is the pathological all-in-one-bucket case.

Space is O(n): the table stores one entry per key plus some empty slots, and the number of slots stays proportional to the number of entries as it resizes. The one-line derivation for lookup: computing hash(key) is constant work, % num_slots is constant work, and scanning a bucket of expected length near one is constant work, so the total is a fixed number of steps that does not grow with n. The worst case replaces that short scan with a length-n scan when every key collides into a single bucket.

Why keys must be hashable and immutable

The rules you met earlier now have a clear cause.

A key must be hashable, meaning the hash function can turn it into a number. And in Python, hashable in practice means immutable, unable to change after it is created. Numbers, strings, and tuples of immutable things are hashable. Lists, dictionaries, and sets are mutable, they can change in place, so they are not hashable and cannot be keys.

d = {}
d["ok"] = 1          # string key: fine
d[(1, 2)] = "point"  # tuple key: fine
d[[1, 2]] = "bad"    # -> TypeError: unhashable type: 'list'

The reason is the mechanism itself. The map picks a key’s slot from its hash. If a key could change after being stored, its hash would change, so its correct slot would move, but the pair would still be sitting in the old slot. A later lookup would compute the new slot, look there, and find nothing. The value would be lost even though it is still in the table. Forbidding mutable keys guarantees the hash never changes, so a stored key stays findable. This is a rule the data structure needs to stay correct, not a stylistic preference.

Values have no such restriction. A value can be a list, a dict, anything; only the key feeds the hash function.

The connection to Python’s dict and set

Everything above is what dict actually is: a hash map from keys to values. Every d[key], key in d, d[key] = v, and del d[key] is a hash-and-jump into a slot, with collision handling underneath. The O(1)-average behavior you were told to trust is exactly the O(1)-average of the hash map.

A set is the same machinery with the values removed. It stores only keys and answers one question, “is this key present?”, by hashing to a slot and checking. That is why set membership is O(1) on average and why set elements must be hashable for the same reason dict keys must be.

seen = set()
seen.add("Alice")           # hash 'Alice', store in its slot
print("Alice" in seen)      # -> True   (hash and jump, O(1) average)
print("Nobody" in seen)     # -> False

counts = {}
for w in ["a", "b", "a"]:
    counts[w] = counts.get(w, 0) + 1   # each access is a hash-and-jump
print(counts)               # -> {'a': 2, 'b': 1}

When you use a set to strip duplicates or a dict to count things, you are using a hash map to replace an O(n) scan with an O(1) lookup. That substitution is one of the highest-value moves in everyday programming.

Common pitfalls

• Mutable keys. You cannot use a list, dict, or set as a dict key or set element. If the contents are fixed, convert to a tuple first: d[tuple(my_list)] = v.
• Assuming hashes are stable across runs. For strings and bytes, Python randomizes hashing between separate program runs (a security measure called hash randomization). Never save a hash value to a file and expect it to match next time, and never rely on the specific iteration order that hashing produces.
• Confusing “unordered mechanism” with dict order. A hash map has no inherent order, yet since Python 3.7 a dict preserves insertion order as a language guarantee layered on top. A set does not; never depend on the order you see when iterating a set.
• Expecting O(1) to mean “instant” or “always.” It is an average. A pathological set of keys, or a moment of resizing, can cost more. For interview and production reasoning, state it as “O(1) average, O(n) worst.”
• Mutating an object after using it as a key. Even a custom object used as a key must keep the same hash for its whole life in the map. Change what its hash depends on and you will “lose” the entry.
• Treating a collision as an error. Collisions are normal and expected. The map handles them; they only affect speed, never correctness.

Practice

1. Extend the TinyMap class with a delete(key) method that removes a key from its bucket and raises KeyError if the key is not present. Confirm that a later get on the deleted key raises KeyError.
2. Using hash(key) % num_slots, write a small loop that computes the slot for the strings "apple", "banana", "cherry", and "date" with num_slots = 4, and print each slot. Are any two forced into the same slot? Try again with num_slots = 16 and compare how the collisions change.
3. Explain in a sentence or two why inserting n items into a dictionary is O(n) total and not O(n²), even though the dictionary resizes several times along the way. Name the property that makes each insert O(1) on average.