De una pregunta reciente de SO (ver Create a dictionary in python which is indexed by lists) Me di cuenta de que probablemente tenía una concepción errónea del significado de los objetos aptos e inmutables en python.Hashable, inmutable
Hashing es el proceso de convertir algunos gran cantidad de datos en una cantidad mucho más pequeña (típicamente un solo número entero) de una manera repetible de modo que se puede consultar en una tabla en tiempo constante (O(1)), que es importante para algoritmos de alto rendimiento y estructuras de datos.
Immutability es la idea de que un objeto no cambiará de alguna manera importante después de que se haya creado, especialmente de alguna 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 deben ser normalmente inmutables para que su valor de hash no cambie. Si se 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ía el objetivo completo de hash para la eficacia.
Para captar 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 clase HashMap.
Técnicamente, hashable significa que la clase define __hash __(). Según los documentos:
__hash __() debería devolver un número entero. La única propiedad requerida es que los objetos que se comparan por igual tengan el mismo valor hash; se recomienda mezclar de alguna manera (por ejemplo, utilizando exclusivo o) los valores hash para los componentes del objeto que también desempeñan 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 quizás no imposible, tener un objeto mutable que, no obstante, definiera __hash __().
Vale la pena señalar que '__hash__' se define por defecto para devolver el' id' del objeto; tienes que salir de tu camino para establecer '__hash__ = None' para hacerlo inigualable. Además, como menciona Mark Ransom, existe una condición adicional de que solo es factible si el valor hash nunca puede cambiar. –
Creo que la respuesta es un poco engañosa, 'list' define' __hash__' en el sentido de que 'hasattr ([1,2,3]," __hash __ ")' devuelve 'True', sin embargo, se llama' hash ([1, 2,3]) 'plantea un' TypeError' (Python 3), por lo que no es exactamente hashable. Confiar en la existencia de '__hash__' no es suficiente para determinar si algo es a) hashable b) inmutable –
Hashable significa que el valor de una variable puede representarse (o, mejor dicho, codificarse) mediante una constante - cadena, número, etc. Ahora bien, algo que está sujeto a cambios (mutable) no puede ser representado por algo que no sea . 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 ...
En Python mayoría son intercambiables; ya que se supone que el hash representa el contenido, por lo que es tan mutable como el objeto, y tener un objeto que cambie el valor del hash lo haría inservible como una clave 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 hash. Suponiendo, por supuesto, que un objeto no se mueva en la memoria (como algunos GC lo hacen). Este es el enfoque utilizado en Lua, por ejemplo. Esto hace que un objeto mutable se pueda utilizar como una clave de tabla; pero crea varias (desagradables) sorpresas para los novatos.
Al final, tener un tipo de secuencia inmutable (tuplas) lo hace más agradable para "claves de valor múltiple".
@javier: 'En Python son en su mayoría intercambiables' Mis dudas se refieren a la parte pequeña no incluida en 'principalmente' – joaquin
Desde el Python Glossary:
un objeto es hashable si tiene un valor hash que nunca cambia durante su vida útil (se necesita un método
__hash__()), y puede ser comparado a otros objetos (que necesita un__eq__()o método__cmp__()). Los objetos que se pueden comparar y que son iguales deben tener el mismo valor hash.La capacidad de acceso hace que un objeto se pueda utilizar como una clave de diccionario y un miembro del conjunto, porque estas estructuras de datos usan internamente el valor hash.
Todos los objetos incorporados inmutables 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 manejables por defecto; todos ellos comparan desigual, y su valor hash es su id().
Los diccionarios y conjuntos deben usar un hash para una búsqueda eficiente en una tabla hash; los valores hash deben ser inmutables, ya que cambiar el hash arruinará las estructuras de datos y hará que el dict o set falle. La manera más fácil de hacer que el valor de hash sea inmutable es hacer que todo el objeto sea inmutable, por lo que los dos se mencionan a menudo juntos.
Si bien ninguno de los objetos mutables incorporados es hashable, es posible hacer un objeto mutable con un valor hash que sea no mutable. Es común que solo una parte del objeto represente su identidad, mientras que el resto del objeto contiene propiedades que pueden cambiarse 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, usted cumplió con los requisitos.
Bueno citación. ¿Quieres decir 'frozenset's, ¿verdad? :) –
@Andrey: los sets congelados son lavables, los conjuntos no; ambos solo pueden contener elementos hashable. En los lugares que Mark mencionó, él estaba en lo cierto, así que no creo que se refiriera a los sets congelados. – tzot
Las clases definidas por el usuario definen de forma predeterminada los tipos hashables (el hash es simplemente el 'id' del objeto). Esto no puede cambiar durante la vida útil del objeto, por lo que es manejable, ¡pero eso no significa que no pueda definir tipos mutables! Lo siento, pero la capacidad de uso no implica inmutabilidad. –
sólo porque se trata de la parte superior Google éxito, he aquí una forma sencilla de hacer un hashable objeto mutable:
>>> 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, me encontré con un uso para algo como esto al crear una clase para emitir registros SQLAlchemy en algo mutable y más útil para mí, manteniendo su capacidad de uso para usar como claves dict.
Hay un implícito, aunque no existe una relación explícita forzado entre inmutable y hashable por la interacción entre los objetos
No hay problema aquí a menos que redefina __eq__ para que la clase de objetos defina la equivalencia en el valor.
Una vez que lo haya hecho, necesita encontrar una función hash estable que devuelva siempre el mismo valor para objetos que representan el mismo valor (por ejemplo, __eq__) devuelve True y nunca cambia durante la vida útil de un objeto.
Es difícil ver una aplicación donde esto es 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 que al hash de creación (b) == almohadilla (c), a pesar del hecho de que nunca se comparan iguales. Me cuesta ver de todos modos para definir útilmente __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 en base a su valor de otro modo.
Inmutables significa que el objeto no cambiará de manera significativa durante su vida útil. Es una idea vaga pero común en los lenguajes de programación.
La capacidad de cambio es ligeramente diferente, y se refiere a la comparación.
hashable un objeto es hashable si tiene un valor hash que nunca cambios durante su vida útil (se necesita un método
__hash__()), y puede ser en comparación con otros objetos (que necesita un método__eq__()o__cmp__()) Los objetos hashables que se comparan iguales deben tener el mismo valor hash.
Todas las clases definidas por el usuario tienen el método __hash__, que de forma predeterminada solo devuelve el ID del objeto. Por lo tanto, un objeto que cumpla con los criterios de capacidad de transferencia no es necesariamente inmutable.
objetos de cualquier nueva clase se declara pueden utilizarse como clave de un diccionario, a menos que se impide que, por ejemplo, tirando de __hash__
Podríamos decir que todos los objetos inmutables son hashable, porque si los cambios de hash 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 es algo lavable (arroja).
d = dict()
d[ (0,0) ] = 1 #perfectly fine
d[ (0,[0]) ] = 1 #throws
La capacidad de transferencia y la inmutabilidad se refieren al objeto instancess, no al tipo. Por ejemplo, un objeto de tipo tuple puede ser hashable o no.
"Los objetos modificables que se comparan por igual deben tener el mismo valor hash". ¿Por qué? Puedo crear objetos que se puedan comparar iguales pero que no tengan el mismo valor hash. – endolith
Es posible crear tales objetos, pero sería una violación de un concepto definido en la documentación de Python. La idea es que, de hecho, podemos utilizar este requisito para derivar tal implicación (lógicamente equivalente): Si los hashes no son iguales, entonces los objetos no son iguales. Muy útil. Muchas implementaciones, contenedores y algoritmos dependen de esta implicación para acelerar las cosas. – user2622016
Casos comunes donde 'comparison! = Identity' es cuando se comparan valores" inválidos "como' float ("nan") == float ("nan") ', o cadenas internas de slices:' "apple" es "apple" 'vs.' "apple" es "crabapple" [4:] ' – sleblanc
En Python, la tupla es inmutable, pero solo se puede manipular si todos sus elementos son lavables.
>>> tt = (1, 2, (30, 40))
>>> hash(tt)
8027212646858338501
>>> tl = (1, 2, [30, 40])
>>> hash(tl)
TypeError: unhashable type: 'list'
Tipos Hashable
Además, no es posible que las tablas hash detecten cuándo cambia el hash de sus teclas (al menos de forma eficiente). Es una trampa común, p. en Java, donde un 'HashMap' se rompe si modifica un objeto utilizado como clave: no se puede encontrar ninguna clave antigua ni nueva, aunque si imprime el mapa, se puede ver allí. – doublep
Hashable e Inmutable están relacionados de alguna manera pero no son lo mismo. P.ej. Las instancias creadas a partir de clases personalizadas que heredan 'object' son procesables pero no inmutables. Estas instancias se pueden usar con las claves de un dict, pero aún se pueden modificar si se transmiten. –