¿Cuál es el __hash__ predeterminado en python?

Question

A menudo utilizo elementos funky como claves para los diccionarios, y por lo tanto, me pregunto cuál es la forma correcta de hacerlo, y esto se logra implementando buenos métodos hash para mis objetos. Estoy al tanto de otras preguntas hechas aquí como good way to implement hash, pero me gustaría entender cómo funciona el predeterminado __hash__ para objetos personalizados, y si es posible confiar en él.

he notado que son mutables explícitamente unhashable desde hash({}) genera un error ... pero extrañamente, clases personalizadas son hashable:

>>> class Object(object): pass 
>>> o = Object() 
>>> hash(o) 

Así que, ¿alguien sabe cómo funciona esta función hash por defecto? Al entender esto, me gustaría saber:

¿Puedo confiar en este hash predeterminado, si pongo objetos del mismo tipo que las claves de un diccionario? p.ej. :

key1 = MyObject() 
key2 = MyObject() 
key3 = MyObject() 
{key1: 1, key2: 'blabla', key3: 456} 

¿Puedo confiar en él si utilizo objetos de diferentes tipos como claves en un diccionario? p.ej.

{int: 123, MyObject(10): 'bla', 'plo': 890} 

Y en el último caso también, cómo asegurarse de que mis valores hash personalizados no entrar en conflicto con los valores hash incorporadas? por ejemplo:

{int: 123, MyObject(10): 'bla', MyObjectWithCustomHash(123): 890} 

Answer 1

En qué puede confiar: los objetos personalizados tienen un valor predeterminado hash() que se basa de algún modo en la identidad del objeto. es decir, cualquier objeto que use el hash predeterminado tendrá un valor constante para ese hash a lo largo de su vida útil y diferentes objetos pueden tener o no un valor de hash diferente.

No puede confiar en ninguna relación particular entre el valor devuelto por id() y el valor devuelto por hash(). En la implementación C estándar de Python 2.6 y anteriores, eran lo mismo, en Python 2.7-3.2 hash(x)==id(x)/16.

Edité: originalmente escribí que en los lanzamientos 3.2.3 y posteriores o 2.7.3 o posterior, el valor hash puede ser aleatorio y en Python 3.3 la relación siempre será aleatoria. De hecho, la asignación al azar en este momento solo se aplica a las cadenas de hashing, por lo que, de hecho, la relación de divide por 16 puede continuar por ahora, pero no se base en ella.

Las colisiones hash no suelen importar: en una búsqueda de diccionario para encontrar un objeto, debe tener el mismo hash y también debe comparar igual.Las colisiones solo importan si obtienes una proporción muy alta de colisiones, como en el ataque de denegación de servicio que llevó a las versiones recientes de Python a poder aleatorizar el cálculo de hash.

Answer 2

>>> class C(object): 
...  pass 
... 
>>> c = C() 
>>> hash(c) == id(c) 
True 

véase función id

Answer 3

Los documentation estados que los objetos personalizados se basan en id() como su hash() aplicación:

detalle de implementación CPython: Esta es la dirección del objeto en memoria.

Si se mezclan objetos personalizados con tipos internos como int podría ser su colisiones hash, pero eso no es problema en absoluto si se distribuyen por igual. No investigue demasiado a menos que realmente ataque un problema de rendimiento.

Answer 4

El hash predeterminado para las clases definidas por el usuario es simplemente devolver su id. Esto proporciona un comportamiento que a menudo es útil; utilizar una instancia de una clase definida por el usuario como una clave de diccionario permitirá recuperar el valor asociado cuando se proporcione exactamente el mismo objeto para buscar el valor. por ejemplo:

>>> class Foo(object): 
    def __init__(self, foo): 
     self.foo = foo 


>>> f = Foo(10) 
>>> d = {f: 10} 
>>> d[f] 
10 

Esto coincide con el de igualdad predeterminado de clases definidas por el usuario:

>>> g = Foo(10) 
>>> f == g 
False 
>>> d[g] 

Traceback (most recent call last): 
    File "<pyshell#9>", line 1, in <module> 
    d[g] 
KeyError: <__main__.Foo object at 0x0000000002D69390> 

Tenga en cuenta que a pesar de que f y g tienen los mismos valores para sus atributos, no son iguales y mirando hacia arriba g en d no encuentra el valor almacenado en f. Además, incluso si cambiamos el valor de f.foo, mirando hacia arriba f en d todavía encuentra el valor:

>>> f.foo = 11 
>>> d[f] 
10 

La suposición es que los casos de alguna nueva clase arbitraria deben ser tratados como no equivalente, a menos que el programador específicamente declara las condiciones para que dos instancias se traten como equivalentes definiendo __eq__ y __hash__.

