Hashable, inmutable

A partir de una pregunta de SO reciente (consulte Crear un diccionario en Python que está indexado por listas ) me di cuenta de que probablemente tenía una concepción incorrecta del significado de los objetos que se pueden hash e inmutables en Python.

• ¿Qué significa hash en la práctica?
• ¿Cuál es la relación entre hash e inmutable?
• ¿Hay objetos mutables que sean hash o inmutables que no sean hash?

El hash es el proceso de convertir una gran cantidad de datos en una cantidad mucho más pequeña (normalmente un único entero) de forma repetible para que se pueda buscar en una tabla en tiempo constante ( O(1)), lo cual es importante para un alto rendimiento. algoritmos y estructuras de datos.

La inmutabilidad es la idea de que un objeto no cambiará de alguna manera importante después de haber sido creado, especialmente de ninguna manera que pueda cambiar el valor hash de ese objeto.

Las dos ideas están relacionadas porque los objetos que se utilizan como claves hash deben ser normalmente inmutables para que su valor hash no cambie. Si se le permitiera cambiar, la ubicación de ese objeto en una estructura de datos, como una tabla hash, cambiaría y entonces se anularía todo el propósito del hash para lograr eficiencia.

Para comprender realmente la idea, debe intentar implementar su propia tabla hash en un lenguaje como C / C ++, o leer la implementación de Java de la HashMapclase.

• ¿Hay objetos mutables que sean hash o inmutables que no sean hash?

En Python, la tupla es inmutable, pero solo es hash si todos sus elementos son hash.

>>> tt = (1, 2, (30, 40))
>>> hash(tt)
8027212646858338501
>>> tl = (1, 2, [30, 40])
>>> hash(tl)
TypeError: unhashable type: 'list'

Tipos Hashable

• Todos los tipos atómicos inmutables son hash, como str, bytes, tipos numéricos
• Un conjunto congelado siempre es hash (sus elementos deben ser hash por definición)
• Una tupla solo es hash si todos sus elementos son hash
• Los tipos definidos por el usuario son hash de forma predeterminada porque su valor hash es su id ()

Del glosario de Python :

Un objeto es hash si tiene un valor hash que nunca cambia durante su vida (necesita un __hash__()método) y se puede comparar con otros objetos (necesita un __eq__()o__cmp__() método ). Los objetos hash que se comparan iguales deben tener el mismo valor hash.

Hashability hace que un objeto se pueda utilizar como clave de diccionario y miembro de un conjunto, porque estas estructuras de datos utilizan el valor hash internamente.

Todos los objetos incorporados inmutables de Python son hash, mientras que ningún contenedor mutable (como listas o diccionarios) lo es. Los objetos que son instancias de clases definidas por el usuario son hash de forma predeterminada; todos comparan de manera desigual, y su valor hash es su id ().

Los dictados y conjuntos deben usar un hash para una búsqueda eficiente en una tabla hash; los valores hash deben ser inmutables, porque cambiar el hash estropeará las estructuras de datos y hará que el dict o set falle. La forma más fácil de hacer que el valor hash sea inmutable es hacer que todo el objeto sea inmutable, razón por la cual los dos a menudo se mencionan juntos.

Si bien ninguno de los objetos mutables incorporados es hash, es posible hacer un objeto mutable con un valor hash que no sea mutable. Es común que solo una parte del objeto represente su identidad, mientras que el resto del objeto contiene propiedades que pueden cambiar libremente. Siempre que el valor hash y las funciones de comparación se basen en la identidad pero no en las propiedades mutables, y la identidad nunca cambia, cumplirá los requisitos.

Técnicamente, hash significa que la clase define __hash__(). Según los documentos:

__hash__()debe devolver un número entero. La única propiedad requerida es que los objetos que se comparan igual tienen el mismo valor hash; Se recomienda mezclar de alguna manera (p. ej., utilizando exclusivo o) los valores hash de los componentes del objeto que también juegan un papel en la comparación de los objetos.

Creo que para los tipos incorporados de Python, todos los tipos hash también son inmutables.

Sería difícil, pero quizás no imposible, tener un objeto mutable que, no obstante, se definiera __hash__().

Hay una relación implícita incluso si no hay una relación explícita forzada entre inmutable y hash debido a la interacción entre

1. Los objetos hash que se comparan iguales deben tener el mismo valor hash
2. Un objeto es hash si tiene un valor hash que nunca cambia durante su vida.

No hay ningún problema aquí a menos que redefina __eq__para que la clase de objetos defina la equivalencia en el valor.

Una vez que haya hecho eso, necesita encontrar una función hash estable que siempre devuelva el mismo valor para los objetos que representan el mismo valor (por ejemplo, donde __eq__) devuelve True, y nunca cambia durante la vida útil de un objeto.

