Códigos hash y funciones hash

En resumen: Un código hash es un número que se calcula a partir de una clave con hash(); dict y set lo usan para elegir dónde buscar, así que encuentran una clave rápido incluso entre un millón.

Problema

El asiento se vendió dos veces

La taquilla del teatro guarda los asientos vendidos en un diccionario: asiento → nombre del cliente. Un asiento es una clase con una fila y un número:

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

bookings = {}
bookings[Seat(5, 12)] = "María"

print(bookings.get(Seat(5, 12)))
print(len(bookings))
bookings[Seat(5, 12)] = "Iván"
print(len(bookings))

Salida

None
1
2

María compró el asiento 5/12, pero get con el mismo asiento devuelve None. Después Iván compra el mismo asiento, y el diccionario ahora tiene dos claves 5/12. ¿Por qué?

La idea

Hash: un número a partir de la clave

Un diccionario no compara la clave con todas las demás. Calcula un número entero a partir de la clave, y con él sabe dónde buscar. Ese número se llama hash (código hash), y lo devuelve la función incorporada hash(). Esta llama al método __hash__ del objeto.

print(hash("María") == hash("María"))
print(hash("María") == hash("Mario"))
print(hash("María") == hash("maría"))
print(hash(1004))

Salida

True
False
False
1004

• Dentro de una misma ejecución, el mismo texto da el mismo número.
• Un cambio pequeño da otro número: "María", "Mario" y "maría" son tres hashes distintos.
• El hash de un número entero es el propio número.
• Un hash se calcula rápido, sin importar cuántas claves haya en el diccionario.

Aquí no se imprime a propósito el número de un texto. Python calcula el hash de un texto de forma distinta en cada ejecución del programa, así que te saldría otro. Las comparaciones salen igual siempre.

El método que produce el número se llama función hash.

Más precisamente, para curiosos

• ¿Por qué cambia el hash de un texto? Si se conociera de antemano, alguien podría enviar a un servidor miles de claves con el mismo hash y volver lento el diccionario. Por eso Python elige una «sal» aleatoria en cada ejecución. Puedes fijarla con la variable de entorno PYTHONHASHSEED, pero un programa no depende del número en sí.
• Una excepción con los números enteros: hash(-1) es -2. En la tarjeta sobre colisiones verás por qué es interesante.

• Las funciones hash criptográficas, como SHA-256, son otra cosa. Dan un resultado largo, y en la práctica es imposible encontrar dos textos con el mismo hash. Por eso se usan para comprobar que un archivo no fue alterado y para guardar contraseñas. hash() sirve para búsquedas rápidas y no da esa protección.

Míralo

Las cubetas

Por dentro, un dict es un array de cubetas. El número de cubeta de una clave es el resto de dividir el hash entre el número de cubetas. El hash de un texto cambia en cada ejecución, así que aquí las claves son números de pedido: para ellos, el hash es el propio número:

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

Paso a paso, en palabras

1. Cuatro claves (números de pedido) y ocho cubetas vacías, numeradas del 0 al 7.
2. hash(1007) es el propio número, 1007. El resto de dividir entre 8 es 7: esa es la cubeta.
3. 2043 da la cubeta 3.
4. 3010 da la cubeta 2.
5. 4051 también cae en la cubeta 3: una colisión. Aquí se dibuja como una cadena, igual que en Java. Un dict de CPython, en cambio, busca otro lugar libre.
6. Se busca 4051: el mismo número, la misma cubeta 3. == con 2043: no. Con 4051: sí.

• Escribir bookings[clave] = … calcula la cubeta y guarda ahí el par. Buscar calcula la misma cubeta y busca solo ahí. Por eso es rápido incluso con un millón de claves.
• En Python, % con un divisor positivo nunca da un número negativo, aunque el hash sea negativo: -7 % 8 es 1. Un número de cubeta no puede ser negativo.
• 2043 y 4051 cayeron en la cubeta 3. Esto se llama colisión. De eso trata la siguiente tarjeta.

Más precisamente, para curiosos

• En CPython el número de cubetas de un diccionario también es una potencia de dos, y la búsqueda empieza por los últimos bits del hash. Es un resto rápido de la división entre el número de cubetas.

print(-7 % 8)

Salida

1

Pruébalo

¿Qué cubeta?

El hash de un número entero es el propio número. Los números de pedido van a un diccionario con 4 cubetas.

¿Qué imprimirá el programa?

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

Respuesta

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

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

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

6 -> cubeta 6
10 -> cubeta 10
13 -> cubeta 13
21 -> cubeta 21

Comprobar

La idea

Colisión: hash encuentra el lugar, == encuentra la clave

Claves distintas pueden tener el mismo hash. En Python, el ejemplo más conocido es con números:

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

codes = {}
codes[-1] = "menos uno"
codes[-2] = "menos dos"
print(codes[-1], codes[-2])

Salida

-2 -2
menos uno menos dos

