Hashing e Igualdades en Python

Este artículo fue publicado originalmente el 15 de abril de 2020 en eng.lyft.com.

Por Roy Williams, traducido por Kevin Woo.

Las cosas se vuelven locas cuando estamos confundidos sobre qué es qué.

En resumen

Trata de usar objetos inmutables en vez de sobreescribir __hash__ y __eq__ para forzar objetos a convertirse en hashables.

Perspectiva general

Los diccionarios (dict) y conjuntos (set) son estructuras de datos utilizadas muchísimo porque tienen una complejidad de O(1) en tiempo de búsqueda. La complejidad O(1) se debe a las funciones de hash que tienen las siguientes características:

• Si a==b entonces hash(a) == hash(b)
• Si hash(a) == hash(b), a podría equivaler a b
• Si hash(a) != hash(b), entonces a != b

Diccionarios y conjuntos, sin importar el lenguaje de programación, asumen lo anterior para habilitar búsquedas en tiempo O(1). Este artículo se concentrará específicamente en Python pero el concepto se puede aplicar a cualquier lenguaje.

Una guía rápida de diccionarios

Los diccionarios de Python son bastante avanzados y optimizados (para más información puedes revisar esta plática por Raymond Hettinger) pero para entender por qué estas propiedades son importantes, revisaremos sus funcionalidades a alto nivel.

Para guardar un objeto:

1. Se llama a __hash__ con la llave para calcular su hash. Si la llave no es un hashable, se lanza un TypeError.
2. Se guarda un (hash, llave, valor) en un arreglo en el índice hash % len(arreglo).
3. Si se necesita cambiar el tamaño del arreglo, se reutilizan los hashes calculados previamente para reinsertar todos los valores al nuevo arreglo.

Para recuperar un objeto con la llave:

1. Se llama a __hash__ con la llave para calcular su hash. Si la llave no es un hashable lanza un TypeError.
2. Se busca en el arreglo, en el índice hash(llave) % len(arreglo), para ver si hay una entrada con el mismo valor de hash. Si existe, se verifica la igualdad primero por la identidad y luego llamando a __eq__.

Para garantizar la funcionalidad del diccionario, se tienen que tomar en cuenta los siguientes puntos:

1. __eq__ y __hash__ deben de corresponder: los objetos equivalentes deben de tener el mismo hash.
2. __hash__ nunca debe cambiar. Cuando un objeto es insertado dentro de un diccionario, su hash nunca vuelve a ser calculado.
3. Los objetos que implementan igualdad lógica (es decir, que implementan __eq__) deben ser inmutables para ser hashables. Si un objeto tiene igualdad lógica, modificar el objeto cambiaría su hash, violando la regla 2. dict, list, set son todos inherentemente mutables y, por lo tanto, no son hashables. str, bytes, frozenset y tuple son inmutables y, por lo tanto, hashables.

Vamos con los detalles

Vamos a ver cómo se comportan los objetos si no implementamos __hash__ y __eq__.

Por defecto, las igualdades y hashes se basan en la identidad de un objeto. La implementación que se muestra abajo es id >> 4 (nunca deberíamos confiar en este detalle de implementación).

Hash of x: 8729258887714
id of x: 139668142203424
id of x >> 4: 8729258887714
Is x equal to itself? True

Los diccionarios y conjuntos asumen que si el objeto tiene una identidad equivalente al de otro objeto en un set o dict, entonces los objetos son equivalentes (es decir, asumimos que un objeto es equivalente a sí mismo). Esto es una optimización importante dado que __eq__ puede ser una función costosa.

Is never_equal in a set of itself? True

__hash__ es llamado una sola vez cuando un objeto es insertado dentro de un dict o un set. Hay que tomar en cuenta que nunca vemos que se llame __hash__ para a o b otra vez aunque forzamos al conjunto a cambiar su tamaño cuando insertamos 10,000 elementos y cuando recuperamos un objeto lógicamente equivalente.

Calling hash for a: 42
Calling hash for b: 37
Calling hash for c: 42
True

Por esto es absolutamente necesario que el __hash__ de un objeto nunca cambie durante el transcurso de su vida. Esto funciona directamente para las identidades de los objetos (si id(a) == id(b), sabemos que a == b).

Si el __hash__ cambia, estaremos en una situación donde los diccionarios y sets ya no funcionan de la manera esperada y tendremos varios bugs muy difíciles de encontrar.

