Hash collisions in Python

Why this matters

Suppose you keep a list of ten thousand customers and you need to find one by email address. If you check each entry from the top, the search may look at all ten thousand. A hash table is a container that finds a key in about one step, most of the time, no matter how many entries it holds. Python's dict and set are hash tables.

Interviewers often ask for a lookup "in constant time". The honest answer depends on collisions, which this lesson explains. You will see how a hash table stores keys, what a collision is, what a collision costs, and why one bad rule for computing a key's number can turn a fast container into a slow one.

The earlier lessons of this module covered lists, deques and the dict and set in general. The next lesson, on custom keys, shows how to make your own class work as a key. This lesson stays inside the table.

Words you need first

A key is the value you search by. In a phone book the key is the name. A value is the data attached to the key, such as the phone number. A dict stores pairs of key and value. A set stores keys only, with no values.

A hash is a whole number that Python computes from an object. The built-in function hash(x) returns it. For an int, the hash is the number itself. For a str, the hash is computed from the characters. A hash is not a unique label. Different objects can return the same number, and that is where collisions come from.

A slot is one numbered place inside the table. A slot holds one entry when all is well. The index is the slot number, from 0 up to the size of the table minus 1.

A collision happens when two different keys want the same slot. A collision is normal. It is not an error. Python handles it, but it costs time.

The hash function is the rule that turns a key into a slot index. Python has two steps. First, hash(key) gives a whole number. Second, the table uses the low bits of that number to pick a slot. For a table of 16 slots, the slot is hash & 15, which keeps the last four bits of the number.

Python's string hash changes each run

Python randomises the hash of strings each time the interpreter starts, so hash("Aa") gives a different number on each run. That is a safety feature, so that a program cannot be slowed down on purpose. It also means the exact numbers for strings cannot be checked against a fixed value.

To show the idea of a string hash with fixed numbers, this lesson uses the rule that Java uses for strings. The rule is written in plain Python below. It is not what the dict uses, but it shows exactly how two different strings can produce the same number.

An example with filing drawers

Think of a filing cabinet with 16 drawers, numbered 0 to 15. When you file a letter, you read its name, apply a fixed rule that turns the name into a drawer number, and put the letter in that drawer. When you want the letter back, you apply the same rule to the same name, open that one drawer, and look through the few letters inside.

The cabinet works well when the letters are spread across the drawers. Most drawers then hold zero or one letter. Finding a letter means opening one drawer and checking one or two papers.

The cabinet works badly when the rule sends almost every letter to drawer 3. Drawer 3 then holds thousands of papers. Every search becomes a search through that one drawer, and the cabinet is no better than a single heap of paper.

A dict is the same cabinet. The hash function is the rule. The slot is the drawer. A good hash function spreads keys across slots. A bad one piles them up.

How a table picks a slot

Here is the first step for storing a key in a table with 16 slots. Suppose the hash of the key is 2112.

1. Python computes hash(key). For this example the result is 2112.
2. The table takes the low four bits of the number with & 15. The number 15 is 1111 in binary, so & 15 keeps only the last four bits. The result is a number from 0 to 15, which is the slot index. For 2112 the index is 0.
3. The table stores the key and the value in slot 0.

Lookup works the same way. Looking up the key computes the same hash, goes to slot 0 and looks at the entry there. The table compares the stored hash number with the one it computed. Only when those numbers match does it call == to confirm that the keys really are the same.

That last point matters. A matching hash number does not prove that two keys are equal. It only says "look here". The equality check makes the final decision.

CPython, the standard Python interpreter, also changes the slot when the first slot is taken. It checks a fixed sequence of other slots (this is called probing) that depends on the hash, until it finds the key or an empty slot. That is a different method from a list of entries in each slot, but the cost works the same way: each slot checked is one more step. You do not need the details to use a dict. They explain why the table size is always a power of two in CPython, which makes & (size - 1) a fast substitute for the remainder after division.

Worked example 1: computing slot numbers

The next program applies the mask to several hash numbers, in a table of 16 slots. It does not use a dict, so you can see the arithmetic directly.

The output is:

hash 0 goes to slot 0
hash 1 goes to slot 1
hash 2 goes to slot 2
hash 16 goes to slot 0
hash 17 goes to slot 1
hash 33 goes to slot 1
hash 2112 goes to slot 0
hash 35 goes to slot 3

Look at the rows for 0 and 16. They have different hash numbers but share slot 0. That is a collision. The hash numbers differ, so the table can tell them apart by the stored hash. But both keys want the same drawer, so the table must check each one with == when it searches that drawer.