Las dos claves tienen el mismo hash, pero el diccionario no las confunde. En CPython una cubeta no guarda una lista de pares: si el lugar está ocupado por otra clave, el diccionario prueba otro lugar según una fórmula hasta encontrar la clave o un lugar vacío. En cada lugar compara las claves con ==.

Así que los dos pasos funcionan así:

1. hash() dice dónde empezar a buscar.
2. == dice cuál de las claves es la que buscas.

Ahora queda claro qué pasó con el asiento del teatro. Seat no tiene ni __eq__ ni __hash__, así que usa los de object por defecto. Ahí, == es lo mismo que is, y el hash es distinto para cada objeto. Los dos objetos Seat(5, 12) son dos objetos distintos, así que también son dos claves distintas.

La idea

El contrato: __eq__ y __hash__ juntos

Seat tiene que decir cuándo dos asientos son el mismo asiento (__eq__), y dar a asientos iguales el mismo 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))

Con el mismo programa que en la primera tarjeta:

bookings = {}
bookings[Seat(5, 12)] = "María"

print(bookings.get(Seat(5, 12)))
print(len(bookings))
bookings[Seat(5, 12)] = "Iván"
print(len(bookings))

Salida

María
1
1

Las reglas que espera Python:

• Si a == b, entonces hash(a) == hash(b). Siempre.
• Si los hashes son iguales, los objetos pueden ser distintos. Eso es una colisión.
• Si escribes __eq__, escribe también __hash__, con los mismos atributos.

Si escribes solo __eq__, Python no te deja cometer el error en silencio. Quita el hash de la clase, y un objeto así no puede ser clave:

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)] = "María" se detiene con este error: «unhashable» significa «no tiene hash».

Más precisamente, para curiosos

• hash((self.row, self.number)) es el hash de la tupla de los atributos. Es la forma habitual: una tupla calcula un hash a partir de todos sus elementos y de su orden, así que 5/12 y 12/5 tienen hashes distintos. También puedes usar una fórmula, como en Java:

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

• isinstance comprueba si el otro es siquiera un Seat. Si no lo es, NotImplemented le dice a Python «no sé compararme con esto», y entonces Seat(5, 12) == "5/12" es False.
• Para una clave hecha de varios valores, a menudo no necesitas una clase: la tupla (5, 12) ya tiene == y hash.

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

Salida

María
False

Pruébalo

Encuentra el error

El catálogo guarda los productos en un set. Dos productos con el mismo código son el mismo producto, aunque el precio haya cambiado. Pero in con el precio nuevo da False:

catalog = set()
catalog.add(Product("A-100", 25.0))
# El precio bajó, pero es el mismo producto.
print(Product("A-100", 19.9) in catalog)

Salida

False

¿En qué línea de la clase está el error?

Elige la línea con el error.

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

Comprobar

La idea

Las cubetas se llenan

Cuando hay muchos pares, las cubetas se alargan y las búsquedas se vuelven lentas. Por eso un dict crece:

• En CPython un diccionario pequeño tiene 8 lugares.
• Cuando hay más pares que 2/3 de los lugares, crea una tabla más grande y reparte de nuevo todas las claves. El lugar depende del tamaño de la tabla, así que cada clave se calcula otra vez. Aquí se ve cuándo crece, a juzgar por la memoria que ocupa el diccionario:

import sys

prices = {}
size = sys.getsizeof(prices)
for i in range(1, 12):
    prices[f"producto {i}"] = i
    if sys.getsizeof(prices) != size:
        size = sys.getsizeof(prices)
        print("Crece en el par", i)

Salida

Crece en el par 1
Crece en el par 6
Crece en el par 11

• La primera vez es cuando aparece la tabla de 8 lugares. Después crece en el 6.º par (5 son 2/3 de 8) y en el 11.º (10 son 2/3 de 16).
• Por eso, en promedio, escribir y buscar son rápidos, pero de vez en cuando una escritura tarda más.

También hay una trampa. Una clave no debe cambiar mientras está en un diccionario o en un conjunto:

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

Salida

False
False
1

El asiento se guardó en el lugar de 5/12. Después su número pasó a ser 13, y el hash cambió. seat in sold busca en el lugar de 5/13 y no lo encuentra. Seat(5, 12) in sold busca en el lugar correcto, pero el objeto que está ahí ya no es igual a 5/12. El elemento está en el conjunto (el tamaño es 1), pero no se puede encontrar. Python no tiene final: que los atributos de una clave no cambien es un acuerdo. Una clave que de verdad no puede cambiar es una tupla.

Más precisamente, para curiosos

• sys.getsizeof da cuántos bytes ocupa el propio diccionario. Aquí sirve solo para ver cuándo cambia la tabla.
• Un set funciona igual, pero guarda solo claves.

Ejercicio

Tus propios hashes

Resuelve las tareas en tu editor.

