Hashable, inmutable

De una pregunta SO reciente (ver Crear un diccionario en python que está indexado por listas ) me di cuenta de que probablemente tenía una concepción errónea del significado de objetos hashable e inmutables en python.

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

Hashing es el proceso de convertir una gran cantidad de datos en una cantidad mucho más pequeña (por lo general, un solo número entero) de manera repetible para que pueda consultarse en una tabla en tiempo constante ( O(1) ), lo cual es importante Para algoritmos de alto rendimiento y estructuras de datos.

La inmutabilidad es la idea de que un objeto no cambiará de una manera importante después de que se haya creado, especialmente de cualquier manera que pueda cambiar el valor de hash de ese objeto.

Las dos ideas están relacionadas porque los objetos que se utilizan como claves hash normalmente deben ser inmutables para que su valor de 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, a continuación, se anulará todo el propósito del hashing para la eficiencia.

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

  • ¿Hay objetos mutables que son objetos hashable o inmutables que no son hashable?

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

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

Tipos hashable

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

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

__hash__() debería devolver un entero. La única propiedad requerida es que los objetos que comparan iguales tengan el mismo valor hash; se recomienda mezclar de alguna manera (por ejemplo, utilizando valores exclusivos o) los valores de hash para 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 de hashable también son inmutables.

Sería difícil, pero tal vez no imposible, tener un objeto mutable que, sin embargo, definiera __hash__() .

Desde el Glosario de Python :

Un objeto es hashable si tiene un valor hash que nunca cambia durante su vida útil (necesita un __hash__() ) y puede compararse con otros objetos (necesita un __eq__() o __cmp__() ). Los objetos hash que comparen iguales deben tener el mismo valor hash.

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

Todos los objetos inmutables incorporados de Python son hashable, mientras que no hay contenedores mutables (como listas o diccionarios). Los objetos que son instancias de clases definidas por el usuario son hashable por defecto; todos se comparan de forma desigual, y su valor hash es su id ().

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

Si bien ninguno de los objetos mutables incorporados es hashable, es posible crear 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 rest del objeto contiene propiedades que se pueden cambiar libremente. Siempre que el valor de hash y las funciones de comparación se basen en la identidad pero no en las propiedades mutables, y la identidad nunca cambie, usted cumple con los requisitos.

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

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

No hay 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 donde __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 del hecho de que nunca se comparan iguales. Me cuesta ver de todos modos para definir con utilidad __hash__ () para un objeto mutable que define la comparación por valor.

Nota : Las __lt__ , __le__ , __gt__ y __ge__ no se ven afectadas, por lo que aún puede definir un orden de los objetos hashable, mutables o de otra forma según su valor.

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

 >>> 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 "", line 1, in  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 los registros de SQLAlchemy en algo mutable y más útil para mí, mientras mantengo su capacidad de hash para usarlos como teclas dict.

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

La hashability es ligeramente diferente, y se refiere a la comparación.

hashable Un objeto es hashable si tiene un valor hash que nunca cambia durante su vida útil (necesita un __hash__() ) y puede compararse con otros objetos (necesita un __eq__() o __cmp__() ). Los objetos hash que comparen iguales deben tener el mismo valor hash.

Todas las clases definidas por el usuario tienen el método __hash__ , que de manera predeterminada solo devuelve el ID del objeto. Por lo tanto, un objeto que cumpla con los criterios de hashabilidad 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 hashable, porque si el hash cambia durante la vida útil del objeto, significa que el objeto ha mutado.

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

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

Hashability e inmutabilidad se refieren a instancia de objeto, no a tipo. Por ejemplo, un objeto de tipo tuple puede ser hashable o no.

En Python son en su mayoría intercambiables; ya que se supone que el hash representa el contenido, por lo tanto, es tan mutable como el objeto, y tener un cambio de objeto en el valor del hash lo haría inutilizable como una tecla dict.

En otros idiomas, el valor de 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 hashing. Suponiendo, por supuesto, que un objeto no se mueve en la memoria (como hacen algunos GC). Este es el enfoque utilizado en Lua, por ejemplo. Esto hace que un objeto mutable sea utilizable como una 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 valor múltiple’.

Hashable significa que el valor de una variable puede representarse (o, más bien, codificarse) mediante una constante: cadena, número, etc. Ahora, algo que está sujeto a cambio (mutable) no puede representarse por algo que no lo está. Por lo tanto, cualquier variable que sea mutable no puede ser hashable y, de la misma manera, solo las variables inmutables pueden ser hashable.

Espero que esto ayude …