Hashing, collisions and how Python dicts find their keys

Why it matters

The dict is the data structure you will reach for most often in Python. A dict answers the question "have I seen this before, and if so, what did I store with it?" A plain list can answer that question too, but only by checking every item one at a time. A dict answers it in about one step, no matter how many items it holds.

To use dicts and sets well you need to know why they are fast, what can make them slow, and what Python does behind the scenes. This lesson opens the box. You will compute a hash by hand, see how a key becomes a slot number, learn what a collision is, build a small hash table of your own, and read the rules Python follows for keys. The next lessons use these ideas to solve real problems.

Words you will need

• Key: the value you look up by, such as the name "Meera" in a dict of student scores.
• Value: the data stored with a key, such as the score 92.
• Hash function: a rule that turns a key into a whole number. Python calls it hash().
• Hash code: the number a hash function returns for one key.
• Bucket: one slot in a table's internal array. A key's hash code picks its bucket.
• Collision: two different keys end up needing the same bucket.
• Set: a collection of unique values with no order promise. It is a dict without values.

Start with the problem: searching takes time

Suppose you have a list of 1,000 student names and you want to know if "Meera" is in it. The simplest method starts at the first name, compares, and moves to the next one, until it finds the name or runs out of names. This is called linear search. In the worst case it looks at all 1,000 names. If the list doubles to 2,000 names, the worst case doubles too.

Programmers describe this growth with Big-O notation. The letter O stands for "order of", and the expression inside tells you how the number of steps grows as the input grows. A linear search is O(n), where n is the number of items. Doubling n roughly doubles the work.

Sorting the list lets you do better. With a sorted list, binary search checks the middle item and throws away half of the rest on each step. That takes about log2(n) steps, which is written O(log n). For 1,000 items that is about 10 steps. Sorting costs something up front, and the list has to stay sorted as you add and remove items.

A hash table aims for something stronger: O(1), which means the number of steps does not grow with n at all. "Constant time" is the usual name for it. The goal is to jump straight to the slot where a key lives, the same way you would walk to a numbered locker without checking the others.

Think about an array with eight slots, numbered 0 to 7. If you know that the name "Meera" lives in slot 5, you read slot 5 and you are done. The question that makes this work is how to get the number 5 from the name "Meera" without searching. That is the job of the hash function.

An everyday picture: the coat check

Think of a theatre coat check. You hand over your coat and receive a numbered ticket. The attendant hangs your coat on the hook with that number. When you come back, you show the ticket, and the attendant walks straight to the hook. Nobody checks every coat in the room.

A hash table works the same way. The key is the thing you hand over, like your coat. A hash function is the rule that turns the key into a number, like the ticket. That number, reduced to fit the size of the table, tells you the hook. In hash table language, a hook is called a bucket, and the table is an array of buckets.

There is one difference from a real coat check. Two coats can end up on the same hook if there are more coats than hooks, or if the rule happens to send them to the same place. In hash tables this is called a collision. We come back to collisions after we see how the number is made.

Step one: a hash function turns a key into a number

A hash function has two properties. It always gives the same number for the same input, and it spreads different inputs over a wide range of numbers. The first property makes lookup possible: if you can compute the number again later, you can find where you put the item. The second property keeps the buckets balanced.

In Python, the built-in hash() function returns the hash code of any value that can be a dict key. Numbers are easy to check:

print(hash(5))
print(hash(-1))
print(hash(True), hash(1), hash(1.0))

5
-2
1 1 1

An integer's hash is the integer itself, except that -1 gives -2, because -1 is reserved internally as an error signal. True and 1 have the same hash, and so does 1.0, because they are equal numbers.

For strings, Python does not give the same hash in every run. It adds a random seed each time the interpreter starts, so that attackers cannot easily build keys that all collide. Run this line twice and you get two different numbers:

python3 -c 'print(hash("cat"))'     # first run:  -2741736765797198187
python3 -c 'print(hash("cat"))'     # second run: 1367516067447729343

The numbers above are from one machine and one run. Yours will differ. That randomness is fine for a dict, because the dict only needs the hash to be stable while the program runs. It is a problem for a lesson that wants to show exact numbers, so the next example uses a hash formula you can check by hand. It is the same formula Java uses for String.hashCode.

