How dict and set work

Problem

The seat was sold twice

The theater box office keeps the sold seats in a dictionary: seat → name of the customer. A seat is a class with a row and a number:

class Seat:
    def __init__(self, row, number):
        self.row = row
        self.number = number

bookings = {}
bookings[Seat(5, 12)] = "Maria"

print(bookings.get(Seat(5, 12)))
print(len(bookings))
bookings[Seat(5, 12)] = "Ivan"
print(len(bookings))

Output

None
1
2

Maria bought seat 5/12, but get with the same seat returns None. Then Ivan buys the same seat, and the dictionary now has two 5/12 keys. Why?

The idea

Hash: a number from the key

A dictionary does not compare the key with all the others. It computes one whole number from the key, and from it, it knows where to look. This number is called a hash (hash code), and the built-in hash() function returns it. It calls the object's __hash__ method.

print(hash("Maria") == hash("Maria"))
print(hash("Maria") == hash("Marie"))
print(hash("Maria") == hash("maria"))
print(hash(1004))

Output

True
False
False
1004

• Within one run, the same text gives the same number.
• A small change gives a different number: "Maria", "Marie" and "maria" are three different hashes.
• The hash of a whole number is the number itself.
• A hash is fast to compute, no matter how many keys are in the dictionary.

The number itself for text is not printed here on purpose. Python computes the hash of text differently on every run of the program, so you would get a different one. The comparisons come out the same every time.

The method that makes the number is called a hash function.

More precisely, if you are curious

• Why does the hash of text change? If it were known in advance, someone could send a server thousands of keys with the same hash and make the dictionary slow. So Python picks a random "salt" on every run. You can fix it with the PYTHONHASHSEED environment variable, but a program does not rely on the number itself.
• An exception for whole numbers: hash(-1) is -2. In the card on collisions you will see why that is interesting.

• Cryptographic hash functions like SHA-256 are something else. They give a long result, and it is practically impossible to find two texts with the same hash. That is why they are used to check that a file has not been tampered with and to store passwords. hash() is for fast lookups and gives no such protection.

See it

The buckets

Inside, a dict is an array of buckets. The number of the bucket for a key is the remainder of the hash divided by the number of buckets. The hash of text changes on every run, so here the keys are order numbers: for them, the hash is the number itself:

keys = [1007, 2043, 3010, 4051]
buckets = 8
for key in keys:
    h = hash(key)
    index = h % buckets
    print(f"{key} -> {h} -> bucket {index}")

Step by step, in words

1. Four keys (order numbers) and eight empty buckets, numbered 0 to 7.
2. hash(1007) is the number itself, 1007. The remainder when divided by 8 is 7: that is the bucket.
3. 2043 gives bucket 3.
4. 3010 gives bucket 2.
5. 4051 is also in bucket 3: a collision. Here it is drawn as a chain, as in Java. A dict in CPython looks for another free place instead.
6. Looking up 4051: the same number, the same bucket 3. == with 2043: no. With 4051: yes.

• Writing bookings[key] = … computes the bucket and puts the pair there. Looking up computes the same bucket and looks only there. That is why it is fast even with a million keys.
• In Python, % with a positive divisor never gives a negative number, even if the hash is negative: -7 % 8 is 1. A bucket number cannot be negative.
• 2043 and 4051 landed in bucket 3. This is called a collision. The next card is about it.

More precisely, if you are curious

• In CPython the number of buckets in a dictionary is also a power of two, and the search starts from the last bits of the hash. That is a fast remainder of division by the number of buckets.

print(-7 % 8)

Output

1

Try it

Which bucket?

The hash of a whole number is the number itself. The order numbers go into a dictionary with 4 buckets.

What will the program print?

order_ids = [6, 10, 13, 21]
for order_id in order_ids:
    print(f"{order_id} -> bucket {hash(order_id) % 4}")

Answer

6 -> bucket 2
10 -> bucket 2
13 -> bucket 1
21 -> bucket 1

6 -> bucket 6
10 -> bucket 10
13 -> bucket 13
21 -> bucket 21

6 -> bucket 2
10 -> bucket 0
13 -> bucket 1
21 -> bucket 3

6 -> bucket 1
10 -> bucket 2
13 -> bucket 3
21 -> bucket 4

Check

The idea

Collision: hash finds the place, == finds the key

Different keys can have the same hash. In Python, the best-known example is with numbers:

print(hash(-1), hash(-2))

