PHASE 4Beginner ~28 min· topic 5 of 11

Topic 4.5

How Dictionaries Work: Hashing

In one line

A dictionary turns each key into a number called a hash, and uses that number to jump straight to a slot in a table, so lookup takes about the same time however big the dictionary is. This is why keys must be hashable (unchanging) and why a list cannot be a key.

Think of it like this

A library with numbered shelves. If the librarian had to walk past every book to find yours, a big library would be slow. Instead, the book's title is turned into a shelf number by a fixed rule, and the book is always put on that shelf. To find it later, apply the same rule and walk straight to the shelf. A Python dictionary does exactly this, and the fixed rule is called a hash function.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Hash: A whole number that Python computes from a value. Equal values give equal hashes.
Hash function: The rule that turns a value into its hash number.
Hash table: An array of slots where each item is stored at a slot chosen by its hash.
Hashable: Has a hash that never changes, so it can be a dictionary key or set member.
Collision: Two different keys that map to the same slot.
Probe: Looking at the next candidate slot after a collision.
Load factor: How full the table is. When it gets too full, Python builds a bigger table.
O(1): "Constant time": the work does not grow when the data grows.

Step by step

01What hash() gives you

Integers hash to themselves, with two exceptions worth knowing: hash(-1) is -2 (CPython reserves -1 as an error signal), and numbers beyond a fixed size are reduced by a large prime (on a 64-bit build, 2**61 - 1). 1, 1.0 and True are equal, so they have the same hash and are the same key in a dictionary. Strings have a hash too, but it changes between runs, so never print it or store it.

main.pywhole filepython

print(hash(42))                    # 42
print(hash(1) == hash(1.0) == hash(True))   # True
d = {1: "one"}
d[1.0] = "uno"                     # same key as 1
print(d)                           # {1: 'uno'}

02A tiny hash table by hand

Here is the idea in plain code with 8 slots. The rule is "slot = key % 8" (the remainder after dividing by 8). Each slot holds a small list so that colliding keys can share a slot. Real dictionaries do it more cleverly, but the principle is the same: compute the slot, go straight to it.

main.pywhole filepython

table = []
for _ in range(8):
    table.append([])

for key in [3, 11, 19, 5, 42]:
    slot = key % 8
    table[slot].append(key)
print(table)

A tiny hash table by handdiagram

Rendering diagram…

03Looking up: go to the slot, then compare

To find 19, compute its slot (3), then look only at the few keys stored there, not at the whole table. With 5 keys in 8 slots most slots have 0 or 1 keys, so this is about one step. This is why dictionary lookup does not slow down as the dictionary grows, as long as the table is resized to keep slots mostly empty.

04Why the key must not change

Imagine a list could be a key. You store it under [1, 2], which hashes to slot 5. Then you append 3 to the list. Its hash would now point to a different slot, say slot 2. When you look up the list, Python goes to slot 2 and finds nothing, although the entry is still sitting in slot 5. The entry is lost. Python prevents this by refusing to hash anything mutable.

main.pywhole filepython

route = ("Delhi", "Mumbai")      # tuple: hashable
cost = {route: 1400}
print(cost[("Delhi", "Mumbai")])

# cost[["Delhi", "Mumbai"]] = 1  # TypeError: unhashable type: 'list'

05Equal means same hash

Two objects that compare equal must have the same hash, otherwise Python would look in different slots for what it considers the same key. For your own classes you define __eq__ and __hash__ together, based on the same fields. A class is a blueprint for your own kind of object, and Phase 8 teaches it. Do not worry about every line of the code below yet: the point is the last two methods.

main.pywhole filepython

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __hash__(self):
        return hash((self.x, self.y))

06Hash randomisation and order

Run "print(hash('abc'))" twice and you get different numbers. That is intentional security (see the Pro section). The result: a set of strings may print in a different order on every run. A dictionary does not have this problem because it keeps insertion order separately from the hash table. If you need a set printed in a stable order, print sorted(the_set).

Try it yourself

1
Create a collision
In the second example, add the key 27 and then 35. Predict their slots first. Which slots now hold more than one key?
2
Break equality
In the third example, change __hash__ to return 0. Everything still works, but think: what would happen to lookup speed if every key landed in slot 0? (All keys collide, so lookup degrades to a scan: O(n).)

Code & diagrams