The formula reads the letters one at a time. Each letter's character code is a number, so c is 99, a is 97 and t is 116. The Python function ord() returns that code. For each letter, the running total is multiplied by 31 and the letter's code is added:

total = 0
total = 0 * 31 + 99  = 99          (c)
total = 99 * 31 + 97 = 3166        (a)
total = 3166 * 31 + 116 = 98262    (t)

So the hash code of cat is 98262. The number 31 is a small odd prime. Multiplying by it mixes the letters together so that their order matters. Compare ab and ba:

"ab" = 97 * 31 + 98 = 3105
"ba" = 98 * 31 + 97 = 3135

Both words use the same letters, but they get different hash codes. If the hash only added the character codes, both would get 195, and every anagram would collide with every other anagram.

Step two: the hash code becomes a bucket number

A hash code can be negative or larger than the number of buckets. To pick a bucket, the table reduces it to a range from 0 up to the number of buckets minus one. The simple way is the remainder operator %. In Python, % always gives a result that is zero or positive when the divisor is positive, even if the number on the left is negative. With 16 buckets, 98262 % 16 is 6, because 16 * 6141 is 98256 and the remainder is 6.

Many real tables use a second step. They mix the high bits of the hash into the low bits, so that keys differing only in their high bits do not all land together. Then they keep the low bits with a mask. The operator >> shifts bits to the right, ^ flips a bit when exactly one of two bits is 1, and & keeps only the bits where both numbers have a 1. When the number of buckets is a power of two, such as 16, capacity - 1 is a mask of all ones: 15 is 1111 in binary.

The program below prints the hash code and the bucket for four keys, using the spread step and the mask for a 16-bucket table:

cat hash=98262 bucket=7
dog hash=99644 bucket=13
Aa hash=2112 bucket=0
BB hash=2112 bucket=0

The first line has hash code 98262, which matches the hand calculation. The bucket is 7, not 6, because the spread step changes the answer. Python's real dict does its own mixing and probing, so the bucket numbers in this program are not the ones a real dict uses. The idea is the same in both: a key becomes a number, the number becomes a bucket, and the same key always gets the same bucket.

The last two lines are a warning sign. Aa and BB have the same hash code, so they land in the same bucket. That is a collision, and the next section explains why it happens.

Trace one lookup from start to finish

Use the eight-bucket table from the next program and follow two lookups by hand. The steps are the ones the program takes, so this is a good way to check that you understand the code.

Look up cow first. Its hash code is 99 * 31 * 31 + 111 * 31 + 119, which is 95139 + 3441 + 119, or 98699. The table has 8 buckets, so the bucket is the remainder after dividing by 8. Since 8 * 12337 is 98696, the remainder is 3. The lookup goes to bucket 3, finds cow in the chain there, and returns its value, 5.

Now look up fish. Build the hash one letter at a time, which is faster for longer words. Start with f, which is 102. Then multiply the running total by 31 and add the next letter's code:

102
102 * 31 + 105 = 3267
3267 * 31 + 115 = 101392
101392 * 31 + 104 = 3143256

The remainder of 3143256 divided by 8 is 0, because 8 * 392907 is exactly 3143256. Bucket 0 holds fish, so the lookup returns 3.

Two details matter here. First, the lookup never looks at the other buckets. That is why the operation is fast. Second, the lookup compares keys with ==, not by the bucket alone. If the chain held a different key that shared the bucket, such as Aa and BB in the earlier example, the lookup would compare keys one by one until it found an exact match or reached the end of the chain.

Collisions: why they cannot be avoided

A collision happens when two different keys land in the same bucket. You might think a good hash function could avoid this completely. It cannot, for a simple reason called the pigeonhole principle: if you have more pigeons than holes, some hole gets two pigeons. Here the pigeons are keys and the holes are buckets. There are endlessly many possible strings, but a table with 16 buckets has only 16 holes. Even a perfect hash function would put some different keys in the same bucket.

The Aa and BB pair is a collision that comes from the formula itself. The character A has code 65 and a has code 97. The hash of Aa is:

65 * 31 + 97 = 2015 + 97 = 2112

The character B has code 66, so the hash of BB is:

