Locker numbers: hashing, equality and the big picture

Yesterday we cleared the two ghost bags from conveyor 13. One line in the storage ledger remains. Last month B was registered in the lost-and-found lockers, but when its owner came to collect it, the ledger answered "not here". B went back onto the conveyor, and the rest you know up to yesterday.

Han opens the ledger from that time again. Print the list and B is clearly there, yet asking with in gives False. Supervisor Do Miran takes the last report and says, "The locker number is decided by the bag. If the bag changes after it goes in, so does the number."

12-1. Locker numbers: find the slot by hash, confirm with == (8 min)

dict and set are banks of lockers with many slots. Storing or looking up a key always follows the same steps.

1. Compute the key's hash (locker number) with hash(key).
2. Use the hash to choose the starting slot.
3. If the slot is empty, that's the end. When storing, the key goes into that slot; when looking up, the answer is "not here".
4. If the slot is taken, check whether the hash matches and whether == says it is the same key. If not, look at the next slot by a fixed rule.

That requires one promise: if a == b, then hash(a) == hash(b) must hold. If equal keys started searching from different slots, they would never meet.

print(1 == 1.0 == True, hash(1) == hash(1.0) == hash(True))
# True True
print({1: "int", 1.0: "float", True: "bool"})
# {1: 'bool'}

1, 1.0 and True are all == to each other, so their hashes are equal too, and in a dict they are the same key. The key stays as the 1 stored first; only the value was replaced by the last one.

The reverse need not hold. A collision, where hashes are equal but values differ, is normal. The == in step 4 sorts it out.

print(hash(42), hash(-1), hash(-2))
# 42 -2 -2
print(hash(-1) == hash(-2), -1 == -2)
# True False
lockers = {-1: "A", -2: "B"}
print(lockers[-1], lockers[-2])
# A B

In CPython, the hash of a small integer is the integer itself. But -1 means "error" inside the C code, so hash(-1) becomes -2. That is a collision, yet the dict tells the two apart without trouble.

The hash of a string changes every time the program runs. It is a safeguard against attacks that predict hash values. If you need the same values (to reproduce a test, say), fix the environment variable PYTHONHASHSEED.

$ python -c "print(hash('T1'))"
# e.g.: 4646783657884298203
$ python -c "print(hash('T1'))"
# e.g.: -1769311965495050168
$ PYTHONHASHSEED=0 python -c "print(hash('T1'))"
# the same value on every run

So never save hash values to a file or exchange them with other processes. A hash is a number for use within a single run.

The lockers below are simplified to 8 slots. A key starts at the slot given by its hash modulo 8, and if that is taken, moves straight to the next slot. Store 7 and 15, then -1 and -2, one after another to create collisions.

12-2. A key that changed after it went in (10 min)

The lockers put a key in the slot for the number computed when it was stored, and never recompute that number afterwards. What happens if the key's value changes after it goes in, so that its hash changes? Let's check with a deliberately broken key.

class Tag:
    def __init__(self, n):
        self.n = n
    def __eq__(self, other):
        return isinstance(other, Tag) and self.n == other.n
    def __hash__(self):
        return hash(self.n)   # mistake: hashing a value that can change
    def __repr__(self):
        return f"Tag({self.n})"

key = Tag(3)
lockers = {key: "bag B"}
print(Tag(3) in lockers)
# True
key.n = 13
print(lockers)
# {Tag(13): 'bag B'}
print(Tag(13) in lockers, Tag(3) in lockers, key in lockers)
# False False False

The listing shows Tag(13), yet every question gets False.

• Looking up with Tag(13): the search starts at the slot for hash 13. The bag is in the slot for hash 3, so they never meet.
• Looking up with Tag(3): the search does reach the slot for hash 3. But the key in that slot is now Tag(13), so == is False.
• Even looking up with the stored key itself: its hash is now 13, so it takes the same path as the first case.

