Números de taquilla: hash, igualdad y repaso final

Ayer retiramos las dos maletas fantasma de la cinta 13. Solo queda una línea del registro de depósitos. El mes pasado, B se registró en la taquilla de objetos perdidos, pero cuando su dueño vino a buscarla, el registro respondió «no está». B volvió a la cinta, y lo que pasó después es la historia hasta ayer.

Han vuelve a abrir el registro de entonces. Al imprimir la lista, B aparece claramente, pero al preguntar con in sale False. La supervisora Do Miran recibe el último parte y dice: «El número de taquilla lo decide la maleta. Si la maleta cambia después de guardarla, el número también cambia.»

12-1. Números de taquilla: se busca la casilla por hash y se confirma con == (8 min)

dict y set son taquillas con muchas casillas. Cada vez que se guarda o se busca una clave, se siguen los mismos pasos:

1. Se calcula el hash (número de taquilla) de la clave con hash(key).
2. El hash decide la casilla de partida.
3. Si la casilla está vacía, se acaba ahí. Al guardar, se mete en esa casilla; al buscar, es «no está».
4. Si la casilla está ocupada, se comprueba que el hash coincida y que sea la misma clave con ==. Si no, se mira la siguiente casilla según una regla fija.

Por eso hace falta una promesa: si a == b, entonces tiene que cumplirse hash(a) == hash(b). Si dos claves iguales empezaran a buscar en casillas distintas, nunca se encontrarían.

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 y True son == entre sí, así que también tienen el mismo hash, y en un dict son la misma clave. Se queda la clave que se guardó primero, 1, y solo el valor cambia al último.

Lo contrario no tiene por qué cumplirse. Una colisión, mismo hash con valores distintos, es normal. El == del paso 4 las distingue.

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

En CPython, el hash de un entero pequeño es el propio entero. Pero -1 es el valor que dentro de C significa «error», así que hash(-1) da -2. Es una colisión, pero el dict distingue los dos sin problema.

El hash de las cadenas cambia cada vez que se ejecuta el programa. Es una protección contra ataques que intentan predecir los valores de hash. Si necesitas el mismo valor (para reproducir una prueba, por ejemplo), fija la variable de entorno PYTHONHASHSEED.

$ python -c "print(hash('T1'))"
# p. ej.: 4646783657884298203
$ python -c "print(hash('T1'))"
# p. ej.: -1769311965495050168
$ PYTHONHASHSEED=0 python -c "print(hash('T1'))"
# el mismo valor en cada ejecución

Por eso no hay que guardar valores de hash en archivos ni intercambiarlos con otros procesos. El hash es un número que solo vale dentro de una misma ejecución.

La taquilla de abajo está simplificada a 8 casillas. Empieza en la casilla que da el resto de dividir el hash entre 8 y, si está ocupada, pasa directamente a la siguiente. Guarda por orden 7 y 15, y -1 y -2, para provocar colisiones.

12-2. Claves que cambian después de guardarlas (10 min)

La taquilla deja la clave en la casilla del número calculado al guardarla y no vuelve a calcular el número después. ¿Qué pasa si, después de guardarla, el valor de la clave cambia y su hash es otro? Lo comprobamos con una clave mal hecha a propósito.

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)   # error: el hash se basa en un valor que puede cambiar
    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

En la lista se ve Tag(13), pero se pregunte como se pregunte, da False.

• Si buscas con Tag(13): empieza en la casilla del hash 13. La maleta está en la casilla del hash 3, así que no se encuentran.
• Si buscas con Tag(3): sí llega a la casilla del hash 3. Pero la clave de esa casilla ahora es Tag(13), así que == da False.
• Incluso buscando con la propia key que guardaste: su hash ahora es 13, así que sigue el mismo camino que en el primer caso.

# continuación del ejemplo anterior
key.n = 3
print(Tag(3) in lockers)
# True

Si devuelves el valor a 3, vuelve a encontrarse. La maleta estuvo todo el tiempo en la casilla donde se guardó. Lo único que cambió fue el número para encontrar la casilla.

Por eso Python directamente no acepta como claves los tipos integrados cuyo valor puede cambiar. list, dict y set no tienen 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'

Una tupla puede ser clave, pero si contiene una lista, no se le puede calcular el hash. Como vimos en la lección 2, la inmutabilidad de una tupla solo afecta a «las referencias que guarda», y si la lista de dentro cambiara, el hash también tendría que cambiar. Para usar algo como clave, usa valores inmutables hasta el fondo, como (1, (2,)) o frozenset.

12-3. Si decides la igualdad, decides también el hash (7 min)