66 * 31 + 66 = 2046 + 66 = 2112

Two different two-letter strings give exactly the same hash code. This is not a bug in Python. It is a property of any hash function that combines values with a multiplier. Because the same hash code gives the same bucket, the two keys collide.

Once a collision happens, the table needs a plan. There are two common plans.

Chaining. Each bucket holds a small list of entries. When two keys land in one bucket, the table adds the second entry to that list. To find a key, the table goes to the bucket and compares keys in the list one by one. The MiniTable below uses chaining, and it is the plan most people learn first.

Open addressing. There is no list. Each bucket holds at most one entry. If the slot is taken, the table probes other slots in a fixed pattern until it finds a free one. The simplest pattern is linear probing, which checks the next slot, then the one after that. CPython (the standard Python, written in C) uses open addressing for its dict and set, with a more spread-out probing pattern. Here is a table with eight slots, where A and B both hash to slot 3:

insert A: slot 3 is free, so A goes in slot 3
insert B: slot 3 holds A, so probe slot 4, which is free: B goes in slot 4
find B:   start at slot 3 (holds A, not B), probe slot 4, found B
find C:   C hashes to 3, probe 3 (A), probe 4 (B), probe 5 (empty), stop: C is not here

Open addressing uses less memory per entry, but deleting an entry is harder, because the empty slot you leave behind can stop a search too early. CPython handles this with special marker values for deleted slots.

What a real dict does

Python's dict is a hash table with a few rules that keep it fast. You do not write these rules yourself, but knowing them explains what you see when you use a dict.

• Insertion order. A dict remembers the order in which keys were added, and loops over it in that order. This has been part of the language since Python 3.7. The position of a key in a dict does not depend on its hash.
• Compact storage. CPython stores the keys and values in an array in insertion order, and keeps a separate, smaller index table of bucket positions. Iterating over a dict walks the array, so it is quick.
• Growth. When a dict is nearly full, CPython builds a bigger table and places every entry again. The exact growth rule is an internal detail that can change between Python versions. This lesson does not state a fixed threshold for Python, because the number is not part of the language promise.
• Equality. A lookup first compares the stored hash with the new key's hash. Only when the hashes match does it call ==. So an unequal pair with equal hashes still costs one == check, and an unequal pair with different hashes costs none.

If you know Java, dict is the closest match to HashMap. The big difference is ordering: a Python dict keeps insertion order, while Java's HashMap does not promise any order.

Step through the visualizer and watch where each key lands after its hash is computed. Look for the moment two keys share a bucket, and notice what the table does when a bucket already has an entry. Then answer three questions in your own words. Where does a new key go? What happens when the bucket is already taken? Why does the table grow when it gets full? If you can answer those, you understand the core of a hash table.

A small hash table you can run

Reading about chaining is one thing. Writing it is another. The program below is a small hash table with chaining and resizing. It is not CPython's dict, but it uses the same basic plan. Read it from the top. Each method has one job.

• string_hash gives the Java-style hash code for a string, so the numbers in the output are the same on every run.
• _index turns a key into a bucket number with %. Python's % keeps the answer zero or positive for a positive divisor, so a negative hash code is still safe.
• put walks the chain. If the key is already there, it replaces the value. If not, it adds a new pair at the front of the chain, and checks the size. When the size goes above 75 percent of the bucket count, it calls _resize.
• get walks one chain and returns the value, or None when the key is missing.
• _resize doubles the list of buckets and places every entry again.

resized to 8 buckets at size 4
0: fish=3
1: bird=4
2: (empty)
3: cow=5
4: dog=2
5: (empty)
6: pig=6 -> cat=1
7: (empty)
get dog = 2
get horse = None

The table starts with 4 buckets, so its limit is 3 entries. The first three words go in without a resize. When bird is added, the size becomes 4, which is above 3, so the table doubles to 8 buckets. That is the first line of output. The resize places each old entry again, because the bucket for a key depends on the number of buckets.

Look at bucket 6. It holds pig=6 -> cat=1. The put method adds each new pair at the front of its chain, so pig, which was added last, sits first. This is a small detail, but it explains why the order of entries inside a bucket is not something to rely on.