# continuing the example above
key.n = 3
print(Tag(3) in lockers)
# True

Set the value back to 3 and it is found again. The bag sat in the slot it was put into the whole time. Only the number used to find the slot changed.

That is why Python refuses mutable built-in types as keys altogether. list, dict and set have no hash.

lockers = {}
lockers[[1, 2]] = "bag"
# TypeError: cannot use 'list' as a dict key (unhashable type: 'list')

print(hash((1, 2)) == hash((1, 2)))
# True
hash((1, [2]))
# TypeError: unhashable type: 'list'

A tuple can be a key, but if it contains a list, no hash can be made. As we saw in Lesson 2, a tuple's immutability only covers "the references it holds", and if the list inside changed, the hash would have to change too. For keys, use values that are immutable all the way down, such as (1, (2,)) or a frozenset.

12-3. Define equality, and you define the hash (7 min)

A class that defines nothing compares with is, and its hash is based on identity too. That is why instances can be used as keys. But define only __eq__, and Python sets __hash__ to None (as announced in Lesson 8). The standard of equality has changed, and keeping the old hash would break the promise.

class Label:
    def __init__(self, code):
        self.code = code
    def __eq__(self, other):
        return isinstance(other, Label) and self.code == other.code

print(Label("T1") == Label("T1"), Label.__hash__)
# True None
{Label("T1")}
# TypeError: cannot use 'Label' as a set element (unhashable type: 'Label')

If you need a hash, there are two ways.

1. @dataclass(frozen=True): generates __eq__ and __hash__ from the fields and prevents the fields from being changed.

from dataclasses import dataclass

@dataclass(frozen=True)
class Tag:
    n: int

key = Tag(3)
lockers = {key: "bag B"}
print(lockers[Tag(3)])
# bag B
key.n = 13
# dataclasses.FrozenInstanceError: cannot assign to field 'n'

A plain @dataclass without frozen generates only __eq__, so __hash__ is None. For a class you will use as a key, add frozen=True.

2. Writing __hash__ yourself: bundle exactly the fields __eq__ compares into a tuple and hash that.

class Route:
    def __init__(self, origin, dest):
        self.origin = origin
        self.dest = dest
    def __eq__(self, other):
        if not isinstance(other, Route):
            return NotImplemented
        return (self.origin, self.dest) == (other.origin, other.dest)
    def __hash__(self):
        return hash((self.origin, self.dest))

seen = {Route("ICN", "NRT")}
print(Route("ICN", "NRT") in seen, len({Route("ICN", "NRT"), Route("ICN", "NRT")}))
# True 1

When writing it yourself, there are three rules.

• Build the hash from the same fields that __eq__ compares.
• Don't change those fields while the object is used as a key.
• For an object you can't compare with, return NotImplemented instead of False (Lesson 8).

12-4. The big picture: inspecting the baggage center's management program (15 min)

As a final task, the supervisor brings out the center's old management program. Every bug from the eleven reports is in this one file. Let's look at the output first.

import gc
import weakref

class Bag:
    stickers = []                          # mutable list as a class attribute

    def __init__(self, code, items=[]):    # list as a default argument
        self.code = code
        self.items = items
        self.partner = None

    def __eq__(self, other):
        return isinstance(other, Bag) and self.code == other.code

    def __hash__(self):
        return hash(self.code)             # hash from a value that can change

a = Bag("A1")
b = Bag("B1")
a.items.append("camera")
a.stickers.append("fragile")
print(b.items, b.stickers)
# ['camera'] ['fragile']

shelves = [[]] * 3                         # the same list three times
shelves[0].append("A1")
print(shelves)
# [['A1'], ['A1'], ['A1']]

calls = [lambda: f"gate {g}" for g in (1, 2, 3)]
print([call() for call in calls])
# ['gate 3', 'gate 3', 'gate 3']