Una clase que no define nada compara la igualdad con is y calcula el hash a partir de la identidad. Por eso sus instancias se pueden usar como claves. Pero si solo defines __eq__, Python pone __hash__ a None (lo que anunciamos en la lección 8). Si el criterio de igualdad cambia y se sigue usando el hash antiguo, se rompe la promesa.

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')

Si necesitas hash, hay dos formas.

1. @dataclass(frozen=True): genera __eq__ y __hash__ a partir de los campos e impide modificarlos.

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'

Si usas @dataclass sin frozen, solo se genera __eq__, así que __hash__ es None. Si la clase va a usarse como clave, ponle frozen=True.

2. Escribir __hash__ a mano: agrupa en una tupla los mismos campos que compara __eq__ y calcula su hash.

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

Si lo escribes a mano, hay tres reglas:

• Calcula el hash con los mismos campos que compara __eq__.
• No cambies esos campos mientras el objeto se use como clave.
• Ante un objeto con el que no se puede comparar, devuelve NotImplemented en lugar de False (lección 8).

12-4. Repaso final: revisión del programa de gestión del centro de equipajes (15 min)

Como último encargo, la supervisora saca el viejo programa de gestión del centro. En un solo archivo están todos los errores de los once partes anteriores. Empecemos por el resultado de ejecutarlo.

import gc
import weakref

class Bag:
    stickers = []                          # lista mutable como atributo de clase

    def __init__(self, code, items=[]):    # lista como argumento por defecto
        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 basado en un valor que puede cambiar

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

shelves = [[]] * 3                         # la misma lista tres veces
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"                              # cambia la clave después de guardarla
print(Bag("B1") in lockers, Bag("B2") in lockers)
# False False

a.partner, b.partner = b, a                # dos maletas que se llevan la una a la otra
watch = weakref.ref(a)
del a, b, lockers
print(watch() is None)
# False
gc.collect()
print(watch() is None)
# True

Señalemos la causa línea a línea y convirtámoslo en una lista de revisión.

Este es el programa corregido. Todas las salidas son ahora las esperadas.

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"}                   # la clave es una cadena, que no cambia
lockers["B2"] = lockers.pop(b.code)        # al cambiar el código, se traslada la clave
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

Copiar lo recibido con list(items) también es la copia defensiva de la lección 4. Como hemos quitado __eq__ y __hash__ de Bag, las maletas en sí se comparan por identidad y el papel de clave lo cumple el código, que es una cadena.

Comparemos en el tablero los dos primeros errores (argumento por defecto y atributo de clase). En bug, las flechas items de las dos instancias convergen en una sola lista, y stickers cuelga de la caja de la especificación (class).

Repasemos las doce lecciones, una línea cada una.

Caso cerrado (10 min)

La maleta fantasma B calculaba su hash a partir de su número, no. Al reclasificarla después de guardarla en la taquilla, le reescribieron el número y cambió el camino para encontrar su casilla. Si se recorren las casillas una a una sin usar el hash, B sigue ahí.

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                                         # le reescriben el número al reclasificarla
print(ghost in lockers)
# False
print([v for k, v in lockers.items() if k is ghost])  # recorriendo una a una sin hash, está
# ['L7']

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

lockers = {BagNo(13): "L7"}                           # se vuelve a guardar con una clave que no cambia
print(lockers[BagNo(13)], BagNo(13) in lockers)
# L7 True

• Recorrer una a una con items() no usa el hash, así que encuentra a B. A cambio, tarda tanto como casillas haya.
• La nueva clave BagNo es frozen=True, así que no se puede cambiar su número después de guardarla. Si el número cambia, se crea un BagNo nuevo y se traslada.

La taquilla L7 se abre. Sale el equipaje de B, encerrado durante un mes, y Han empieza a llamar a su dueño. La supervisora Do Miran vuelve a guardar el fajo de etiquetas en el cajón. «¿Te acuerdas de lo que te dije el primer día? Una maleta, muchas etiquetas. Ahora ya ves de dónde cuelga cada etiqueta, quién sujeta cada maleta y en qué casilla está cada una, ¿verdad?» Pin señala la cinta 13. Hoy no da vueltas nada.

Ejercicios

1. ¿Cuántas casillas ocupa {(1, 2): "A", (2, 1): "B"}? Compara el == y el hash de las dos tuplas para predecirlo y luego compruébalo.
2. Vuelve a escribir el Tag de 12-2 con @dataclass(frozen=True) y comprueba dónde se bloquea key.n = 13.
3. Arregla tú mismo el programa con errores de 12-4 sin mirar la versión corregida. Cada vez que arregles algo, apunta a qué línea de la lista de revisión corresponde.