Es difícil ver una aplicación donde esto sea posible, considere una posible clase A que cumpla con estos requisitos. Aunque existe el caso degenerado obvio en el que __hash__devuelve una constante.

Ahora:-

>>> a = A(1)
>>> b = A(1)
>>> c = A(2)
>>> a == b
True
>>> a == c
False
>>> hash(a) == hash(b)
True
>>> a.set_value(c)
>>> a == c
True
>>> assert(hash(a) == hash(c)) # Because a == c => hash(a) == hash(c)
>>> assert(hash(a) == hash(b)) # Because hash(a) and hash(b) have compared equal 
                                 before and the result must stay static over the objects lifetime.

De hecho, esto significa en la creación hash (b) == hash (c), a pesar de que nunca se comparan iguales. Lucho por ver de todos modos definir de manera útil __hash__() para un objeto mutable que define comparar por valor.

Nota : __lt__, __le__, __gt__y __ge__comparsions no se ven afectados por lo que aún puede definir un ordenamiento de objetos mutables hashable, o de otra manera en función de su valor.

solo porque este es el principal éxito de Google, aquí hay una manera simple de hacer que un objeto mutable sea hash:

>>> class HashableList(list):
...  instancenumber = 0  # class variable
...  def __init__(self, initial = []):
...   super(HashableList, self).__init__(initial)
...   self.hashvalue = HashableList.instancenumber
...   HashableList.instancenumber += 1
...  def __hash__(self):
...   return self.hashvalue
... 
>>> l = [1,2,3]
>>> m = HashableList(l)
>>> n = HashableList([1,2,3])
>>> m == n
True
>>> a={m:1, n:2}
>>> a[l] = 3
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> m.hashvalue, n.hashvalue
(0, 1)

De hecho, encontré un uso para algo como esto al crear una clase para convertir registros SQLAlchemy en algo mutable y más útil para mí, mientras mantenía su capacidad de hash para usar como claves de dic.

Inmutable significa que el objeto no cambiará de manera significativa durante su vida. Es una idea vaga pero común en los lenguajes de programación.

Habilidad es ligeramente diferente y se refiere a la comparación.

hash Un objeto es hash si tiene un valor hash que nunca cambia durante su vida útil (necesita un__hash__()método) y se puede comparar con otros objetos (necesita unmétodo__eq__()o__cmp__()). Los objetos hash que se comparan iguales deben tener el mismo valor hash.

Todas las clases definidas por el usuario tienen un __hash__método, que de forma predeterminada solo devuelve el ID del objeto. Por lo tanto, un objeto que cumple los criterios de capacidad de acceso no es necesariamente inmutable.

Los objetos de cualquier clase nueva que declare se pueden usar como clave de diccionario, a menos que lo impida, por ejemplo, lanzando desde __hash__

Podríamos decir que todos los objetos inmutables son hash, porque si el hash cambia durante la vida del objeto, significa que el objeto mutó.

Pero no del todo. Considere una tupla que tiene una lista (mutable). Algunos dicen que la tupla es inmutable, pero al mismo tiempo, no se puede mezclar (arroja).

d = dict()
d[ (0,0) ] = 1    #perfectly fine
d[ (0,[0]) ] = 1  #throws

La habilidad y la inmutabilidad se refieren al instante de objeto, no al tipo. Por ejemplo, un objeto de tipo tupla puede ser hash o no.

En Python son en su mayoría intercambiables; ya que se supone que el hash representa el contenido, por lo que es tan mutable como el objeto, y si un objeto cambia el valor del hash, sería inutilizable como clave de dictado.

En otros idiomas, el valor hash está más relacionado con la 'identidad' de los objetos, y no (necesariamente) con el valor. Por lo tanto, para un objeto mutable, el puntero podría usarse para iniciar el hash. Suponiendo, por supuesto, que un objeto no se mueve en la memoria (como lo hacen algunos GC). Este es el enfoque utilizado en Lua, por ejemplo. Esto hace que un objeto mutable se pueda utilizar como clave de tabla; pero crea varias sorpresas (desagradables) para los novatos.

Al final, tener un tipo de secuencia inmutable (tuplas) lo hace más agradable para las 'claves de valores múltiples'.

Hash significa que el valor de una variable puede ser representado (o, mejor dicho, codificado) por una constante - cadena, número, etc. Ahora, algo que está sujeto a cambios (mutable) no puede ser representado por algo que no lo está. Por lo tanto, cualquier variable que sea mutable no puede ser hash y, del mismo modo, solo las variables inmutables pueden ser hash.

Espero que esto ayude ...