Object is in list: True
Object is in set: True
Logically equivalent object is in list: True
Logically equivalent object is in set: True

Hasta ahora, todo bien. ¡Hemos engañado a Python y forzamos algo que un diccionario no quería hashear a ser un hashable! Pero, ¿qué pasa si mutas d — el diccionario subyacente?

Object is in list: True
Object is in set: False
Logically equivalent object is in list: True
Logically equivalent object is in set: False

¿Qué? Pensé que un objeto siempre era equivalente a sí mismo, ¿por qué está el x en la lista pero no en el conjunto que contiene los mismos objetos? ¿No era lo mismo para los objetos lógicamente equivalentes?

Hay que recordar: todas las optimizaciones que habilitan diccionarios y conjuntos para tener una búsqueda de O(1) requieren que el hash nunca cambie. Por andar peleando en contra del lenguaje hemos introducido un pequeño y confuso bug.

OK, entiendo, pero ¿qué debería hacer entonces?

¡¡Gracias por preguntar!! Si de verdad queremos que estos objetos sean hashables, ¡podemos lograrlo con inmutabilidad!

Podemos utilizar algunos built-ins como tuple y frozenset y algunas otras bibliotecas de terceros como immutables y attrs. Aunque tanto immutables como attrs son bibliotecas de terceros, ambas tienen fuertes análogos en la biblioteca estándar de Python (immutables podría ser parte de la biblioteca estándar en 3.9, ya que se usa como parte de asyncio contextvars y attrs se ha duplicado casi por completo también en la biblioteca estándar en dataclass).

Built-ins
Si tenemos un list que queremos hashear, podemos convertirlo en un tuple para garantizar su inmutabilidad:

Exception when trying to hash a list! unhashable type: 'list'
hash(tuple(x)): 2528502973977326415

Si tenemos un set que queremos hashear, podemos convertirlo en un frozenset para asegurarnos de que sea inmutable manteniendo su búsqueda de O(1).

Exception when trying to hash a set! unhashable type: 'set'
hash(frozenset(x)): -272375401224217160

Clases y Diccionarios
Vamos a utilizar bibliotecas de terceros de calidad, attrs e immutables.

attrs soporta objetos de tipo frozen que pueden ser tratados como inmutables y por ende son hashables. Como cereza del pastel, se elimina un montón de código genérico.

Created an ImmutableThing: ImmutableThing(x=42, y='hello world', computed_field=('hello', 'world'))
Caught an error trying to assign to ImmutableThing! <class 'attr.exceptions.FrozenInstanceError'>
hash(thing): -7021629421173658791
ImmutableThing respects logical equality: True
ImmutableThing as a dictionary key: {'thing': 'thing is a key'}

Para los dict vamos a usar immutables.Map, que es un mapa inmutable y por ende también un hashable. Cualquier cambio crea un nuevo mapa pero deja el mapa subyacente sin tocar. Este método tiene un rendimiento significativamente mayor que un deepcopy.

Exception when trying to hash a dict! unhashable type: 'dict'
hash(m): -4868096002692125985
Map as a dictionary key: {'m': 'map is a key!'}
'immutables._map.Map' object does not support item assignment
m after assignment: <immutables.Map({'c': 3, 'b': 2, 'a': 1}) at 0x7f0705d0d1b0>
m_prime after assignment: <immutables.Map({'c': 3, 'b': 2, 'a': 42}) at 0x7f0705d0d5e8>

Conclusión

Pelear contra el lenguaje para forzar objetos a ser hashable es lento e inseguro (desperdicias dinero, perjudicas los tiempos de respuesta y la fiabilidad). Hemos visto algunas herramientas que puedes usar para convertir un objeto a un hashable preservando el funcionamiento y rendimiento. Nosotros utilizamos Python como ejemplo en el artículo pero estos problemas y reglas no se limitan a solamente Python: son fundamentales para entender el funcionamiento de estructuras de datos como hash maps o hash sets. ¡Este blog también está disponible como un notebook de Jupyter y lo puedes descargar y jugar con los ejemplos tú mismo!

Si te encuentras peleando en contra del lenguaje detente y piensa primero si esta es la manera correcta de lograr lo que quieres.

Si estás interesado en unirte a un equipo en Lyft, ¡estamos contratando! Revisa nuestra página de bolsa de trabajo para más detalles.