2011-10-04 28 views
22

A continuación de la pregunta this, me interesa saber cuándo es el hash de un objeto python calculado?¿Cuándo se calcula el hash de un objeto python y por qué el hash de -1 es diferente?

  1. En el momento de una instancia __init__,
  2. La primera vez que se llama __hash__(),
  3. Cada vez __hash__() se llama, o
  4. Cualquier otra posibilidad puede ser que falte?

¿Esto puede variar según el tipo de objeto?

¿Por qué hash(-1) == -2 mientras que otros enteros son iguales a su hash?

+0

3 está fuera como he [leer] (http://www.laurentluce.com/posts/ python-dictionary-implementation /) se almacena en caché la primera vez que se llama.Asumiría que la segunda opción es correcta, pero como no estoy seguro, no la publicaré como respuesta :) – rplnt

+0

@rplnt: wrong; eso es simplemente cuando se habla de un diccionario. Su hash se almacenará en el diccionario, pero eso no es cierto para hash general. –

+0

@ChrisMorgan En realidad, no creo que python 'dict' almacene valores hash para sus claves. Por supuesto, las clases individuales pueden hacer lo que quieran en su función '__hash__', por lo que el artículo mencionado anteriormente dice que' str' almacena en caché sus valores hash. – max

Respuesta

19

El hash generalmente se calcula cada vez que se usa, ya que puede comprobarlo con facilidad (ver a continuación). Por supuesto, cualquier objeto en particular es libre de almacenar en caché su hash. Por ejemplo, las cadenas CPython hacen esto, pero las tuplas no (por ejemplo, this rejected bug report).

El valor hash -1signalizes an error a CPython. Esto se debe a que C no tiene excepciones, por lo que debe usar el valor de retorno. Cuando un objeto Python __hash__ devuelve -1, CPython cambiará silenciosamente a -2.

Vea usted mismo:

class HashTest(object): 
    def __hash__(self): 
     print('Yes! __hash__ was called!') 
     return -1 

hash_test = HashTest() 

# All of these will print out 'Yes! __hash__ was called!': 

print('__hash__ call #1') 
hash_test.__hash__() 

print('__hash__ call #2') 
hash_test.__hash__() 

print('hash call #1') 
hash(hash_test) 

print('hash call #2') 
hash(hash_test) 

print('Dict creation') 
dct = {hash_test: 0} 

print('Dict get') 
dct[hash_test] 

print('Dict set') 
dct[hash_test] = 0 

print('__hash__ return value:') 
print(hash_test.__hash__()) # prints -1 
print('Actual hash value:') 
print(hash(hash_test)) # prints -2 
5

De here:

El valor hash -1 está reservado (se utiliza para marcar los errores en la implementación C). Si el algoritmo hash genera este valor, simplemente usamos -2 en su lugar.

Como el hash entero es un número entero en sí mismo, se ha cambiado de inmediato.

1

Es fácil ver que la opción # 3 es válida para los objetos definidos por el usuario. Esto permite que el hash varíe si muta el objeto, pero si alguna vez usa el objeto como una clave de diccionario, debe asegurarse de evitar que el hash cambie.

>>> class C: 
    def __hash__(self): 
     print("__hash__ called") 
     return id(self) 


>>> inst = C() 
>>> hash(inst) 
__hash__ called 
43795408 
>>> hash(inst) 
__hash__ called 
43795408 
>>> d = { inst: 42 } 
__hash__ called 
>>> d[inst] 
__hash__ called 

cadenas utilizan la opción # 2: calculan el valor hash de una vez en caché el resultado. Esto es seguro porque las cadenas son inmutables, por lo que el hash nunca puede cambiar, pero si subclase str el resultado puede no ser inmutable, se volverá a llamar al método __hash__. Suele pensarse que las tuplas son inmutables, por lo que podría pensar que el hash podría almacenarse en caché, pero de hecho el hash de una tupla depende del hash de su contenido y eso podría incluir valores variables.

Para @max que no cree que las subclases de str puede modificar el hash:

>>> class C(str): 
    def __init__(self, s): 
     self._n = 1 
    def __hash__(self): 
     return str.__hash__(self) + self._n 


>>> x = C('hello') 
>>> hash(x) 
-717693723 
>>> x._n = 2 
>>> hash(x) 
-717693722 
+0

Si pasa una tupla que contiene valores mutables como argumento para la construcción en la función hash, se generará la excepción TypeError. Así que esta no es la razón por la que las tuplas no almacenan en caché sus valores hash. El enlace al comienzo de [@ PetrViktorin's answer above] (http://stackoverflow.com/a/7648538/336527) proporciona la explicación. Ver también [los comentarios de Guido] (http://mail.python.org/pipermail/python-dev/2003-August/037424.html). Además, ¿está seguro de que el hash no se almacena en caché para las subclases str? Parece devolver el mismo valor que str.hash, que se almacena automáticamente en caché. – max

+0

@max, agregué un ejemplo para usted que muestra que el hash de una subclase 'str' no está en la memoria caché. – Duncan

+0

ah sí, correcto ... Supongo que estaba pensando si no defines '__hash__', está en la memoria caché, pero luego es obvio ya que solo usa' str .__ hash__' en ese caso. – max

Cuestiones relacionadas