lockers = {b: "L7"}
b.code = "B2"                              # key changed after it went in
print(Bag("B1") in lockers, Bag("B2") in lockers)
# False False

a.partner, b.partner = b, a                # two bags holding each other
watch = weakref.ref(a)
del a, b, lockers
print(watch() is None)
# False
gc.collect()
print(watch() is None)
# True

Let's pin down the cause line by line and turn it into a checklist.

Here is the fixed program. Every output now comes out as intended.

import weakref

class Bag:
    def __init__(self, code, items=None):
        self.code = code
        self.items = [] if items is None else list(items)
        self.stickers = []
        self._partner = None

    @property
    def partner(self):
        return self._partner() if self._partner is not None else None

    @partner.setter
    def partner(self, other):
        self._partner = weakref.ref(other)

a = Bag("A1")
b = Bag("B1")
a.items.append("camera")
a.stickers.append("fragile")
print(b.items, b.stickers)
# [] []

shelves = [[] for _ in range(3)]
shelves[0].append("A1")
print(shelves)
# [['A1'], [], []]

calls = [lambda g=g: f"gate {g}" for g in (1, 2, 3)]
print([call() for call in calls])
# ['gate 1', 'gate 2', 'gate 3']

lockers = {b.code: "L7"}                   # the key is a string that doesn't change
lockers["B2"] = lockers.pop(b.code)        # when the code changes, move the key
b.code = "B2"
print("B1" in lockers, "B2" in lockers, lockers[b.code])
# False True L7

a.partner, b.partner = b, a
watch = weakref.ref(a)
del a, b, lockers
print(watch() is None)
# True

Copying what was passed in with items=list(items) is the defensive copy from Lesson 4 as well. With __eq__ and __hash__ removed from Bag, bags themselves are compared by identity, and the string code does the job of the key.

Let's compare the first two bugs (default argument, class attribute) on the tag board. In bug, the items arrows of the two instances converge on one list, and stickers hangs on the spec (class) box.

Let's look back over the twelve lessons, one line each.

Case closed (10 min)

Ghost bag B was a bag that built its hash from its number no. After it went into the locker, its number was rewritten during reclassification, and that changed the path to its slot. Scan the slots one by one without using the hash, and B is still there.

from dataclasses import dataclass

class Bag:
    def __init__(self, no):
        self.no = no
    def __eq__(self, other):
        return isinstance(other, Bag) and self.no == other.no
    def __hash__(self):
        return hash(self.no)

ghost = Bag(3)
lockers = {ghost: "L7"}
ghost.no = 13                                         # number rewritten during reclassification
print(ghost in lockers)
# False
print([v for k, v in lockers.items() if k is ghost])  # scanning one by one without the hash finds it
# ['L7']

@dataclass(frozen=True)
class BagNo:
    no: int

lockers = {BagNo(13): "L7"}                           # store it again under a key that can't change
print(lockers[BagNo(13)], BagNo(13) in lockers)
# L7 True

• Scanning one by one with items() does not use the hash, so it finds B. The price is time proportional to the number of slots.
• The new key BagNo is frozen=True, so its number cannot change after it goes in. If the number changes, build a new BagNo and move the entry over.

Locker L7 opens. B's luggage, locked away for a month, comes out, and Han starts calling the owner. Supervisor Do Miran puts the bundle of tags back in her drawer. "Remember what I told you on the first day? One bag, many tags. Now you can see where every tag hangs, who's holding on to a bag, and which slot a bag is in, right?" Pin points at conveyor 13. Today nothing is going around on it.

Exercises

1. How many slots does {(1, 2): "A", (2, 1): "B"} use? Predict by comparing the == and hash of the two tuples, then check.
2. Rebuild the Tag from 12-2 with @dataclass(frozen=True) and check where key.n = 13 is stopped.
3. Fix the buggy program from 12-4 yourself without looking at the fixed version. For each fix, note which line of the checklist it corresponds to.