codes = {}
codes[-1] = "minus one"
codes[-2] = "minus two"
print(codes[-1], codes[-2])

Output

-2 -2
minus one minus two

The two keys have the same hash, but the dictionary does not mix them up. In CPython a bucket does not hold a list of pairs: if the place is taken by another key, the dictionary tries another place by a formula until it finds the key or an empty place. At each place it compares the keys with ==.

So the two steps work like this:

1. hash() says where to start looking.
2. == says which of the keys is the one you want.

Now it is clear what happened with the theater seat. Seat has neither __eq__ nor __hash__, so it uses the default ones from object. There, == is the same as is, and the hash is different for every object. The two Seat(5, 12) objects are two different objects, so they are also two different keys.

The idea

The contract: __eq__ and __hash__ together

Seat has to say when two seats are the same seat (__eq__), and give equal seats the same hash (__hash__):

class Seat:
    def __init__(self, row, number):
        self.row = row
        self.number = number

    def __eq__(self, other):
        if not isinstance(other, Seat):
            return NotImplemented
        return self.row == other.row and self.number == other.number

    def __hash__(self):
        return hash((self.row, self.number))

With the same program as in the first card:

bookings = {}
bookings[Seat(5, 12)] = "Maria"

print(bookings.get(Seat(5, 12)))
print(len(bookings))
bookings[Seat(5, 12)] = "Ivan"
print(len(bookings))

Output

Maria
1
1

The rules Python expects:

• If a == b, then hash(a) == hash(b). Always.
• If the hashes are equal, the objects may be different. That is a collision.
• If you write __eq__, write __hash__ too, with the same attributes.

If you write only __eq__, Python does not let you make the mistake quietly. It removes the hash from the class, and an object like that cannot be a key:

class Seat:
    def __init__(self, row, number):
        self.row = row
        self.number = number

    def __eq__(self, other):
        if not isinstance(other, Seat):
            return NotImplemented
        return self.row == other.row and self.number == other.number

Error

TypeError: unhashable type: 'Seat'

bookings[Seat(5, 12)] = "Maria" stops with this error: "unhashable" means "has no hash".

More precisely, if you are curious

• hash((self.row, self.number)) is the hash of the tuple of the attributes. This is the usual way: a tuple computes a hash from all its elements and their order, so 5/12 and 12/5 have different hashes. You can also use a formula, as in Java:

def __hash__(self):
    return 31 * self.row + self.number

• isinstance checks whether the other one is a Seat at all. If it is not, NotImplemented tells Python "I do not know how to compare myself with this", and then Seat(5, 12) == "5/12" is False.
• For a key made of several values, you often do not need a class: the tuple (5, 12) already has == and a hash.

bookings = {}
bookings[(5, 12)] = "Maria"
print(bookings.get((5, 12)))
print(hash((5, 12)) == hash((12, 5)))

Output

Maria
False

Try it

Find the bug

The catalog keeps the products in a set. Two products with the same code are the same product, even if the price has changed. But in with the new price gives False:

catalog = set()
catalog.add(Product("A-100", 25.0))
# The price went down, but it is the same product.
print(Product("A-100", 19.9) in catalog)

Output

False

Which line in the class has the bug?

Pick the line with the bug.

1class Product:2 def __init__(self, code, price):3 self.code = code4 self.price = price56 def __eq__(self, other):7 if not isinstance(other, Product):8 return NotImplemented9 return self.code == other.code1011 def __hash__(self):12 return hash((self.code, self.price))

Check

The idea

The buckets fill up

When there are many pairs, the buckets get long and lookups slow down. That is why a dict grows:

• In CPython a small dictionary has 8 places.
• When there are more pairs than 2/3 of the places, it makes a bigger table and redistributes all the keys. The place depends on the size of the table, so every key is computed again. Here is when it grows, judging by the memory the dictionary takes:

import sys

prices = {}
size = sys.getsizeof(prices)
for i in range(1, 12):
    prices[f"product {i}"] = i
    if sys.getsizeof(prices) != size:
        size = sys.getsizeof(prices)
        print("Grows at pair", i)

Output

Grows at pair 1
Grows at pair 6
Grows at pair 11

• The first time is when the table with 8 places appears. Then it grows at the 6th pair (5 is 2/3 of 8) and at the 11th (10 is 2/3 of 16).
• That is why, on average, writing and looking up are fast, but now and then one write takes longer.

There is a trap too. A key must not change while it is in a dictionary or a set:

seat = Seat(5, 12)
sold = set()
sold.add(seat)

seat.number = 13
print(seat in sold)
print(Seat(5, 12) in sold)
print(len(sold))

Output

False
False
1

The seat was put in the place for 5/12. Then its number became 13, and the hash changed. seat in sold looks in the place for 5/13 and does not find it. Seat(5, 12) in sold looks in the right place, but the object there is no longer equal to 5/12. The element is in the set (the size is 1), but it cannot be found. Python has no final: that the attributes of a key do not change is an agreement. A key that really cannot change is a tuple.

More precisely, if you are curious

• sys.getsizeof gives how many bytes the dictionary itself takes. Here it only serves to see when the table changes.
• A set works the same way, but holds only keys.

Exercise

Your own hashes

Solve the tasks in your editor.

1. A hash for a person. A Person class with a first name, a last name and an age. Write __eq__ and __hash__ from the three attributes, with a tuple. Create Ivan Petrov at 30 twice and once at 31. Print whether the hashes of the first two are equal, whether the hashes of the first and the third are equal, and how many different people are left in a set. Do not print the hashes themselves: with text they change on every run.

Output

True
False
Different people: 2

2. The robot in the warehouse. The robot starts at cell (0, 0) and makes the moves NNEESWWN: N is up (y + 1), S is down, E is right (x + 1), W is left. How many different cells has it visited, counting the starting one? Keep them in a set of Point. With this class the program says 9, but it should say 7. Fix it:

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

Output

Moves: 8
Different cells: 7

3. A hash of a file. A hash_file_content(file_path) function reads the file and returns the hash of its content as hexadecimal text. hash() will not do here: on the next run the same file would have a different hash. Use SHA-256 from the built-in hashlib module: hashlib.sha256(content.encode("utf-8")).hexdigest(). Write three reports: a.txt and b.txt with "October report: €1250", and c.txt with "October report: €1260". Compare their hashes. Different hashes mean different files, and equal SHA-256 hashes in practice mean the same files.

Output

a.txt: 31c9db0c6cb9b9af7e6b355f9e6306b35281291f6a015049da01d1f6858bd293
b.txt: 31c9db0c6cb9b9af7e6b355f9e6306b35281291f6a015049da01d1f6858bd293
c.txt: cb9486eaca5007b8fef9f72a07411f78ed1fcd9a1fad3229c293ee3676024861
a and b: same
a and c: different

More tasks

• Your own hash table. A follow-up to the user table from the last lesson, this time without dict. Make a list of 8 buckets, each a list of username and email pairs. The hash function is the sum of the character codes in the name (ord). Write add, get, and a method that prints how many pairs are in each bucket.
• An ID from an email. generate_user_id(email) returns "U" and the first 8 characters of the SHA-256 of the lowercase email. Is the ID the same for Ivan@Example.com and ivan@example.com? Why will hash() not do here? Can two different emails get the same ID? How would you find out?
• Counting collisions. Compute the place of the keys user1 … user1000 with hash(key) % n for 16, 64 and 1024 buckets, and count how many keys land in a bucket that already has a key. Run the program twice: the count changes a little, because the hash of text changes.
• The shoe box. A Box class with a width, a height and a depth. Two boxes are the same if their sizes are the same, in the same order. Write __eq__ and __hash__ with a tuple, and check the boxes 30×20×10 and 10×20×30 in a set.

Test

Check yourself

1. What does a dict do with the hash of a key?

It computes from it where to start lookingIt compares it with all the other hashesIt stores it instead of the key

2. Two different keys have the same hash. What happens?

Both stay in the dictionary, and == tells them apartThe program stops with an errorThe second one deletes the first

3. a == b is True. What must be true about their hashes?

NothingThey must be differenthash(a) == hash(b), always

4. You use your own Seat class as a key, without __eq__ and __hash__. What does bookings.get(Seat(5, 12)) return?

The program stops with an errorNone: the new object is a different object, and the default == and hash do not look at the attributesThe value put in with bookings[Seat(5, 12)] = …

5. Seat has __eq__ but no __hash__. What happens at bookings[Seat(5, 12)] = "Maria"?

It works as it would with __hash__The keys become textTypeError: unhashable type: Python removes the hash when there is __eq__ without __hash__

6. Which attribute is safe to make part of the __hash__ of a key?

An attribute that does not change and that __eq__ also comparesAn attribute that changes while the object is in a setA random number picked in __init__

Check

Start the lesson over