Lesson 07: Stop Searching Every Item: The Hash Map Trick That Makes Lookups So Fast

Hash Maps and Hash Functions Explained Through Varastra's E-Commerce Platform — Learn How Keys Map to Storage Locations, Why Dictionary Lookups Average O(1), and What Happens When Two Keys Collide.

The interview insight: A fast lookup doesn't need to search every record. It needs an efficient way to find where the record should be stored.

Looking up an item in a list means checking one item after another. A hash map jumps straight to it. Here is how, in plain English, and the one case where the trick fails.

The problem at Varastra

Varastra is an online store for Indian ethnic wear. Every night at 11, a job matches payments to orders. The payment partner sends a file. Each payment has a reference code. Each order has the same code. The job finds the order for every payment, so finance can close the day.

On the first night of a big sale, the job ran for a very long time. Finance could not close the day until it finished. (This story is made up.)

Sam, a senior engineer, put the code on the screen. It had a loop over payments. Inside it was a loop over orders.

"This compares every payment with every order," Tara said. She was a new intern, and she had learned this lesson the hard way.

"How would you fix it?" Sam asked Dev.

"Use a dict," Dev said at once.

"Why does a dict help?"

Dev opened his mouth. He knew the answer. He could not explain it. "It just looks it up directly," he said.

"How?" Sam asked. Nobody answered.

Tara picked up a pencil and a sheet of paper. "Can I try?" she said. She drew some lockers.

What a hash map is

A hash map stores pairs. Each pair has a key and a value. You give the map a key, and it gives you the value back. In Python, a hash map is a dict.

by_ref = {"P001": 101, "P002": 102}
print(by_ref["P002"])      # 102

A set is a hash map with keys only. It answers one question: "Is this item inside?"

The locker picture

How can a lookup be fast? Think of a row of lockers.

A guard does not open every locker to find your bag. He turns your name into a locker number using a fixed rule. Then he walks straight to that locker.

That rule is a hash function. It turns a key into a number. Python uses the number to decide where to store the pair. To find the key later, it runs the same rule again and goes straight to the spot.

Look at the diagram. The key P002 goes through the hash function. The rule gives the number 5. The pair is stored in locker 5. Later, to find P002, run the same rule again. It gives 5 again. Go to locker 5. Do not open the other lockers.

The locker numbers in the picture are made up to teach the idea. Real Python is more complex inside. But the idea is the same: turn the key into an address, then go to the address.

Sometimes two keys give the same locker number. This is a collision. Python has its own way to handle collisions, and it costs a little extra time. We come back to this at the end.

The cost, measured

Back to the nightly job. Tara builds test files with n payments and n orders. She times both approaches.

def match_nested(payments, orders):
    result = []
    for ref in payments:
        found = None
        for order_ref, order_id in orders:
            if order_ref == ref:
                found = order_id
                break
        result.append(found)
    return result


def match_dict(payments, orders):
    by_ref = {}
    for order_ref, order_id in orders:        # one pass to build
        by_ref[order_ref] = order_id
    return [by_ref.get(ref) for ref in payments]   # one lookup per payment

Pause and predict

Before you look at the table: the nested loops took 0.065 seconds for 2,000 payments. How long for 4,000?

Answer: About four times longer, so around 0.25 seconds. That is the O(n²) shape.

Here are the results. Each time is the best of a few runs.

The nested loops grow about four times each time n doubles. That is the O(n²) shape.

Nobody ran the nested version for 200,000 payments. By the same shape it would take about 0.851 × (200,000 ÷ 8,000)² seconds. That is about 530 seconds, close to 9 minutes. That is an estimate. The dict version was timed and took 0.03 seconds.

Now put it in business terms. If the job takes 9 minutes tonight, it takes about 18 when the sale orders double. Finance waits. The next day's pickup list is late. (These consequences are part of the story, not data.)

These numbers were measured on one machine. They will differ on yours.

The cost line is: time O(n) on average to match n payments. Space O(n) extra for the map.

What each line does

by_ref = {}

This makes an empty map.

for order_ref, order_id in orders:
    by_ref[order_ref] = order_id

This reads each order once and stores it under its payment reference. Building costs n steps.

return [by_ref.get(ref) for ref in payments]

by_ref.get(ref) looks up the reference. If the key is missing, get returns None and does not raise an error. This runs once for each payment.

We spent memory to remember every order. In return, each lookup stopped being a scan. That is the whole idea: trade space for speed.

Try it

Try orders = [("P1", 10), ("P1", 20)] and payments = ["P1"]. What do match_nested and match_dict return?

match_nested returns [10], because it stops at the first match. match_dict returns [20], because the later order replaced the earlier one. Know which rule you want when the same key appears twice.

Three mistakes that fail quietly

Mistake 1: a key that is not unique. Tara tries a dict keyed by customer name. It sounds smart.

def orders_by_name_bad(orders):
    d = {}
    for name, order_id in orders:
        d[name] = order_id
    return d

print(orders_by_name_bad([("Anita Joshi", 1), ("Ravi Kale", 2), ("Anita Joshi", 3)]))
# {'Anita Joshi': 3, 'Ravi Kale': 2}

Three orders went in, but only two keys came out. Order 1 is gone. No error, no warning. A dict holds one value per key, and a repeated key replaces the old value.

Choose a key that is unique for what you need. Or store a list under each key.

def orders_by_name(orders):
    d = {}
    for name, order_id in orders:
        d.setdefault(name, []).append(order_id)
    return d

Mistake 2: a list as a key. Tara wants a key made of name and city.

d = {}
d[["Anita", "Leeds"]] = 1
# TypeError: unhashable type: 'list'

A key must keep the same hash for its whole life. A list can change, so Python refuses it. Use a tuple of plain values instead: ("Anita", "Leeds"). A tuple that holds a list inside is still unhashable.

Mistake 3: saving hash values. The hash() of a string changes from one program run to the next. Never save a hash value in a file or database.

Here is one more fact that surprises people. 1 and 1.0 are equal, so they are the same key.

d = {}
d[1] = "int"
d[1.0] = "float"
print(len(d), d[1])   # 1 float

When one lookup is not one step

Everything above is the average case. What if every key lands in the same locker?

Tara makes a class whose hash is always 1.

class SameHash:
    def __init__(self, v):
        self.v = v
    def __hash__(self):
        return 1
    def __eq__(self, other):
        return isinstance(other, SameHash) and self.v == other.v

Then she builds a set of n of them, and a set of n plain integers.

The SameHash column grows about four times each time n doubles. Each add must walk past every earlier key in the same locker. That is O(n) for each add, and O(n²) in total. The set still gives the right answer. It is just slow.

You will rarely meet this in real code. Built-in keys like integers, strings and tuples of those hash well. But now you know what "average case" means. In an interview, say:

"Lookups are O(1) on average. In the worst case, when many keys collide, they are O(n)."

When to reach for a hash map

1. The question is "have I seen this before?" Use a set.
2. For each item, you need to find its partner or match. Use a dict from the thing you saw to what you need to remember.
3. You search the same list again and again. Build a map once, then look up.

If none of these fit, a hash map may not help. Do not use one just because it is popular. If you look something up only once, a single pass is simpler.

Takeaway: A hash map turns a key into an address, so each lookup is one look on average. It costs extra memory. Always say "on average."