1. Un hash para una persona. Una clase Person con nombre, apellido y edad. Escribe __eq__ y __hash__ a partir de los tres atributos, con una tupla. Crea dos veces a Iván Pérez con 30 años y una vez con 31. Imprime si los hashes de los dos primeros son iguales, si los hashes del primero y el tercero son iguales, y cuántas personas distintas quedan en un conjunto. No imprimas los hashes en sí: con texto cambian en cada ejecución.

Salida

True
False
Personas distintas: 2

2. El robot del almacén. El robot empieza en la celda (0, 0) y hace los movimientos NNEESWWN: N es arriba (y + 1), S es abajo, E es a la derecha (x + 1), W es a la izquierda (W de west, oeste en inglés). ¿Cuántas celdas distintas visitó, contando la inicial? Guárdalas en un conjunto de Point. Con esta clase el programa dice 9, pero debería decir 7. Corrígelo:

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

Salida

Movimientos: 8
Celdas distintas: 7

3. El hash de un archivo. Una función hash_file_content(file_path) lee el archivo y devuelve el hash de su contenido como texto hexadecimal. hash() no sirve aquí: en la siguiente ejecución el mismo archivo tendría otro hash. Usa SHA-256 del módulo incorporado hashlib: hashlib.sha256(content.encode("utf-8")).hexdigest(). Escribe tres informes: a.txt y b.txt con «Informe de octubre: 1250 €», y c.txt con «Informe de octubre: 1260 €». Compara sus hashes. Hashes distintos significan archivos distintos, y hashes SHA-256 iguales significan, en la práctica, archivos iguales.

Salida

a.txt: a7c494bfd367dcfa0a42a273ad6d6d1e5886537b8abf228413732e2a7d29fc8a
b.txt: a7c494bfd367dcfa0a42a273ad6d6d1e5886537b8abf228413732e2a7d29fc8a
c.txt: 55326c55a315a74bbe791da3c40262c0e4186a48b0d4c098801c64390993b9b1
a y b: iguales
a y c: distintos

Más tareas

• Tu propia tabla hash. Una continuación de la tabla de usuarios de la lección anterior, esta vez sin dict. Crea una lista de 8 cubetas, cada una una lista de pares de nombre de usuario y correo. La función hash es la suma de los códigos de los caracteres del nombre (ord). Escribe add, get y un método que imprima cuántos pares hay en cada cubeta.
• Un ID a partir de un correo. generate_user_id(email) devuelve "U" y los primeros 8 caracteres del SHA-256 del correo en minúsculas. ¿El ID es el mismo para Ivan@Example.com y ivan@example.com? ¿Por qué hash() no sirve aquí? ¿Pueden dos correos distintos recibir el mismo ID? ¿Cómo lo averiguarías?
• Contar colisiones. Calcula el lugar de las claves user1 … user1000 con hash(key) % n para 16, 64 y 1024 cubetas, y cuenta cuántas claves caen en una cubeta que ya tiene una clave. Ejecuta el programa dos veces: el número cambia un poco, porque el hash de un texto cambia.
• La caja de zapatos. Una clase Box con ancho, alto y profundidad. Dos cajas son la misma si sus medidas son iguales, en el mismo orden. Escribe __eq__ y __hash__ con una tupla, y comprueba las cajas 30×20×10 y 10×20×30 en un conjunto.

Test

Ponte a prueba

1. ¿Qué hace un dict con el hash de una clave?

Lo compara con todos los demás hashesLo guarda en lugar de la claveCalcula a partir de él dónde empezar a buscar

2. Dos claves distintas tienen el mismo hash. ¿Qué pasa?

La segunda borra la primeraEl programa se detiene con un errorLas dos quedan en el diccionario, y == las distingue

3. a == b es True. ¿Qué debe cumplirse con sus hashes?

hash(a) == hash(b), siempreTienen que ser distintosNada

4. Usas tu propia clase Seat como clave, sin __eq__ ni __hash__. ¿Qué devuelve bookings.get(Seat(5, 12))?

None: el objeto nuevo es otro objeto, y el == y el hash por defecto no miran los atributosEl valor guardado con bookings[Seat(5, 12)] = …El programa se detiene con un error

5. Seat tiene __eq__ pero no __hash__. ¿Qué pasa con bookings[Seat(5, 12)] = "María"?

Funciona igual que con __hash__TypeError: unhashable type: Python quita el hash cuando hay __eq__ sin __hash__Las claves se convierten en texto

6. ¿Qué atributo es seguro incluir en el __hash__ de una clave?

Un atributo que no cambia y que __eq__ también comparaUn atributo que cambia mientras el objeto está en un setUn número aleatorio elegido en __init__

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Archivos · Listas: append, remove y sort · Pila, cola y lista enlazada · dict y set
• Continúa en: dataclass, match y patrones · Tabla hash · Contraseñas · Dependencias: el código ajeno que ejecuta el tuyo
• Ejercicios sobre el tema: Colecciones