Y esto funciona bastante; si defino una clase Car, probablemente considero que dos autos con atributos idénticos representan dos automóviles diferentes. Si tengo un diccionario mapeando autos a propietarios registrados, no quiero encontrar a Alice cuando busco el auto de Bob, ¡incluso si Alice y Bob tienen automóviles idénticos! OTOH, si defino una clase para representar códigos postales, probablemente quiero considerar dos objetos diferentes con el mismo código para ser representaciones intercambiables de "lo mismo", y en este caso si tuviera un diccionario mapeando códigos postales a estados , Claramente querría poder encontrar el mismo estado con dos objetos diferentes que representan el mismo código postal.

Me refiero a esto como la diferencia entre "tipos de valores" y "tipos de objetos". Los tipos de valor representan algún valor, y es el valor Me importa, no la identidad de cada objeto individual. Dos formas diferentes de obtener el mismo valor son igualmente buenas, y el "contrato" de código que pasa alrededor de los tipos de valor generalmente solo promete darle un objeto con algún valor, sin especificar qué objeto particular es. Para los tipos de objetos OTOH, cada instancia individual tiene su propia identidad, incluso si contiene exactamente los mismos datos que otra instancia. El "contrato" de código que pasa alrededor de los tipos de objetos generalmente promete hacer un seguimiento de los objetos individuales exactos.

Entonces, ¿por qué las clases mutables incorporadas no usan su id como hash? Es porque son todos contenedores, y por lo general consideran contenedores a ser en su mayoría como los tipos de valor, con su valor determinado por los elementos contenidos:

>>> [1, 2, 3] == [1, 2, 3] 
True 
>>> {f: 10} == {f: 10} 
True 

Pero mutables contenedores tienen un valor que es transitoria. Alguna lista dada actualmente tiene el valor [1, 2, 3], pero se puede mutar en tener el valor [4, 5, 6]. Si pudiera usar listas como claves del diccionario, entonces tendríamos que decidir si la búsqueda debe usar el valor (actual) de la lista o su identidad.De cualquier manera, podemos (muy) sorprendernos cuando el valor de un objeto que se está utilizando actualmente como clave de diccionario se modifique al mutarlo. El uso de objetos como claves del diccionario solo funciona bien cuando el valor del objeto es su identidad, o cuando la identidad de un objeto es irrelevante para su valor. Entonces, la respuesta elegida por Python es declarar que los contenedores mutables son inigualables.

---

Ahora, detalles más específicos en respuesta a preguntas directas:

1) Desde este hash predeterminada en CPython (aunque al parecer sólo < 2.6, de acuerdo con otras respuestas/comentarios) mapas en la memoria del objeto dirección, luego en CPython no hay dos objetos que usen hashing predeterminado que estén en vivo al mismo tiempo y que posiblemente entren en conflicto en sus valores de hash, independientemente de las clases involucradas (y si está almacenado como clave de diccionario está en vivo). También esperaría que otras implementaciones de Python que no usan direcciones de memoria como hash aún tengan distribuciones de hash precisas entre los objetos que usen el hashing predeterminado. Entonces sí, puedes confiar en eso.

2) Mientras no devuelva como un hash personalizado un resultado que sea exactamente el hash de algún objeto existente, debería estar relativamente bien. Tengo entendido que los contenedores basados ​​en hash de Python son relativamente tolerantes con funciones hash subóptimas, siempre que no estén completamente degeneradas.

Answer 5

>>> class C(object): 
...  pass 
... 
>>> c = C() 
>>> hash(c) == id(c) 
False 
>>> hash(c) == id(c)/16 
True 

Dividido por 16 da la verdadera

Answer 6

En Python 3 se utiliza la siguiente función en subclases de object contra la id() del objeto (de pyhash.c)

Py_hash_t 
_Py_HashPointer(void *p) 
{ 
    Py_hash_t x; 
    size_t y = (size_t)p; 
    /* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid 
     excessive hash collisions for dicts and sets */ 
    y = (y >> 4) | (y << (8 * SIZEOF_VOID_P - 4)); 
    x = (Py_hash_t)y; 
    if (x == -1) 
     x = -2; 
    return x; 
} 

SIZEOF_VOID_P es 8 para 64 -bit Python y 4 para Python de 32 bits.

>>> class test: pass 
... 
>>> a = test() 
>>> id(a) 
4325845928 
>>> hash(a) 
-9223372036584410438 

se puede ver que el hash se calcula a partir id(a) utilizando la fórmula (id(a) >> 4) | (id(a) << (8 * SIZEOF_VOID_P - 4)), donde se realizan las operaciones bit a bit en C enteros con signo. Por ejemplo, para el a definido anteriormente:

>>> import numpy 
>>> y = numpy.array([4325845928], dtype='int64') 
>>> SIZEOF_VOID_P = 8 
>>> (y >> 4) | (y << (8 * SIZEOF_VOID_P - 4)) 
array([-9223372036584410438]) 

Tenga en cuenta que estoy usando numpy.array(dtype='int64') de manera que las operaciones bit a bit actúan de la misma manera que lo harían en C (si realiza la misma operación en enteros Python se obtiene un comportamiento diferente porque no se desbordan). Ver https://stackoverflow.com/a/5994397/161801.