Hashable and unhashable values New tab

The last line ends with an error on purpose. Read the message: it names the type that cannot be hashed.

Expected output

hash(42): 42
1, 1.0 and True share a hash: True
equal tuples, equal hashes: True
equal strings, equal hashes: True
one key, last value wins: {1: 'yes'}
Traceback (most recent call last):
  File "main.py", line 11, in <module>
    hash([1, 2])
    ~~~~^^^^^^^^
TypeError: unhashable type: 'list'

A hash table by hand, with collisions New tab

Add the key 27 and predict which slot it lands in (27 % 8) before you run.

Expected output

slot 0 -> []
slot 1 -> []
slot 2 -> [42]
slot 3 -> [3, 11, 19]
slot 4 -> []
slot 5 -> [5]
slot 6 -> []
slot 7 -> []
looking for 19 in slot 3 -> True
looking for 42 in slot 2 -> True
looking for 7 in slot 7 -> False

Equal objects need equal hashes New tab

Classes are taught in Phase 8. For now see the result: two different Point objects that are equal work as the same dictionary key.

Expected output

a == b: True | same object: False
lookup with b: home
distinct keys: 1

A stable cache key for a prompt New tab

`hash("text")` changes on every run, so it is the wrong tool for a cache that is saved to disk. `hashlib.sha256` gives the same fingerprint everywhere, every time. (`.encode("utf-8")` turns text into bytes, which is what `sha256` reads; Topic 6.1 teaches the import.)

Expected output

fingerprint: 82d3e453ffb434b6 | length: 64
same prompt, cache hit: True
different prompt, cache hit: False

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Use a list as a dictionary key

Put a list inside the braces as a key.

main.pywhole filepython

d = {[1, 2]: "numbers"}

terminal

$ python main.py

── what you'll see ──

Traceback (most recent call last):

File "main.py", line 1, in <module>

d = {[1, 2]: "numbers"}

^^^^^^^^^^^^^^^^^^^

TypeError: unhashable type: 'list'

Break #2

Put a set inside a set

Try to store a set (a collection of unique items; Topic 4.6 teaches it) as a member of another set.

main.pywhole filepython

groups = {{1, 2}, {3}}

terminal

$ python main.py

── what you'll see ──

Traceback (most recent call last):

File "main.py", line 1, in <module>

groups = {{1, 2}, {3}}

^^^^^^^^^^^^^

TypeError: unhashable type: 'set'

Myth vs fact

Myth

A dictionary searches through its keys one by one.

Fact

It computes a slot from the key's hash and goes straight there. The cost does not grow with the size (on average).

Myth

Different keys always have different hashes.

Fact

Collisions are normal and handled. Only the opposite is guaranteed: equal keys have equal hashes.

Myth

hash('abc') is a stable fingerprint I can store in a file.

Fact

String hashes are randomised per run on purpose. For a stable fingerprint use the hashlib module from the standard library.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
CPython's dict uses open addressing with a pseudo-random probe sequence, stores entries in a compact array in insertion order, and keeps a separate small index array pointing into it. This split design (the compact layout is the default since Python 3.6) saves memory and is the reason for guaranteed order.
▸
Worst case, many colliding keys make lookup O(n). Hash randomisation (on by default for strings and bytes in Python 3) defends against "hash flooding" attacks, where a client sends many keys that collide on purpose. You can fix the seed with the PYTHONHASHSEED environment variable when you need repeatable runs in tests.
▸
Dictionary and set resizing is the reason a single d[k] = v can occasionally take much longer than usual. The cost averages out (amortised O(1)). For latency-sensitive code, pre-size by building the dictionary once rather than growing it in a hot path.
▸
Lookup compares identity first, then equality: after the hashes match, CPython checks key is stored_key and only then calls ==. That is why nan (which is not equal to itself) can be found again if you use the very same nan object, and why a slow __eq__ is skipped for the common case of looking up the same object. In your own __eq__, return NotImplemented (not raise) when other is a different type, so Python can try the other side; the version in this topic is short on purpose. Topic 8.7 covers the full contract.
▸
Because string hashes change on every run, never use hash() for anything that must be stable: file names, shard choices, cache keys saved to disk, or train/test splits. Use hashlib (for example hashlib.sha256(text.encode()).hexdigest()), or a seeded, documented hash. The last example below shows it. Remember also that a dict key lookup costs one hash() call, and the hash of a str is cached on the string object, so repeated lookups with the same string do not rehash it.
▸
In AI work, caching model calls by prompt is just a dictionary keyed by the prompt string (or a hash of it), which relies on exactly this mechanism. functools.cache is a dictionary keyed by the function's arguments, which is why the arguments must be hashable.