Look at 17 and 33. They also share slot 1. The mask only looks at the last four bits, so any two numbers that agree on those four bits land together. Numbers that differ only in bits 4 and above always collide in a table of 16 slots. A bigger table looks at more bits, which is one reason tables grow.

How a hash code is computed for a string

Java builds the hash code of a string from its characters. The rule is a loop. Start with 0. For each character, multiply the running total by 31 and add the character's numeric code. The characters A and a have the codes 65 and 97, which Python gives you with ord.

For "Aa":

• Start with 0.
• Add the code of A: 0 * 31 + 65 = 65.
• Multiply by 31 and add the code of a: 65 * 31 + 97 = 2015 + 97 = 2112.

The result is 2112. Now compute "BB". The code of B is 66:

• Start with 0.
• Add the code of B: 0 * 31 + 66 = 66.
• Multiply by 31 and add the code of B: 66 * 31 + 66 = 2046 + 66 = 2112.

Both strings give 2112. The next program writes the rule in Python and checks it.

The output is:

Aa 2112
BB 2112
Ab 2113
BC 2113
C 67
AaAa 2031744
BBBB 2031744
Aa equals BB: False

The line & 0xFFFFFFFF keeps the running total to 32 bits, the same size as Java's int. Python's integers do not overflow on their own, so the mask is what makes the result match Java. The last if turns the number into a signed value, as Java does.

"Aa" and "BB" collide. They have the same hash number, but they are different strings, so == returns False. A dict that holds both keys sends both to the same first slot. It then probes to another slot for the second key, and it tells them apart with ==. The strings "Ab" and "BC" also collide, and you can check that by hand the same way.

Collisions like these are not rare accidents for short strings. Any two strings with the same hash number collide, however different their letters are. The multiplier 31 is a common choice because it is small, fast to compute and spreads the characters reasonably well. Even so, collisions cannot be avoided completely. There are more possible strings than possible 32-bit numbers, so some strings must share a number.

What a collision costs

When a slot holds one entry, a lookup checks one hash number and at most one == comparison. When a slot holds many entries, a lookup must check each entry in that part of the table until it finds the key or runs out of entries. The cost grows with the number of entries that share a path.

The next program measures that cost. It counts how many times == runs during a series of lookups. The key class has a hash method that the caller controls. In one run the hash codes are spread out, one per key. In the other run every key gets the same hash code, 42. The class counts its __eq__ calls in a module-level variable.

The output is:

n = 500, good hashes: 500 == calls, all hashes 42: 125250 == calls
n = 1000, good hashes: 1000 == calls, all hashes 42: 500969 == calls
n = 2000, good hashes: 2000 == calls, all hashes 42: 2002469 == calls

Read the first line. With good hashes, 500 lookups make 500 == calls, one per lookup. Each key sits alone on its path, so each lookup checks exactly one key.

With all hashes equal to 42, 500 lookups make 125,250 == calls. Every key shares the same path, so a lookup for key number i checks the keys stored before it. The total is about half of n times n, which is why the numbers grow so fast. Doubling n from 1000 to 2000 multiplies the work by about four, not two.

The program prints == calls, not seconds, on purpose. The number does not depend on how fast your computer is. It shows how much work the table does. Timing numbers would change from one machine to another. The exact counts depend on the Python version, because the probing order is an implementation detail, so your numbers may differ slightly. The pattern does not change.

Note what changed between the two runs. The keys and their values are the same, and the table gives correct answers in both runs. Only the hash codes changed, so the bad hash code is the only cause of the slowdown.

Why a bad hash makes lookups slow

A hash function is bad when it sends many keys to few slots. The most extreme case is a function that returns the same number for every key, as in the second run above. The table still gives correct answers, but it has lost its speed. A dict of ten thousand keys then behaves like a list of ten thousand keys, and each lookup checks thousands of entries.

Bad hash functions usually come from one of three mistakes:

• Returning a constant, such as return 1, for every object.
• Using only a small part of the data, such as the length of a name, so most names share a hash.
• Using a field that changes after the object is put in the dict. The next lesson covers this case.

Python's own types have good hash functions. int, str, tuple and the other built-in types spread their values across many slots. When you write your own key class, you must define __hash__ yourself, and you must make it spread values across slots as well as the built-in types do.

Python does not turn a crowded slot into a tree, the way some other languages do. A dict relies on the hash function and the probing order. You should not expect any protection from the table. Write a hash function that spreads keys well.

How the table grows

A table with 16 slots and 1,000 entries would put about 60 entries on each path. That is slow. To keep paths short, CPython grows the table when it fills up. Python does not let you set the load factor, which is the fraction of the table that may be full before it grows. CPython grows the table when it is about two-thirds full. The exact steps depend on the Python version, so this lesson does not depend on them.