The line get dog = 2 finds dog in bucket 4 and returns its value. The line get horse = None computes a bucket, finds no horse in the chain there, and returns None. Python's None is the value that means "nothing here", and the next section shows what a real dict does instead.

The program does not remove entries, and it does not handle very long chains. A real table needs both. The core plan is the same: compute a number, pick a bucket, walk a short chain, grow when the table gets full.

Keys must follow the equality and hash rules

The MiniTable works for strings because the string type already defines equality and hashing. When you use your own class as a key, you must give it the same two behaviours. Python expects two rules.

1. If a == b is true, then hash(a) and hash(b) must return the same number.
2. The hash of a key must not change while the key is in the dict.

The first rule is the one beginners break most often. Suppose you write a BadPoint class with x and y, and you define __eq__ so that two points are equal when their coordinates match. Python then sets __hash__ to None for that class. That means instances are unhashable (hash() cannot give them a hash code), and a dict refuses them. The program below shows the error, then the fix.

TypeError: cannot use 'BadPoint' as a dict key (unhashable type: 'BadPoint')
good: home

The BadPoint class defines equality but no hash, so the dict refuses it at the moment you try to use it as a key. This is a clear error, and it is better than the silent wrong answer that Java gives in the same situation. If you want a class that is hashable, you have two choices. You can define __hash__ yourself, returning hash((self.x, self.y)) so that it uses the same fields as __eq__. Or you can use a dataclass with frozen=True, which generates both methods and stops you from changing the fields. The Point class above does the second.

The second rule matters for mutable keys. A key is mutable when you can change its values after you add it. If a key's hash changes while it sits in the dict, the entry stays in the bucket chosen by the old hash. A lookup with the new hash looks in a different bucket and misses the entry. The next program shows the effect with a class whose hash depends on a field that can change.

after change: None
keys still stored: ['blue']

The entry was stored under the hash of "red". After the change, tag has the hash of "blue", so get starts in another bucket and returns None. The key is still in the dict, which is why the second line shows it. The rule of thumb is simple: use immutable keys, such as strings, numbers, tuples of immutable values, frozen dataclasses, and do not change a key after you insert it.

Python's built-in list is not hashable at all, so a list cannot be a key. A tuple can be, if everything inside it can be hashed:

try:
    store = {[1, 2]: "saved"}
except TypeError as error:
    print("TypeError:", error)
 
print({(1, 2): "saved"}[(1, 2)])

TypeError: cannot use 'list' as a dict key (unhashable type: 'list')
saved

Iteration order is insertion order for dicts

Many beginners expect a Python dict to print its entries in the order they were added. For dicts, that is true, and you can rely on it. The order of a set is different. A set walks its internal table, so the order depends on the hash values and the table size. The next program shows both.

{'banana': 30, 'apple': 80, 'cherry': 120, 'date': 45}
['banana', 'apple', 'cherry', 'date']
{1, 17, 3, 40, 8, 25}
[9, 2, 1]

The dict lines keep the insertion order, which is the order the code added them. The set lines are not sorted and are not in insertion order. A set of small integers often looks sorted, because the hash of a small integer is the integer itself, so the slot for each number is close to its value. The [9, 2, 1] line shows that this is not a rule. If you need sorted output, use sorted(...). If you need insertion order from a set, you cannot get it from set; use a dict with keys and None values, or a list.

Do not change a dict while you loop over it. Adding or removing a key during a for loop raises an error:

scores = {"a": 1, "b": 2}
for name in scores:
    if scores[name] == 1:
        del scores[name]

RuntimeError: dictionary changed size during iteration

Loop over list(scores) instead, or build a new dict. Lesson 11 covers this in detail.

Cost summary

Here is the cost table to remember. The average case assumes the hash function spreads keys well and the table is not too full.

The worst case is rarely the one you hit in practice, but interviewers ask about it. A bad hash function, or keys chosen by an attacker to collide, can make every key share one bucket. Python's dict has no tree buckets like Java's HashMap does, so the worst case is O(n) and not O(log n). The randomized string hash is one of the defences against attacks of this kind.

Common mistakes and the messages you will see

Mistakes with dicts often fail loudly, which is good, because the message points at the cause. Here are the ones you will meet most.

Mistake 1: reading a key that is not there. Using d[key] for a missing key raises KeyError:

