¿Por qué un dictado de Python puede tener varias claves con el mismo hash?

Estoy tratando de entender la hashfunción de Python bajo el capó. Creé una clase personalizada donde todas las instancias devuelven el mismo valor hash.

class C:
    def __hash__(self):
        return 42

Simplemente asumí que solo una instancia de la clase anterior puede estar en a dicten cualquier momento, pero de hecho a dictpuede tener múltiples elementos con el mismo hash.

c, d = C(), C()
x = {c: 'c', d: 'd'}
print(x)
# {<__main__.C object at 0x7f0824087b80>: 'c', <__main__.C object at 0x7f0823ae2d60>: 'd'}
# note that the dict has 2 elements

Experimenté un poco más y descubrí que si anulo el __eq__método de manera que todas las instancias de la clase se comparen de la misma manera, entonces la dictúnica permite una instancia.

class D:
    def __hash__(self):
        return 42
    def __eq__(self, other):
        return True

p, q = D(), D()
y = {p: 'p', q: 'q'}
print(y)
# {<__main__.D object at 0x7f0823a9af40>: 'q'}
# note that the dict only has 1 element

Así que tengo curiosidad por saber cómo se dictpueden tener varios elementos con el mismo hash.

Para obtener una descripción detallada de cómo funciona el hash de Python, consulte mi respuesta a ¿Por qué el retorno temprano es más lento que los demás?

Básicamente, usa el hash para elegir un espacio en la mesa. Si hay un valor en la ranura y el hash coincide, compara los elementos para ver si son iguales.

Si el hash no coincide o los elementos no son iguales, intenta con otra ranura. Hay una fórmula para elegir esto (que describo en la respuesta a la que se hace referencia), y gradualmente extrae partes no utilizadas del valor hash; pero una vez que los haya usado todos, eventualmente pasará por todos los espacios de la tabla hash. Eso garantiza que eventualmente encontraremos un artículo coincidente o un espacio vacío. Cuando la búsqueda encuentra un espacio vacío, inserta el valor o se da por vencido (dependiendo de si estamos sumando u obteniendo un valor).

Lo importante a tener en cuenta es que no hay listas ni depósitos: solo hay una tabla hash con un número particular de espacios, y cada hash se utiliza para generar una secuencia de espacios candidatos.

Aquí está todo sobre los dictados de Python que pude reunir (probablemente más de lo que a nadie le gustaría saber; pero la respuesta es completa). Un agradecimiento a Duncan por señalar que los dictados de Python usan ranuras y me llevan por esta madriguera de conejo.

• Los diccionarios de Python se implementan como tablas hash .
• Las tablas hash deben permitir colisiones hash, es decir, incluso si dos claves tienen el mismo valor hash, la implementación de la tabla debe tener una estrategia para insertar y recuperar los pares clave y valor de forma inequívoca.
• Python dict usa direccionamiento abierto para resolver colisiones hash (se explica a continuación) (consulte dictobject.c: 296-297 ).
• La tabla hash de Python es solo un bloque continuo de memoria (algo así como una matriz, por lo que puede O(1)buscar por índice).
• Cada espacio de la tabla puede almacenar una y solo una entrada. Esto es importante
• Cada entrada de la tabla en realidad es una combinación de los tres valores:. Esto se implementa como una estructura C (ver dictobject.h: 51-56 )

• La siguiente figura es una representación lógica de una tabla hash de Python. En la siguiente figura, 0, 1, ..., i, ... a la izquierda son índices de las ranuras en la tabla hash (¡son solo para fines ilustrativos y obviamente no se almacenan junto con la tabla!).

  # Logical model of Python Hash table
  -+-----------------+
  0| <hash|key|value>|
  -+-----------------+
  1|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  i|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  n|      ...        |
  -+-----------------+
  

• Cuando se inicializa un nuevo diccionario, comienza con 8 ranuras . (ver dictobject.h: 49 )

• Al agregar entradas a la tabla, comenzamos con algún espacio, ique se basa en el hash de la clave. CPython usa initial i = hash(key) & mask. Dónde mask = PyDictMINSIZE - 1, pero eso no es realmente importante). Solo tenga en cuenta que la ranura inicial, i, que se verifica depende del hash de la clave.
• Si ese espacio está vacío, la entrada se agrega al espacio (por entrada, quiero decir <hash|key|value>). Pero, ¿y si ese espacio está ocupado? Muy probablemente porque otra entrada tiene el mismo hash (¡colisión de hash!)
• Si la ranura está ocupada, CPython (e incluso PyPy) compara el hash Y la clave (por comparación, me refiero a la ==comparación, no a la iscomparación) de la entrada en la ranura con la clave de la entrada actual que se va a insertar ( dictobject.c: 337 , 344-345 ). Si ambos coinciden, entonces cree que la entrada ya existe, se da por vencida y pasa a la siguiente entrada que se insertará. Si el hash o la clave no coinciden, comienza a sondear .
• Probar solo significa que busca las ranuras por ranura para encontrar una ranura vacía. Técnicamente, podríamos ir uno por uno, i + 1, i + 2, ... y usar el primero disponible (eso es sondeo lineal). Pero por razones que se explican maravillosamente en los comentarios (ver dictobject.c: 33-126 ), CPython usa sondeo aleatorio . En el sondeo aleatorio, la siguiente ranura se elige en un orden pseudoaleatorio. La entrada se agrega a la primera ranura vacía. Para esta discusión, el algoritmo real usado para elegir la siguiente ranura no es realmente importante (vea dictobject.c: 33-126 para el algoritmo de sondeo). Lo importante es que se prueben las ranuras hasta que se encuentre la primera ranura vacía.
• Lo mismo sucede con las búsquedas, solo comienza con la ranura inicial i (donde i depende del hash de la clave). Si el hash y la clave no coinciden con la entrada en la ranura, comienza a sondear, hasta que encuentra una ranura con una coincidencia. Si todas las ranuras están agotadas, informa un error.
• Por cierto, el dict cambiará de tamaño si está lleno en dos tercios. Esto evita ralentizar las búsquedas. (ver dictobject.h: 64-65 )