Remember this

1
A hash is a whole number that Python computes from a value with the built-in hash(). The important rule: equal values must give equal hashes. So hash("abc") is always the same within one run of a program, and hash(1) == hash(1.0) == hash(True) because 1 == 1.0 == True. Different values usually give different hashes, but not always.
2
The dictionary keeps a table of slots (a row of numbered boxes in memory). To store a key, it computes the hash and turns it into a slot number (roughly, the remainder after dividing the hash by the number of slots). Then it puts the key and value there. To look a key up, it computes the same hash, goes to the same slot, and checks whether the key found there equals the one you asked for. That is why lookup is O(1) on average: a fixed number of steps, not a search.
3
Sometimes two different keys land in the same slot. This is called a collision. It is normal and handled: Python checks the next probe slot until it finds a free one or the matching key. Keys also store their full hash, so Python first compares the cheap numbers and only calls == when the hashes match. When the table gets about two-thirds full, Python builds a bigger table and re-inserts everything, which is why growth is smooth on average.
4
For this to work, a key's hash must never change while it is in the dictionary. If it could, the key would be sitting in the wrong slot and could not be found. So keys must be hashable, which in practice means immutable: ints, floats, strings, booleans, None, and tuples (or frozensets) whose items are themselves hashable. Lists, dictionaries and sets can change, so hash([1, 2]) raises TypeError: unhashable type: 'list'.
5
Your own classes (Phase 8 teaches them: a class is a blueprint for making your own kind of object) are hashable by default, and two different objects are never equal. __eq__ is the special method that decides what == means for a class. If you define __eq__ to say two objects are equal, you must also define __hash__ so that equal objects hash equally; Python sets __hash__ to None (unhashable) if you define __eq__ alone. The rule to remember: **if a == b then hash(a) == hash(b)**.
6
String hashes are randomised on purpose: every time Python starts, it picks a secret random starting number (a seed), so hash("abc") is different from one run to the next. This stops attackers from sending thousands of keys that all collide and slow a server to a crawl. A consequence for you: **never rely on the order of a set of strings** or on printed hash values; sort or use dictionaries, which keep insertion order. Small non-negative integers hash to themselves, which is why sets of small ints often look sorted. Do not depend on that either.

Explain it without notes

Why is dictionary lookup O(1) on average?

Why can't a list be a dictionary key, but a tuple can?

What is a hash collision, and how does Python handle it?

If you define __eq__ on a class, why should you also define __hash__?

Is dictionary lookup always O(1)? What could make it slow, and what does Python do about it?

Practice

Create d = {1: "int", 1.0: "float", True: "bool"} and print it and its length. Explain why the length is not 3.

Make a dictionary that maps grid coordinates to names: (0, 0) is "start" and (2, 3) is "exit". Print the name at (2, 3).

Write a loop that puts the numbers 10, 17, 25, 33 into a table of 5 slots (lists) using number % 5, then print the table.

Trade-offs

↔
Speed for memory and order-by-key. A hash table answers "is this key here?" in constant time, but it keeps spare slots empty and cannot answer "what is the next key in sorted order?" without sorting.
↔
Immutable keys are a restriction that makes the speed possible. You cannot use a changing object as a key. The workaround (convert to a tuple, or use an id) is cheap and keeps the guarantee.

Done when you can

Done when you can explain a hash table with the library-shelf analogy.
Done when you can say why equal values must have equal hashes.
Done when you can explain why lists, dicts and sets are unhashable and tuples may be hashable.
Done when you can explain a collision and why average lookup is still O(1).
Done when you can say why a set of strings should be printed with sorted(...).

Command Palette

Words you'll meet

Step by step

01What hash() gives you

02A tiny hash table by hand

03Looking up: go to the slot, then compare

04Why the key must not change

05Equal means same hash

06Hash randomisation and order

Try it yourself

Create a collision

Break equality

Code & diagrams

Break it on purpose

Use a list as a dictionary key

Put a set inside a set

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can