Growing the table makes it bigger, and every entry is placed again using the new size. The table then has room for more entries before the next growth. With 1,000 entries and a large enough table, most slots hold zero or one entry. Growing costs time once in a while, but each lookup stays fast on average.

The growth rule also explains why a good hash function matters more as the table gets big. A bad hash function fills the same few slots no matter how large the table is. The table can grow, and the work stays the same.

Common mistakes

Assuming equal hash codes mean equal keys. Two different keys can share a hash code, as "Aa" and "BB" do under the Java rule. The dict must still call == to confirm a match. If you skip the check, you will treat different keys as the same key.

Assuming collisions cannot happen. They can happen with any key type. Plan for them. Use the built-in types or write a careful __hash__.

Writing a hash that ignores most of the data. A __hash__ that returns only the length of a name sends every name of the same length to one place. The dict will still work, but it will be slow for large inputs.

Hashing a field that cannot be hashed. A key class that stores a list in a field and hashes that field fails when the hash is computed. Here is a small class that does this, with its output:

The output is:

caught: unhashable type: 'list'

The message names the type that cannot be hashed, list. The fix is to store a tuple, which can be hashed, or to hash a tuple made from the list, as hash(tuple(self.tags)). The next lesson shows the full pattern for key classes.

Expecting a fast lookup from a bad key. A lookup takes time in proportion to the number of entries that share its path. If you see a dict slow down as it grows, check whether your keys share hash codes.

Practice

Exercise 1. Without running code, work out whether "Ab" and "BC" collide under the Java rule. Use the rule from the string section: multiply the running total by 31 and add each character's code. The codes are A = 65, b = 98, B = 66, C = 67.

Show the answer: they collide. For "Ab": 65 * 31 + 98 = 2015 + 98 = 2113. For "BC": 66 * 31 + 67 = 2046 + 67 = 2113. Both numbers are 2113, so both keys want the same slot.

Exercise 2. A table has 16 slots. Using the mask from the slot section, which slot does the hash number 35 go to?

Show the answer: slot 3. The number 35 is 100011 in binary. The mask & 15 keeps the last four bits, 0011, which is 3. The first worked example prints the same result.

Exercise 3. Which of these strings share a hash code with "Aa" under the Java rule: "BB", "C", "AaAa", "BBBB"? You may use the rule or the Python function from this lesson.

Show the answer: "BB" shares it, with 2112. "C" does not, because its hash is the code of C, which is 67. "AaAa" and "BBBB" both have the hash 2031744, so they collide with each other, but not with "Aa". Appending a two-letter block multiplies the running total by 961, which is 31 squared, and adds the block's hash again. So "AaAa" is 2112 times 961 plus 2112, which is 2031744.

Exercise 4. A dict holds 1,000 keys. Every key's __hash__ returns len(key), the number of characters in the key. Keys are the words k0 to k999, with lengths 2 to 4. Explain why a lookup in this dict may be slow, even though the table has many slots.

Show the answer: only three distinct hash numbers exist, one for each length 2, 3 and 4. So at most three paths are used, however large the table grows. Keys k100 to k999 all have length 4, which is 900 keys on one path. A lookup for one of them checks many keys before it finds its match. In one run of this experiment, 1000 lookups made 409,600 == calls, which is about 410 per lookup. Growing the table does not help, because the hash number does not change when the table grows. The fix is a hash function that uses the content of the key, not its length.

Exercise 5. Read the output of the comparison program again. Why does the count for "all hashes 42" grow faster than the count for "good hashes" when n doubles?

Show the answer: with good hashes each lookup checks one key, so the total is n. Doubling n doubles the total. With every key on one path, each lookup checks about n/2 keys on average, so the total is about n times n divided by 2. Doubling n multiplies the total by four. The printed counts match this: 125,250 at n = 500 and 500,969 at n = 1,000 is close to a factor of four.

Summary

• A dict turns a key into a slot index using the key's hash, so it can find a key without checking every key.
• A collision happens when two different keys share a slot. It is normal, and Python handles it with ==.
• Equal hash codes do not prove equal keys. The table always compares the keys before it decides that two keys match.
• A lookup costs time in proportion to the number of entries that share its path, so a bad hash function that piles keys together makes every lookup slow.
• CPython grows its table when it is about two-thirds full, which keeps paths short when the hash function is good.
• Python randomises string hashes on each run. When you write a key class, define __hash__ yourself, use only fields that never change, and spread the values well.