counts = {}
counts["x"] += 1

Traceback (most recent call last):
  File "example.py", line 2, in <module>
    counts["x"] += 1
    ~~~~~~^^^^^
KeyError: 'x'

Read the last line first. It names the missing key. The fix is counts.get("x", 0) when you only want a value, or counts["x"] = counts.get("x", 0) + 1 when you want to store one. Lesson 15 shows Counter and defaultdict, which handle this pattern for you.

Mistake 2: get returns None and the code uses it as a number. dict.get returns None when the key is missing. If you then add a number to None, Python raises an error:

scores = {"ana": 90}
print(scores.get("bo") + 5)

TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'

The fix is a default value: scores.get("bo", 0) + 5.

Mistake 3: defining __eq__ but not __hash__. The error is TypeError: cannot use 'BadPoint' as a dict key (unhashable type: 'BadPoint'). The fix is in the equality and hash section: define both, or use a frozen dataclass.

Mistake 4: changing a key after you add it. This gives a wrong None from get, and it appears only after some code changes a field. Use immutable keys.

Mistake 5: comparing values with is. The is operator checks whether two names refer to the same object in memory. The == operator checks whether the values are equal. Dicts use == for keys, so your own checks should too:

a = "cat"
b = "".join(["c", "a", "t"])
print(a == b, a is b)

True False

The result of a is b depends on how Python stores strings internally, so do not use is to compare text or numbers. Use is None for the single check where None is the right answer.

Debugging walkthrough: my dict forgets a seat

Suppose you write a Seat class with row and number fields, use it as a dict key, and the lookup says the seat is missing. Follow this order. It finds the cause in a few minutes.

from dataclasses import dataclass
 
 
@dataclass
class Seat:
    row: int
    number: int
 
 
booked = {Seat(3, 14): "Ravi"}
print(booked.get(Seat(3, 14)))

TypeError: cannot use 'Seat' as a dict key (unhashable type: 'Seat')

1. Read the error. The class is unhashable, so the dict will not accept it. This is the simplest possible cause, and the error says it outright.
2. Check the decorator. A plain @dataclass generates __eq__ but sets __hash__ to None, because a mutable object should not be a key. Add frozen=True if seats never change after they are created.
3. Check the fields. If you write __hash__ yourself, use the same fields that __eq__ compares. A hash that uses fewer fields is still correct. A hash that uses an extra field is wrong, because equal objects can then get different hashes.
4. Check mutability. If the lookup works once and then fails after some code runs, a field changed after insertion. Search for places that assign to the fields.
5. Check the lookup key type. A Seat is not equal to a tuple (3, 14), even if the numbers match. Look up with the same kind of object you inserted.

The fixed version is @dataclass(frozen=True). Running it prints Ravi. This order follows the rules. It starts with the simplest check, the error message, and works outward to the cause.

Edge cases to know

A dict accepts None as a key and as a value. get cannot tell "missing" from "stored as None" on its own, so use in when the difference matters.

7 True None

The first value is the value stored under the None key. The second is True, because "x" is a key in the dict, even though its value is None. The third is None, because that is the stored value.

A dict literal with a repeated key does not raise an error. Python keeps the last value:

{'a': 2}

Also note that Python treats numbers that are equal as the same key. 1, 1.0 and True are equal, so they share one entry:

{1: 'bool'}

The key stays as 1, and the value is replaced twice, so the last value wins.

An empty dict is also a normal case. get on an empty dict returns None, and looping over it does nothing. A function that takes a dict should not assume it has entries.

Interview angle: explain the O(1) claim

Interviewers often ask, "Why is a dict lookup O(1)?" A strong answer is short and precise. Say that the hash function turns the key into a bucket index in constant time, that the table grows when it becomes full enough, so each bucket holds only a few entries on average, and that a lookup compares only a few keys. Then say the average holds when the hash spreads keys well, and that the worst case is O(n).

Expect a follow-up: "What if all keys collide?" Answer that every lookup then scans one long chain or probes through many slots, which is O(n). Mention that a good __hash__ is the first line of defence, and that CPython randomizes string hashes so that attackers cannot easily pick colliding keys.

