You write ages["cat"] in Python and the answer comes back at once, even if the dictionary holds a million names. Nobody went through them one by one. So how does Python know where to look? The trick is called a hash table, and once you see it, a huge part of everyday programming makes sense.

The problem: finding a name in a long list

Imagine a notebook of pet names and ages, written in the order you met each pet. To find "cat" you have to start at page one and read until you hit it. With 10 pets that is fine. With a million, you may read a million pages. Computer scientists call that linear time: double the data, double the work.

A hash table avoids the reading. Instead of searching for the name, it calculates where the name must be stored.

Step 1: turn the key into a number

The name you look things up by is the key ("cat"). A hash function turns any key into a number. The same key always gives the same number. Real hash functions are carefully designed; here is a deliberately simple toy that adds up the character codes of the letters:

def toy_hash(key):
    total = 0
    for ch in key:
        total += ord(ch)   # ord("c") is 99, the code for that letter
    return total

For "cat" that is 99 + 97 + 116 = 312.

Step 2: turn the number into a bucket

The table is a row of numbered slots called buckets. We squeeze the big number into the available slots with the remainder operator %. With 8 buckets, 312 % 8 is 0, so "cat" goes in bucket 0. To look it up later, repeat the same two steps and open bucket 0 directly. No scanning.

Try it yourself

Collisions: when two keys want the same bucket

Try inserting "act". It uses the same letters as "cat", so the toy hash gives the same number, and both keys land in bucket 0. This is a collision, and every hash table has to handle them, because there are far more possible keys than buckets.

One simple fix is what the demo shows: each bucket holds a short list, and a lookup checks the keys in that list one by one. Here is the whole idea in Python:

buckets = [[] for _ in range(8)]

def put(key, value):
    i = toy_hash(key) % 8
    for pair in buckets[i]:
        if pair[0] == key:      # key already there: update it
            pair[1] = value
            return
    buckets[i].append([key, value])

def get(key):
    i = toy_hash(key) % 8
    for k, v in buckets[i]:
        if k == key:
            return v
    return None

put("cat", 3); put("act", 7); put("dog", 5)
print(buckets)
print(get("act"), get("cat"), get("emu"))

Running it prints:

[[['cat', 3], ['act', 7]], [], [['dog', 5]], [], [], [], [], []]
7 3 None

Notice that finding "act" only meant checking two keys, not every key in the table.

Why it is fast, and when it is not

If the hash function spreads keys evenly, each bucket stays short, so a lookup does a little arithmetic and checks a handful of keys. That is why the average cost does not grow as the table grows. Real tables keep this true by resizing: when they get crowded, they move everything into a bigger set of buckets.

The worst case is a bad hash function that sends everything to one bucket. Then the table degrades into a plain list. Try inserting lots of keys with the same letters in a different order in the demo and watch one bucket fill up.

What this means for your Python code

A Python dict and a set are both built on this idea, so key in my_dict stays quick on large data, while x in my_list scans the list. Two details worth knowing, as of Python 3.13:

First, keys must be hashable, meaning they have a hash that never changes. Strings, numbers and tuples of them qualify. A list does not, because you can edit it, which would change its hash and strand it in the wrong bucket:

{[1, 2]: "x"}
# TypeError: unhashable type: 'list'

Second, Python does not use my toy hash. It uses its own, and for strings the result is deliberately different on each run of the program (a security measure), so never depend on the actual number. CPython also resolves collisions differently from the lists in this demo (it probes for another free slot in the same table), but the core idea is the same: calculate where the key lives, then check a very small number of places.

Next time you write ages["cat"], picture that little calculation: add, remainder, open the bucket.