¡Ahí tienes! La implementación de Python de dict comprueba tanto la igualdad hash de dos claves como la igualdad normal ( ==) de las claves al insertar elementos. Entonces, en resumen, si hay dos claves, ay by hash(a)==hash(b), pero a!=b, ambas pueden existir armoniosamente en un dictado de Python. Pero si hash(a)==hash(b) y a==b , entonces no pueden ambos estar en el mismo dictá.

Debido a que tenemos que sondear después de cada colisión de hash, un efecto secundario de demasiadas colisiones de hash es que las búsquedas y las inserciones se volverán muy lentas (como señala Duncan en los comentarios ).

Supongo que la respuesta corta a mi pregunta es: "Porque así es como se implementa en el código fuente;)"

Si bien es bueno saberlo (¿para los puntos frikis?), No estoy seguro de cómo se puede usar en la vida real. Porque a menos que esté tratando de romper algo explícitamente, ¿por qué dos objetos que no son iguales tienen el mismo hash?

Editar : la respuesta a continuación es una de las posibles formas de lidiar con las colisiones de hash, sin embargo, no es así como lo hace Python. La wiki de Python a la que se hace referencia a continuación también es incorrecta. La mejor fuente proporcionada por @Duncan a continuación es la implementación en sí: https://github.com/python/cpython/blob/master/Objects/dictobject.c Pido disculpas por la confusión.

Almacena una lista (o depósito) de elementos en el hash y luego recorre esa lista hasta que encuentra la clave real en esa lista. Una imagen dice más que mil palabras:

Aquí lo ves John Smithy Sandra Deeambos hash 152. Bucket 152contiene ambos. Al buscar Sandra Dee, primero encuentra la lista en el depósito 152, luego recorre esa lista hasta que Sandra Deese encuentra y regresa 521-6955.

Lo siguiente es incorrecto, solo está aquí para el contexto: en la wiki de Python puede encontrar (¿pseudo?) Código de cómo Python realiza la búsqueda.

En realidad, hay varias soluciones posibles para este problema, consulte el artículo de wikipedia para obtener una descripción general: http://en.wikipedia.org/wiki/Hash_table#Collision_resolution

Las tablas hash, en general, deben permitir las colisiones hash. Tendrás mala suerte y dos cosas eventualmente se convertirán en lo mismo. Debajo, hay un conjunto de objetos en una lista de elementos que tiene la misma clave hash. Por lo general, solo hay una cosa en esa lista, pero en este caso, seguirá apilándolas en la misma. La única forma en que sabe que son diferentes es a través del operador igual.

Cuando esto sucede, su rendimiento se degradará con el tiempo, por lo que desea que su función hash sea lo más "aleatoria posible".

En el hilo no vi qué hace exactamente Python con instancias de clases definidas por el usuario cuando lo ponemos en un diccionario como claves. Leamos algo de documentación: declara que solo los objetos hash se pueden usar como claves. Hashable son todas las clases integradas inmutables y todas las clases definidas por el usuario.

Las clases definidas por el usuario tienen métodos __cmp __ () y __hash __ () por defecto; con ellos, todos los objetos se comparan de forma desigual (excepto con ellos mismos) y x .__ hash __ () devuelve un resultado derivado de id (x).

Entonces, si tiene un __hash__ constante en su clase, pero no proporciona ningún método __cmp__ o __eq__, entonces todas sus instancias son diferentes para el diccionario. Por otro lado, si proporciona cualquier método __cmp__ o __eq__, pero no proporciona __hash__, sus instancias siguen siendo desiguales en términos de diccionario.

class A(object):
    def __hash__(self):
        return 42


class B(object):
    def __eq__(self, other):
        return True


class C(A, B):
    pass


dict_a = {A(): 1, A(): 2, A(): 3}
dict_b = {B(): 1, B(): 2, B(): 3}
dict_c = {C(): 1, C(): 2, C(): 3}

print(dict_a)
print(dict_b)
print(dict_c)

Salida

{<__main__.A object at 0x7f9672f04850>: 1, <__main__.A object at 0x7f9672f04910>: 3, <__main__.A object at 0x7f9672f048d0>: 2}
{<__main__.B object at 0x7f9672f04990>: 2, <__main__.B object at 0x7f9672f04950>: 1, <__main__.B object at 0x7f9672f049d0>: 3}
{<__main__.C object at 0x7f9672f04a10>: 3}