Expect another: "How would you implement a hash map?" The answer is the MiniTable from this lesson, plus resizing and deletion. Practise writing it from memory. The exercises ask you to add remove to it.

Real-world uses

Dicts and sets sit under many everyday tools. A web framework keeps request headers in a dict from header name to value. A spell checker keeps a set of known words. A compiler keeps a symbol table from variable names to their types. A database keeps in-memory indexes that map keys to row positions. A cache, which you will meet in lesson 4, keeps recent answers in a dict so that repeated questions are fast.

Each of these uses depends on the same properties. The key must be stable, == and hash must agree, and the caller must not depend on the order of a set. When a program misbehaves in one of these places, the cause is usually one of the mistakes in this lesson.

Practice

Try each exercise before you open its answer. Use paper for the hash calculations, and check them with a short program afterwards.

1. Compute the hash code of ab and of ba by hand using the formula in this lesson. Check your answers with string_hash from the MiniTable program. Hint: start with 97 * 31 + 98.

Show the answer

ab gives 3105 and ba gives 3135. Both come from 97 * 31 + 98 and 98 * 31 + 97. Calling string_hash("ab") and string_hash("ba") prints the same two numbers.

2. A simplified table uses hash % 16 for the bucket. What bucket does hash 77 go to? Hint: 77 - 4 * 16.

Show the answer

Bucket 13. Four sixteens make 64, and 77 - 64 is 13. In Python, 77 % 16 also gives 13.

3. The MiniTable in this lesson starts with 4 buckets and resizes when the size goes above 75 percent of the bucket count. What is the limit for 4 buckets, and which insert triggers the first resize? Hint: 4 * 0.75.

Show the answer

The limit is 3 entries. The fourth insert makes the size 4, which is above 3, so that insert triggers the resize to 8 buckets.

4. Your friend says Aa and BB collide because the hash function is bad. Explain why the collision is a property of the formula, not a mistake in Python. Hint: think about the multiplier 31 and the letters A and B.

Show the answer

Both two-letter strings give 2112. The formula is first * 31 + second, and A is one less than B, so A times 31 plus a equals B times 31 plus B. The formula is doing exactly what it was designed to do, and any formula that combines values with a multiplier has pairs like this.

5. Add a Pair class with two integer fields and define __eq__ only. Predict what happens when you put a Pair in a dict, then run it. Then add a __hash__ that returns hash((self.x, self.y)) and run again.

Show the answer

The first run raises TypeError: cannot use 'Pair' as a dict key (unhashable type: 'Pair'), because defining __eq__ sets __hash__ to None. After adding __hash__, the dict accepts the object, and get with an equal pair returns the stored value.

6. Predict how many resizes the MiniTable does when it receives 100 entries. Write down each size where a resize happens. Hint: the limits are 3, 6, 12, 24, 48 and 96.

Show the answer

Six resizes, to 8, 16, 32, 64, 128 and 256 buckets. The resize happens on the insert that makes the size 4, 7, 13, 25, 49 and 97. You can count the lines the program prints to check.

7. Write a function count_used_buckets(table) that returns the number of buckets with at least one entry in the MiniTable. Hint: count the chains that are not empty.

Show the answer

def count_used_buckets(table):
    return sum(1 for chain in table.buckets if chain)

An empty list is false in a condition, so if chain keeps only the buckets that have entries.

8. Explain why iterating over a set of small integers often looks sorted, and why you cannot rely on that. Hint: think about the hash of a small integer.

Show the answer

The hash of a small integer is the integer itself, so each number tends to land in a slot close to its value. That often gives a sorted-looking order. The order still depends on the table size and on the values, as the [9, 2, 1] line in this lesson shows, so you must not rely on it. Use sorted() when you need order.

9. A key object is changed after insertion, and get returns None. Explain what happened in two sentences, using the word bucket.

Show the answer

The entry was placed in the bucket chosen by the old hash. After the change, the new hash points to a different bucket, so get searches the wrong bucket and does not find the entry.

10. Write the error you would see if n = scores["x"] runs on a dict with no key "x". Then write one line that fixes it without changing the dict's contents. Hint: get takes a default value.

Show the answer

The error is KeyError: 'x'. The fix is n = scores.get("x", 0), which returns 0 when the key is missing and does not add anything to the dict.