example - ¿Cuál es el predeterminado__hash__ en python?

getattr 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 formuladas aquí, como una buena forma de implementar hash , pero me gustaría entender cómo funciona __hash__ predeterminado para objetos personalizados, y si es posible confiar en él.

Me he dado cuenta de que las tablas mutables son explícitamente indescifrables ya que hash({}) genera un error ... pero curiosamente, las clases personalizadas son hashable:

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

Entonces, ¿alguien sabe cómo funciona esta función hash predeterminada? 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 uso 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 asegurarme de que mis hashes personalizados no entren en conflicto con los hash incorporados? p.ej :

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

Answer 1

El hash predeterminado para las clases definidas por el usuario es simplemente devolver su id. Esto proporciona un comportamiento que a menudo es útil; el uso de 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. p.ej:

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


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

Esto coincide con la igualdad predeterminada de las 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 aunque f y g tienen los mismos valores para sus atributos, no son iguales y buscar g en d no encuentra el valor almacenado en f . Además, incluso si cambiamos el valor de f.foo , al buscar f en d aún encontramos el valor:

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

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

Y esto funciona bastante; si defino una clase de 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 que 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 su hash? Es porque todos son contenedores , y generalmente consideramos que los contenedores son, en general, 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 los contenedores mutables tienen un valor transitorio . Alguna lista dada actualmente tiene el valor [1, 2, 3] , pero puede mutarse para 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. Usar objetos como teclas 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 sus preguntas directas:

1) Dado que este hash predeterminado en CPython (aunque aparentemente solo <2.6, de acuerdo con otras respuestas / comentarios) se asigna a la dirección de memoria del objeto, entonces en CPython no pueden chocar dos objetos que usen el hash predeterminado ambos vivos al mismo tiempo sus valores de hash, independientemente de las clases involucradas (y si se está almacenando como una 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) Siempre y cuando no devuelvas como hash personalizado un resultado que es exactamente el hash de algún objeto existente, deberías 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 2

En Python 3 la siguiente función se usa en subclases de object contra el id() del objeto (desde 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 Python de 64 bits y 4 para Python de 32 bits.

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

Puede ver que el hash se calcula a partir de id(a) usando la fórmula (id(a) >> 4) | (id(a) << (8 * SIZEOF_VOID_P - 4)) (id(a) >> 4) | (id(a) << (8 * SIZEOF_VOID_P - 4)) , donde las operaciones bit a bit se realizan en C enteros con signo. Por ejemplo, para el 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'') para que las operaciones bit a bit actúen de la misma manera que lo harían en C (si realiza la misma operación en Python, obtendrá un comportamiento diferente porque no se desbordará). Ver https://.com/a/5994397/161801 .

Answer 3

En qué puede confiar: los objetos personalizados tienen un hash() predeterminado hash() que está basado de alguna manera en la identidad del objeto. es decir, cualquier objeto que utilice 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 .

Edición: originalmente escribí que en los releases 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 4

La documentation indica que los objetos personalizados dependen de id() como su implementación de hash() :

Detalle de implementación de CPython: esta es la dirección del objeto en la memoria.

Si mezcla objetos personalizados con tipos integrados como int podrían ser colisiones hash, pero eso no supone ningún problema si se distribuyen por igual. No investigue demasiado a menos que realmente ataque un problema de rendimiento.

Answer 5

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

Dividido por 16 da True

Answer 6

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

Ver la id() función